首先,对于这篇题解的标题,可以使用一二级标题展示:
Java算法练习题,每天进步一点点(1)
题意说明
本练习题题目数量较多,可根据自己的情况自行选择练习。本文以题目1为例:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
解题思路
本题可以使用滑动窗口算法来解决。具体方法如下:
- 定义一个窗口,用于存储不重复的字符
- 定义两个指针,用于指向窗口的左右边界
- 开始遍历字符串,将右指针向右移动一位
- 如果新字符在窗口中不存在,则将其加入窗口中,并增加右指针
- 如果新字符在窗口中已存在,则需要对左指针进行移动,使窗口中不存在该字符,直到窗口中不含重复字符
- 记录每次操作时窗口的长度,最后返回窗口的最大长度即可
代码实现
Java代码示例:
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, right = 0, maxLen = 0;
while (right < s.length()) {
char ch = s.charAt(right);
while (set.contains(ch)) {
set.remove(s.charAt(left++));
}
set.add(ch);
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
Python代码示例:
def lengthOfLongestSubstring(s: str) -> int:
h = {}
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in h and h[s[right]]>=left:
left = h[s[right]] + 1
h[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
上面的代码对应的是示例1。在实际中还需要根据题目要求进行相应的修改。
总结
本题使用滑动窗口算法,时间复杂度为O(N),空间复杂度为O(K),K为字符集的大小。本题可以通过多次练习来熟悉滑动窗口算法的具体实现及优化。此外,还需要注意代码的可读性和复杂度优化。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java算法练习题,每天进步一点点(1) - Python技术站