文章目录
- 直接刷题链接直达
- 如何找出一个字符串中的最大不重复子串
- 给定一个数，删除K位得到最大值
- 字符串的排列
- 至少有K个重复字符的最长子串
直接刷题链接直达
- 如何找出一个字符串中的最大不重复子串
- 滑动窗口 --> 滑动窗口直到最后一个元素，每当碰到重复时（可用一个Map记录，表示字母和位置），左指针往后走至当前位置，每轮都进行比较，取最大长度。 / 时间复杂度 --> O(n)
- 3. 无重复字符的最长子串
- 给定一个数，删除K位得到最大值
- 单调栈
- 402. 移掉K位数字
- 至多包含 K 个不同字符的最长子串
- 340. 至多包含 K 个不同字符的最长子串
- 字符串的排列
- 深度优先搜索（DFS） + 剪枝
- 理解递归的构造过程 --> 每次固定一个字符，继续处理剩余字符
- 处理后还原交换（保证所有可能都被遍历到）
- 面试题38. 字符串的排列
- 46. 全排列 （相同思路）
- 至少有K个重复字符的最长子串
- 分治法，递归求解
- 用一个map计数，一个set存储不应该包含的字母（即 count < k）
- 双指针遍历字符串，一旦找到需要剔除的字符，判断该字符左右两边满足条件的最长子串，比较返回较大值
- 395. 至少有K个重复字符的最长子串
如何找出一个字符串中的最大不重复子串
题目： 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
class Solution {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>(); // 存储字符和索引int maxLen = 0;int start = 0; // 滑动窗口左边界for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);// 如果字符重复，移动左边界（要取 `Math.max` 以保证 `start` 只向前移动）if (map.containsKey(ch)) {start = Math.max(start, map.get(ch) + 1);}// 更新最大长度maxLen = Math.max(maxLen, i - start + 1);// 记录当前字符的索引map.put(ch, i);}return maxLen;}}
给定一个数，删除K位得到最大值
题目： 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
class Solution {public String removeKdigits(String num, int k) {if (num == null || num.length() <= k) return "0";// 单调栈 维持一个单调递增的栈Stack<Character> stack = new Stack<>();for (int i = 0; i < num.length(); i++) {char ch = num.charAt(i);while (!stack.isEmpty() && k > 0 && stack.peek() > ch ) {stack.pop();k--;}stack.push(ch);}while (k > 0) {stack.pop();k--;}Collections.reverse(stack);StringBuilder sb = new StringBuilder();while (!stack.isEmpty() && stack.peek() == '0') {stack.pop();}while (!stack.isEmpty()) {sb.append(stack.pop());}return sb.toString().length() == 0 ? "0":sb.toString();}
}
字符串的排列
某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。
返回结果 无顺序要求，但不能含有重复的元素。
class Solution {Set<String> ans;public String[] goodsOrder(String goods) {ans = new HashSet<>();boolean[] used = new boolean[goods.length()];dfs(goods, new StringBuilder(), used);return ans.toArray(new String[0]);}public void dfs(String goods, StringBuilder path, boolean[] used) {if (path.length() == goods.length()) {ans.add(path.toString());return;}for (int i = 0; i < goods.length(); i++) {if (!used[i]) {used[i] = true;path.append(goods.charAt(i));dfs(goods, path, used);path.deleteCharAt(path.length() - 1);used[i] = false;}}}}
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {Set<List<Integer>> ans = new HashSet<>();public List<List<Integer>> permute(int[] nums) {dfs(new ArrayList<>(), nums, new boolean[nums.length]);return new ArrayList<>(ans);}public void dfs(List<Integer> path, int[] nums, boolean[] used) {if (path.size() == nums.length) {ans.add(new ArrayList(path));return;}for (int i = 0; i < nums.length; i++) {if (!used[i]) {used[i] = true;path.add(nums[i]);dfs(path, nums, used);used[i] = false;path.remove(path.size() -1);}}}}
至少有K个重复字符的最长子串
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
如果不存在这样的子字符串，则返回 0。
思路：
-
统计字符出现次数（用 HashMap<Character, Integer>）。
-
找到不满足 k 次的字符（存入 Set）。
-
使用递归或分治法：
- 如果所有字符都 出现至少 k 次，返回整个字符串长度。
- 否则，把字符串按 不符合的字符 拆分，分别递归求解。
class Solution {public int longestSubstring(String s, int k) {return helper(s, k, 0, s.length()-1);}public int helper(String s, int k, int left, int right) {if (right - left + 1 < k) return 0;// 用一个map计数Map<Character, Integer> count = new HashMap<>();for (int i = left; i <= right; i++){char ch = s.charAt(i);count.put(ch, count.getOrDefault(ch, 0)+1);}// 找到 不满足 k 的字符 =》左右分治for (int i = left; i <= right; i++){if (count.get(s.charAt(i)) < k) {int next = i + 1;while (next <= right && count.get(s.charAt(next)) < k) {next++;}return Math.max(helper(s, k, left, i-1), helper(s, k, next, right));}}return right - left + 1;}
}