[size=24px;]Longest Substring Without Repeating Characters[/size]
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.
关于这个题目,最先印到脑子的是一个暴力的算法,即把所有的组合都尝试一遍,进行循环。然后关键就是如何判断字符是否重复,用了一个取巧的方式,即根据HashSet只能保存一份元素的特性进行判断。这样的时间复杂度为O(N^2).具体代码如下。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
HashSet<Character> hs = new HashSet();
for(int i =0;i<s.length()-1;i++){
for(int j = i;j<s.length()-1;j++){
int length = hs.size();
hs.add(s.charAt(j));
if(length == hs.size()){
max = length>max?length:max;
hs.clear();
break;
}
}
}
return max;
}
}
果然这种答案是没法蒙混过关的,Leetcode显示时间过长。
然后接下来有一种更加有效的算法,其实主要还是将上面这个方法中所查询的无效子字符串剔除了。设置两个标志来界定一个局部最长的一个无循环字符串,如果出现字符和先前的一样,那就将前一个标志往前进,一直到重复的那个字符之后,然后后一个标志继续走。而判断字符是否相等是用一个256位的布尔数组进行判断。时间复杂度为到O(n)。代码如下
public class Solution {
public int lengthOfLongestSubstring(String s) {
int maxlen =0;
int begin = 0;
int end = 0;
boolean[] exist = new boolean[256];
for(;end<s.length();end++){
if(exist[s.charAt(end)]){
maxlen = Math.max(maxlen, end-begin);
while(s.charAt(begin) != s.charAt(end)){
exist[s.charAt(begin)] = false;
begin++;
}
begin++;
}else{
exist[s.charAt(end)] = true;
}
}
maxlen = Math.max(maxlen, end-begin);
return maxlen;
}
}
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.
关于这个题目,最先印到脑子的是一个暴力的算法,即把所有的组合都尝试一遍,进行循环。然后关键就是如何判断字符是否重复,用了一个取巧的方式,即根据HashSet只能保存一份元素的特性进行判断。这样的时间复杂度为O(N^2).具体代码如下。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
HashSet<Character> hs = new HashSet();
for(int i =0;i<s.length()-1;i++){
for(int j = i;j<s.length()-1;j++){
int length = hs.size();
hs.add(s.charAt(j));
if(length == hs.size()){
max = length>max?length:max;
hs.clear();
break;
}
}
}
return max;
}
}
果然这种答案是没法蒙混过关的,Leetcode显示时间过长。
然后接下来有一种更加有效的算法,其实主要还是将上面这个方法中所查询的无效子字符串剔除了。设置两个标志来界定一个局部最长的一个无循环字符串,如果出现字符和先前的一样,那就将前一个标志往前进,一直到重复的那个字符之后,然后后一个标志继续走。而判断字符是否相等是用一个256位的布尔数组进行判断。时间复杂度为到O(n)。代码如下
public class Solution {
public int lengthOfLongestSubstring(String s) {
int maxlen =0;
int begin = 0;
int end = 0;
boolean[] exist = new boolean[256];
for(;end<s.length();end++){
if(exist[s.charAt(end)]){
maxlen = Math.max(maxlen, end-begin);
while(s.charAt(begin) != s.charAt(end)){
exist[s.charAt(begin)] = false;
begin++;
}
begin++;
}else{
exist[s.charAt(end)] = true;
}
}
maxlen = Math.max(maxlen, end-begin);
return maxlen;
}
}
发表评论
-
Merge k Sorted Lists
2015-03-12 19:55 325Merge k sorted linked lists and ... -
Generate Parentheses
2015-03-12 19:50 363Given n pairs of parentheses, w ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 307Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 339Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 330Letter Combinations of a Phone ... -
4Sum
2015-03-05 22:26 310Given an array S of n integers, ... -
3Sum Closest
2015-03-05 22:25 291Given an array S of n integers, ... -
3Sum
2015-03-03 22:34 317Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 327Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 326Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 289Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 321Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 365Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 330Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 340Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 227Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 254The string "PAYPALISHIRING ... -
Longest Palindromic Substring
2015-02-12 22:50 333Given a string S, find the long ... -
Add Two Numbers
2015-02-12 22:12 299You are given two linked lists ...
相关推荐
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...
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...
js代码-3. Longest Substring Without Repeating Characters
3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17...
#3:Longest Substring Without Repeating Characters #5:Longest Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先...
Characters.cpp │ │ ├── 004 - Median of Two Sorted Arrays.cpp │ │ └── 005 - Longest Palindromic Substring.cpp │ └── python │ ├── 001 - Two Sum.py │ ├── 002 - Add Two...
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.
Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 Longest Palindromic Substring 中等 回文 ZigZag Conversion 中等 矩阵 重要 Reverse Integer 简单 字串 String to Integer ...
Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to ...
Characters4. Median of Two Sorted Arrays 004. Median of Two Sorted Arrays 005. Longest Palindromic Substring 006. ZigZag Conversion 007. Reverse Integer 008. String to Integer 009. Palindrome Number ...
Repeating Characters 31.1% Medium 0004 Median of Two Sorted Arrays 30.7% Hard 0005 Longest Palindromic Substring 30.1% Medium 0006 ZigZag Conversion 37.5% Medium 0007 Reverse Integer 25.8% Easy 0008 ...
Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122....
Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 10....
java lru leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 ...Longest Substring Without Repeating Characters LeetCode 13 Roman to Integer LeetCode 6 Zi
Longest Substring Without Repeating Characters 哈希表 双指针 滑动窗口 Substring with Concatenation of All Words 哈希表 注意匹配方向 Valid Sudoku 数组 遍历 Sudoku Solver 深度优先遍历 回溯 先检查后修改 ...
Repeating Characters (无重复字符的最长子串) Medium Dual Pointer (Sliding Window), Hash Table 4 Median of Two Sorted Arrays (寻找两个有序数组的中位数) Hard Divide and Conquer 5 Longest Palindromic ...
Characters [Medium] LC4: Longest Palindromic Substring [Medium] LC5: Median Of Two Sorted Arrays [Hard] LC6: Zigzag Conversion [Medium] LC7: Reverse Integer [Easy] LC8: String To Integer Atoi [Medium]...
Characters 32.0% 中等 4 Median of Two Sorted Arrays 36.3% 困难 5 Longest Palindromic Substring 27.6% 中等 6 ZigZag Conversion 45.6% 中等 7 Reverse Integer 33.2% 简单 8 String to Integer (atoi) 18.5% ...
Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring 6.ZigZag Conversion 7.Reverse Integer 8.String To Integer 9.Palindrome Number 10.String To Integer 11....