剑指 Offer 48. 最长不含重复字符的子字符串
程序员文章站
2022-07-14 08:08:04
...
解法 动态规化
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) return 0;
char[] chars = s.toCharArray();
return lengthOfLongestSubstring(chars);
}
private int lengthOfLongestSubstring(char[] chars) {
// f(i)代表以第i个字符结尾,不包含重复字符的子字符串的最大长度
// 不含重复字符的子字符串的最大长度
int maxLength = 0;
// f(i-1)
int curLength = 0;
// 数组用于记录任意字符之前出现的位置,ASCII码表一个128个字符
int[] position = new int[128];
Arrays.fill(position,-1);
for(int i = 0; i < chars.length; ++i) {
// 第i个字符之前出现的位置
int preIndex = position[chars[i]];
// 第i个字符之前没有出现过,或者第i个字符与它上次出现位置的距离大于f(i-1)
if(preIndex < 0 || i - preIndex > curLength) {
curLength++;
// 第i个字符出现在f(i-1)对应的子字符串之中
}else {
if(curLength > maxLength)
maxLength = curLength;
curLength = i - preIndex;
}
position[chars[i]] = i;
}
if(curLength > maxLength)
maxLength = curLength;
return maxLength;
}
}
上一篇: element-ui 本地化使用教程
下一篇: ELK(1):ELK组件下载
推荐阅读
-
Leetcode刷题记录——面试题48. 最长不含重复字符的子字符串
-
20200329-剑指offer-面试题48. 最长不含重复字符的子字符串(滑动窗口)
-
剑指 Offer 48. 最长不含重复字符的子字符串
-
剑指 Offer 48. 最长不含重复字符的子字符串
-
剑指Offer 48. 最长不含重复字符的子字符串(Medium)
-
Leetcode 剑指 Offer 48. 最长不含重复字符的子字符串
-
剑指 Offer 48. 最长不含重复字符的子字符串 -- DP解法
-
《剑指offer》-- 复杂链表的复制、字符串的排列、数组中出现次数超过一半的数字、连续子数组的最大和
-
leetcode 3 最长不含重复字符的子字符串
-
(C++)剑指offer-54:字符流中第一个不重复的字符(字符串)