3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
很早就就看到了这个题目了，但是之前都没做，现在打算试一下。
给我的感觉，一看想用二分法来做，先看题目给出的子串是不是最长子串，如果是的话那就木有问题，如果不是就分成两半，考虑最中间和两边的。
分成左右两部分的处理和最开始给出的字符串的处理一样，现在考虑的就是跨中间的那一段的最长子串怎么确定，这是当时没想出来的地方。
这里我想到的做法是从图中红线左侧第一个a向红线右侧找出最长的子串，然后又从a开始向左找起。
另一个从红线右侧的b开始向左找起，找到最长子串之后再向右找。是不是说的有点复杂。。。
大概思路是出来了，然后就看具体怎么写了
1 #include2 #include 3 4 int isRepeat(char *a, int left, int right); 5 int getRight(char *s, int left, int right); 6 int getLeft(char *s, int left, int right); 7 int getNonRepeat(char *s, int left, int right); 8 int lengthOfLongestSubstring(char* s); 9 10 int main(void) { 11 12 char a[100]; 13 gets(a); 14 fprintf(stderr, "you input a string: [%s]\n", a); 15 fprintf(stderr, "不重复子串的长度为%d\n", lengthOfLongestSubstring(a)); 16 } 17 18 19 int getRight(char *s, int left, int right) { 20 21 int map[127], i; 22 memset(map, 0, sizeof(map)); 23 24 int l = (left + right)/2; 25 int r = l+1; 26 27 if(s[l] == s[r]) { 28 return 0; 29 } 30 31 int pos = s[l]%127; 32 map[pos] = map[pos] + 1; 33 pos = s[r]%127; 34 map[pos] = map[pos] + 1; 35 int count = 2; 36 for(i=r+1; i<=right && s[i] != '\0'; i++) { 37 pos = s[i]%127; 38 if ( (map[pos] = map[pos] + 1) > 1) 39 break; 40 else 41 count++; 42 } 43 44 for(i=l-1; i>=left; --i) { 45 pos = s[i]%127; 46 if ( (map[pos] = map[pos] + 1) > 1) 47 return count; 48 else 49 count++; 50 } 51 52 return count; 53 } 54 55 int getLeft(char *s, int left, int right) { 56 57 int map[127], i; 58 memset(map, 0, sizeof(map)); 59 60 int l = (left + right)/2; 61 int r = l+1; 62 if(s[l] == s[r]) { 63 return 0; 64 } 65 int pos = s[l]%127; 66 map[pos] = map[pos] + 1; 67 pos = s[r]%127; 68 map[pos] = map[pos] + 1; 69 int count = 2; 70 71 for(i=l-1; i>=left; --i) { 72 pos = s[i]%127; 73 if ( (map[pos] = map[pos] + 1) > 1) 74 break; 75 else 76 count++; 77 } 78 79 for(i=r+1; i<=right && s[i] != '\0'; i++) { 80 pos = s[i]%127; 81 if ( (map[pos] = map[pos] + 1) > 1) 82 return count++; 83 else 84 count++; 85 } 86 87 return count; 88 } 89 90 int isRepeat(char *a, int left, int right) { 91 int map[127] ,i; 92 memset(map, 0, sizeof(map)); /* clear map */ 93 for(i=left; i<=right && a[i] != '\0'; i++) { 94 int pos = a[i]%127; 95 if((map[pos] = map[pos] + 1) > 1) 96 return map[pos]; 97 } 98 return 0; 99 }100 101 int getNonRepeat(char *s, int left, int right) {102 103 104 105 if(isRepeat(s, left, right) == 0) { /* 如果这个串本身就是自己的最大不重复子串 */106 printf("%d %d\n", left, right);107 return right-left + 1;108 }109 110 int len = right - left + 1;111 if(len == 0)112 return 0;113 else if(len == 1)114 return 1;115 else if(len == 2 && s[left] == s[right])116 return 1;117 else {118 int n_l = getRight(s, left, right);119 int n_r = getLeft(s, left, right);120 int sub_n_l = getNonRepeat(s, left, (left+right)/2);121 int sub_n_r = getNonRepeat(s, (left+right)/2+1, right);122 123 if(n_l < n_r)124 n_l = n_r;125 if(n_l < sub_n_l)126 n_l = sub_n_l;127 if(n_l < sub_n_r)128 n_l = sub_n_r;129 130 return n_l;131 }132 }133 134 int lengthOfLongestSubstring(char* s) {135 int length = 0, i=0;136 while(s[i++] != '\0')137 length++;138 printf("输入的字符串的长度为%d\n", length);139 return getNonRepeat(s, 0, length-1);140 }
我很郁闷啊，Output是我计算的输出，Expected是OJ认为的答案，但是对于这个sample来说，明显是我对啊。。。辣鸡leetcode