例题1:LeetCode 第 3 题:无重复字符的最长子串
传送门:英文网址:3. Longest Substring Without Repeating Characters ,中文网址:3. 无重复字符的最长子串 。
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
思路1:使用滑动窗口、“双指针”。
步骤1:首先试一试“右指针”能不能向右边“扩散”,即尝试“扩散”的元素在已经扫过的元素中还没有出现(字母频率为 ),可以向右“扩散”,则频率加 。
步骤2:如果不能扩散,把“左指针”向右移动一格,相应的字母频率减 。然后继续步骤1。
在以上两个步骤中,记录下最长不重复的子串的长度。
Python 代码:滑动窗口、“双指针”典型的写法,在理解的基础上记住它
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
size = len(s)
if size < 2:
return size
l = 0
r = -1
counter = [0 for _ in range(256)]
res = 1
while l < size:
if r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示没有重复元素,r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
else:
# 有重复元素,左边就要减 1
counter[ord(s[l])] -= 1
l += 1
res = max(res, r - l + 1)
return res
Java 代码:
public class Solution4 {
// 定义成频率数组,刘宇波老师给出的思路,使用滑动窗口的思路
// 不是很好理解,可以供参考
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len == 0 || len == 1) {
return len;
}
int[] freq = new int[128];
int res = 1;
int l = 0;
int r = -1;
// 只要左边不越界
while (l < len) {
// r + 1 最多到 len-1 表示没有越界
// freq[s.charAt(r + 1)] == 0 表示下一个字母还没有出现过
// 【这个分类标准是很关键的,r+1 表示接下来要考察的索引位置,=0 表示在 [l,r] 这个区间里没有出现】
// 【这个分类标准是很关键的,r+1 表示接下来要考察的索引位置,=0 表示在 [l,r] 这个区间里没有出现】
// 【这个分类标准是很关键的,r+1 表示接下来要考察的索引位置,=0 表示在 [l,r] 这个区间里没有出现】
if (r + 1 < len && freq[s.charAt(r + 1)] == 0) {
// 右边第 1 个字母加入频率数组,频数 + 1
freq[s.charAt(++r)]++;
} else {
// 如果下一个字符已经越界了,或者右边第 1 个字母是频率数组是曾经出现过的
// 把左边从频数数组中挪掉,即频数减1
freq[s.charAt(l++)]--;
}
res = Math.max(res, r - l + 1);
}
return res;
}
public static void main(String[] args) {
Solution4 solution4 = new Solution4();
String s = "abcabcbb";
int lengthOfLongestSubstring = solution4.lengthOfLongestSubstring(s);
System.out.println(lengthOfLongestSubstring);
}
}
Python 代码:另一种写法,我觉得更直接一些,不过 while 里面还有 while ,看过去不太简洁
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
size = len(s)
if size < 2:
return size
l = 0
r = -1
counter = [0 for _ in range(256)]
res = 1
while l < size:
# 首先"右指针"不断向右边尝试,走到出现重复的最右边
while r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示没有重复元素,r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
# 此时,记录不重复子串是"左指针"固定时候最长
res = max(res, r - l + 1)
# 考虑移动"左指针"
# 此时 s[r+1] 就是已经扫过的区间里重复的元素,要把它剔除出去
while r + 1 < size and s[l] != s[r + 1]:
# 有重复元素,左边就要减 1
counter[ord(s[l])] -= 1
l += 1
# 出了上一个循环以后,还要再把左指针向右移动一格,否则右指针不能向右移动
counter[ord(s[l])] -= 1
l += 1
return res
思路2:隔板法
Python 代码:
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
l = len(s)
if l < 2:
return l
# 隔板法
# key:字符,val 出现的索引
map = dict()
point = 0
res = 1
for i in range(l):
# 关键1:map[s[i]] >= point,等于是可以的
if s[i] in map and map[s[i]] >= point:
# 先把隔板向后移动一位
point = map[s[i]] + 1
# 然后记录最长不重复子串的长度
res = max(res, i - point + 1)
# 关键2:无论如何都更新位置
map[s[i]] = i
return res
思路3:还可以使用“动态规划”完成。
Python 代码:
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
l = len(s)
if l < 2:
return l
# dp[i] 表示以 s[i] 结尾的最长不重复子串的长度
# 因为自己肯定是不重复子串,所以初始值设置为 1
dp = [1 for _ in range(l)]
map = dict()
map[s[0]] = 0
for i in range(1, l):
if s[i] in map:
if i - map[s[i]] > dp[i - 1]:
dp[i] = dp[i - 1] + 1
else:
dp[i] = i - map[s[i]]
else:
dp[i] = dp[i - 1] + 1
# 设置字符与索引键值对
map[s[i]] = i
# 最后拉通看一遍最大值
return max(dp)
参考资料:LeetCode 第 3 题:最长不重复字符串。
(本节完)
网友评论