请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
数据范围:
"abcabcbb"
3
因为无重复字符的最长子串是"abc",所以其长度为 3。
"bbbbb"
1
因为无重复字符的最长子串是"b",所以其长度为 1。
"pwwkew"
3
因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是子串的长度,"pwke" 是一个子序列,不是子串。
#define MAX_LEN 40000 int lengthOfLongestSubstring(char* s ) { // write code here char buf[MAX_LEN] = {0}; int i = 0,ret =0,tmp=0; int len = strlen(s); while(i<len) { tmp = 0; int l = i,j; while(i<len && buf[s[i]]==0) { buf[s[i]]++; tmp++; i++; } if(i<len && buf[s[i]]>0) { ret = ret>tmp?ret:tmp; memset(buf,0,MAX_LEN); for(j=l;j<i;j++) { if(s[j]==s[i]) break; } i = j+1; } } return ret>tmp?ret:tmp; }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ #include <string.h> #define max(x,y)((x)>(y)?(x):(y)) int lengthOfLongestSubstring(char* s ) { // write code here int len = strlen(s); //appear数组类似于哈希表 appear[s[i]]存放每个字符出现过的次数 //s[i]是字符 如abcab s[0]==s[3]=='a' //不难发现 appear[s[0]]==appear[s[3]]==appear['a'] int appear[10000] = {0}; //ans保存最大长度 int ans = 0; //i和j是不含重复字符的子字符串的首尾指针 for (int i=0, j=0; j<len; j++) { //尾指针j开始扫描 字符出现就次数+1 appear[s[j]]++; //存在重复出现的字符 //如abcab appear[s[0]]==appear[s[3]]==appear[a] while (i<j && appear[s[j]]>1) { //重复出现的字符 出现次数-1 appear[s[i]]--; //首指针i向后移动一位 i++; } //ans取ans和每次子串长度的最大值 ans = max(ans, j-i+1); } return ans; }
int lengthOfLongestSubstring(char* s ) { // write code here int max=0; for(int i=0;s[i]!='\0';i++){ int sum=1; for(int j=i+1;s[j]!='\0';j++){ int si=0; for(int k=j-1;k>=i;k--){ if(s[k]==s[j]) si=1; } if(si==1) break; else sum++; } if(sum>max) max=sum; } return max; }