前言:
此时咱们对“最长子串动态规划”大约比较关心,咱们都想要了解一些“最长子串动态规划”的相关文章。那么小编也在网摘上汇集了一些有关“最长子串动态规划””的相关知识,希望各位老铁们能喜欢,姐妹们快快来学习一下吧!昨天面试一个候选人一个算法题:无重复字符的最长子串
吭哧吭哧半天一行代码没写出来啊,后来我尝试提示他,先从暴力解法入手应该怎么想?还是没思路,哎呀妈想让你面试通过是真的难。
#来点儿干货#无重复字符的最长子串是一个常见的字符串处理问题,可以通过滑动窗口的方法来解决。滑动窗口是一种数组/字符串问题处理方法,通过维护一个窗口,能够在O(N)的时间复杂度内解决问题。
滑动窗口思路初始化:创建一个整数变量 maxLen 用来保存最长子串的长度,初始化为0。创建两个指针 left 和 right,分别表示窗口的左右边界,初始化都为0。滑动窗口:创建一个哈希集合 HashSet 来存储窗口中的字符,确保字符的唯一性。移动右指针 right 来扩展窗口,每次循环向 HashSet 中添加一个新字符。检查重复:如果新添加的字符在 HashSet 中已存在,说明窗口中有重复字符,此时需要移动左指针 left,并从 HashSet 中移除对应的字符,直到移除了重复的字符。更新最大长度:在每次右指针移动后,更新 maxLen 的值,使其保持为当前最长无重复字符子串的长度。循环结束条件:当右指针 right 移动到字符串的末尾时,结束循环。滑动窗口Java 解法
下面是解决这个问题的 Java 代码实现:
import java.util.HashSet;public class Solution { public int lengthOfLongestSubstring(String s) { HashSet<Character> set = new HashSet<>(); int maxLen = 0; int left = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 如果字符已存在于HashSet中,移动左指针并从HashSet中移除字符 while (set.contains(c)) { set.remove(s.charAt(left)); left++; } // 添加当前字符到HashSet中 set.add(c); // 更新最大子串长度 maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } public static void main(String[] args) { Solution solution = new Solution(); String s = "abcabcbb"; System.out.println(solution.lengthOfLongestSubstring(s)); // 输出应为 3 }}
该代码实现了无重复字符最长子串的查找,并且时间复杂度是O(N),其中N是字符串的长度。每个字符最多被访问两次(一次是右指针移动,一次是左指针移动)。
上述是效率最高的解法,可能确实不容易想到,但是除此之外还有很多其他解法啊;咱不至于啥也想不到啊。
解法 1:暴力法
这是最直观的方法,枚举所有的子串,然后检查每个子串是否含有重复的字符。这种方法的时间复杂度是O(n^3),空间复杂度是O(min(n, m)),其中n是字符串的长度,m是字符集的大小。
public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxLen = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { if (allUnique(s, i, j)) { maxLen = Math.max(maxLen, j - i); } } } return maxLen; } public boolean allUnique(String s, int start, int end) { Set<Character> set = new HashSet<>(); for (int i = start; i < end; i++) { Character ch = s.charAt(i); if (set.contains(ch)) return false; set.add(ch); } return true; }}解法 2:优化的暴力法
可以对暴力法进行一定的优化,例如,当我们找到一个重复的字符时,不需要从上一个起始位置的下一个字符开始重新检查,而是直接跳过重复的字符。
解法 3:动态规划 + 哈希表
使用动态规划的思想,我们可以记录以第i个字符结尾的最长无重复字符的子串长度,并利用哈希表来存储字符最后一次出现的位置。
import java.util.HashMap;public class Solution { public int lengthOfLongestSubstring(String s) { HashMap<Character, Integer> map = new HashMap<>(); int maxLen = 0; int left = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); if (map.containsKey(c)) { left = Math.max(map.get(c) + 1, left); } map.put(c, right); maxLen = Math.max(maxLen, right - left + 1); } return maxLen; }}
在这个解法中,我们利用哈希表来降低时间复杂度,使得每个字符只需要被访问一次,从而将时间复杂度降低到O(n)。
解法 4:使用数组作为简易哈希表
如果字符集较小,比如只有ASCII字符,我们可以使用一个整数数组代替哈希表来存储字符的索引,从而进一步提高效率。
public class Solution { public int lengthOfLongestSubstring(String s) { int[] index = new int[128]; // 假设字符集为ASCII int maxLen = 0; for (int right = 0, left = 0; right < s.length(); right++) { char c = s.charAt(right); left = Math.max(index[c], left); maxLen = Math.max(maxLen, right - left + 1); index[c] = right + 1; // 更新字符的索引位置 } return maxLen; }}
在这个解法中,数组 index 用来存储每个字符最后一次出现的位置的下一个位置,这样可以直接跳过重复的字符。
所有这些方法中,滑动窗口和动态规划+哈希表是最常用且效率最高的,尤其是在处理大型数据或者字符集较大的情况下。
标签: #最长子串动态规划