leetCode解题报告5道题(六)，leetcode解题报告5道

leetCode解题报告5道题(六)，leetcode解题报告5道

题目一：

Longest Substring Without Repeating Characters

 Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

分析：

这道题目的其实考察的就是指针问题而已，由于我是用java,就相当于两个变量对应两个下标，来移动这两个下标就可以解决这个问题了。

我拿一个例子来说明这道题目吧：

如：字符串：wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco

思想：我们可以知道，按照顺序下去，当下标pos指向 “4” （第二个字符b） 时，我们知道，这样子的话，前面的长度就被确定了，就是4了，下次，当我们要再算下一个不重复子串的长度的时候便只能从这个下标为4的字符开始算了。

根据这样的简要分析，我们要注意这道题目的陷阱

1、字符并不只是a-z的字母，有可能是其他的特殊字符或者阿拉伯数字等等，这样子我们可以想到我们也许需要256个空间(ASCII码总数)来存储每个字符上一次出现的位置下标信息。我们记作 position[i],  i 表示字符 c 的 ASCII编码, position[i] 表示字符 c 上一次出现的位置下标。

2、我们需要一个下标变量来指向此次子串的开始位置，记做 start 变量，当下次 pos 指向的当前字符 对应的值 position[i] 的位置在 start 变量的前面的话，那么我们就忽略不考虑（因为我们这次计算子串是从start开始的，所以前面的出现重复的字符就不管了）

分析完了之后，我们就看下代码里面的解释吧！

AC代码：

[java] view plaincopyprint?

1. package cn.xym.leetcode;  
2.   
3. /** 
4.  * @Description:  [计算不重复子串] 
5.  * @Author:       [胖虎]    
6.  * @CreateDate:   [2014-4-26 下午7:19:25] 
7.  * @CsdnUrl:      [http://blog.csdn.net/ljphhj] 
8.  */  
9. public class Solution {  
10.     public int lengthOfLongestSubstring(String s) {  
11.         if (s == null || s.equals("")){  
12.             return 0;  
13.         }  
14.         int len = s.length();  
15.         int[] position = new int[256];//256:对应ASCII码总数  
16.         int maxLength = 0;  
17.           
18.         //子串开始位置默认为-1  
19.         int start = -1;  
20.         //初始化所有字符的位置下标都为-1  
21.         for (int i=0; i<256; ++i){  
22.             position[i] = -1;  
23.         }  
24.         //遍历字符串  
25.         for (int pos=0; pos<len; ++pos){  
26.             char c = s.charAt(pos);  
27.             //注: 当出现的重复字符串的位置在start后面的话，我们才更新下一次计算子串的起始位置下标  
28.             if (position[c] > start){  
29.                 start = position[c];  
30.             }  
31.             if (pos - start> maxLength){  
32.                 maxLength = pos - start;  
33.             }  
34.             position[c] = pos;  
35.         }  
36.         return maxLength;  
37.     }  
38.     public static void main(String[] args) {  
39.         int result = new Solution().lengthOfLongestSubstring("wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco");  
40.         System.out.println(result);  
41.     }  
42. }