华能电子商务平台_陕西省建设网一体化平台_销售_推广哪个平台好

文章目录

直接刷题链接直达
无重复字符的最长子串
给定一个数，删除K位得到最小值
至多包含 K 个不同字符的最长子串
字符串的排列
至少有K个重复字符的最长子串

直接刷题链接直达

如何找出一个字符串中的最大不重复子串

3. 无重复字符的最长子串

给定一个数，删除K位得到最小值

402. 移掉K位数字

至多包含 K 个不同字符的最长子串

340. 至多包含 K 个不同字符的最长子串

字符串的排列

面试题38. 字符串的排列
46. 全排列（相同思路）

至少有K个重复字符的最长子串

395. 至少有K个重复字符的最长子串

无重复字符的最长子串

题目： 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

思路：

滑动窗口 + 哈希表（Map）解决问题
start 只向前移动【start = Math.max(start, map.get(ch) + 1)】，保证 O(n) 复杂度
考虑边界情况（例如 “”, “bbbbb”, “abcd”）

import java.util.HashMap;
import java.util.Map;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 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

关键点：

局部最优选择 -> 全局最优：
尽量让前面的数字小，所以遇到递增序列时，删除较大的数字。
使用单调栈：
维护一个单调递增的栈，遇到比栈顶小的数字，就移除栈顶（减少较大的数字）。
去除前导 0：
处理 000123 这样的情况，返回 “123” 而不是 “000123”。

思路：
使用 Stack<Character> 模拟递增序列，遍历 num：

遇到比栈顶小的数字，就移除栈顶（最多 k 次）。
所有数字入栈后，如果 k > 0，继续从栈顶移除剩余 k 个数字。
去除前导 0，避免 “000123” 这种情况。

import java.util.Stack;
class Solution {public String removeKdigits(String num, int k) {// 单调栈// （小->大）进栈，保持栈递增 高位越小越好if (num == null || num.length() <= k) return "0";Stack<Integer> stack = new Stack<>();for (int i = 0; i < num.length(); i++) {char ch = num.charAt(i);while (!stack.isEmpty() && k>0 && ch < num.charAt(stack.peek())) {stack.pop();k--;}stack.push(i);} while ( k>0) {stack.pop();k--;}// 去掉前导0StringBuilder sb = new StringBuilder();while(!stack.isEmpty()) {sb.append(num.charAt(stack.pop()));}sb.reverse();while(!sb.isEmpty() && sb.charAt(0) == '0') {sb.deleteCharAt(0);}return sb.isEmpty() ? "0":sb.toString();}
}

至多包含 K 个不同字符的最长子串

题目描述 ：给定一个字符串 s 和一个整数 k，找出最多包含 k 个不同字符的最长子串的长度。

解法： 滑动窗口 + 哈希表
核心思路：

维护一个滑动窗口 [left, right]，窗口内的子串最多包含 k 个不同字符。
用 HashMap<Character, Integer> 统计窗口内字符出现的次数：
当窗口内字符种类 ≤ k：扩大窗口 right++。
当窗口内字符种类 > k：缩小窗口 left++，直到字符种类恢复到 k。
记录窗口的最大长度。

import java.util.HashMap;
import java.util.Map;class Solution {public int lengthOfLongestSubstringKDistinct(String s, int k) {if (s.length() == 0 || k == 0) return 0;Map<Character, Integer> freqMap = new HashMap<>();int left = 0, maxLen = 0;for (int right = 0; right < s.length(); right++) {char ch = s.charAt(right);freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);// 当窗口内的不同字符数超过 k，收缩左指针while (freqMap.size() > k) {char leftChar = s.charAt(left);freqMap.put(leftChar, freqMap.get(leftChar) - 1);if (freqMap.get(leftChar) == 0) {freqMap.remove(leftChar);}left++; // 缩小窗口}// 更新最大长度maxLen = Math.max(maxLen, right - left + 1);}return maxLen;}
}

字符串的排列

题目： 某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的全部排列方式。

返回结果无顺序要求，但不能含有重复的元素。

class Solution {Set<String> ans = new HashSet<>();public String[] goodsOrder(String goods) {dfs(goods, new boolean[goods.length()], new StringBuilder());return ans.toArray(new String[0]);   }public void dfs(String goods, boolean[] used,StringBuilder res) {// 终止if (res.length() == goods.length()) {ans.add(res.toString());return;}//遍历for (int i = 0; i < goods.length(); i++) {if (!used[i]) {used[i] = true;res.append(goods.charAt(i));dfs(goods, used, res);// 回溯used[i] = false;res.deleteCharAt(res.length() - 1);}}}}

给定一个不含重复数字的数组 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。