首页 > 代码库 > leetcode longest substring without repeating characters(medium) /java

leetcode longest substring without repeating characters(medium) /java

2024-09-19 21:10:00   217人阅读

上题：

技术分享

 

最简单粗暴的方法：

技术分享 
 1 public class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         String s1=new String();
 4         char[] c=s.toCharArray();
 5         int len=s.length();
 6         boolean[] f=new boolean[1000];
 7         int i=0;
 8         for(i=0;i<1000;i++)
 9             f[i]=false;
10         int max=0,temp=0;
11         for(i=0;i<len;i++)
12         {
13             
14             int index=c[i];
15             if(f[index]==false)
16             {
17                 temp++;
18                 f[index]=true;
19                 if(temp>max)
20                     max=temp;
21             }
22             else
23             {
24                 
25                 for(int j=0;j<1000;j++)
26                     f[j]=false;
27                 
28                 i=i-temp;
29                 temp=0;
30             }
31         }
32         return max;
33     }
34 }
View Code

 最长不重复子序列。因为不必返回序列，只需返回长度。每次都比较当前长度与最大长度，时时更新最大长度。

故用数组flag标记某字符是否曾经出现过。如果出现过，那么清零temp，回到那遥远的开头。

解释一下，到底回到哪里去。我这里将i=i-temp，然后清零temp。

比如说，dvda。正确输出应该是3。所以我们发现第二个d重复时，不应该直接从这里开始，而是应该回到第一个d的下一个字符即v。那么将i-temp，因为在for循环中，i会自加1.于是就从v又一次开始了。

也许用线性规划，会来得高端一点。

 

leetcode longest substring without repeating characters(medium) /java


联系
我们