滑动窗口问题
76.最小覆盖子串
题目链接:76. 最小覆盖子串 - 力扣(LeetCode)
题目描述:
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
实现思路:
使用HashMap记录模板串t,中的字母分布数量。
在目标串s,中维护一个滑动窗口,并记录目标字符的数量,通过检测目标字符数与hashmap是否一致,判断当前窗口是否是有效窗口。
窗口的扩展:窗口向右扩展,收录一个字符。如果是目标字符,加入当前记录,并判断是否符合窗口收缩要求。不符合要求则继续扩展窗口。
窗口的收缩:1.当前窗口符合找到所有字符之后,并开始从左侧收缩,直到遇见了第一个不能舍去的有效字符。
代码实现:
class Solution {public String minWindow(String s, String t) {HashMap<Character, Integer> dict = new HashMap<>();HashMap<Character, Integer> map = new HashMap<>();char[] arrt = t.toCharArray();for (int i=0; i<arrt.length; i++) {dict.compute(arrt[i], (k,v) -> { return v == null ? 1 : v + 1;});map.compute(arrt[i], (k,v) -> {return 0;});}int left = 0, right = -1;int minLen = Integer.MAX_VALUE, ansl = -1, ansr = -1; char[] arrs = s.toCharArray();while (right < arrs.length - 1) {// 向右拓展窗口right++;char ch = arrs[right];if (!dict.containsKey(ch)) continue; // 过滤掉非目标字符map.compute(ch, (k,v) -> { return v + 1;});// 从左侧收缩窗口if (check(map,dict)) {while (left <= right) {char c = arrs[left];// 收缩过程中跳过普通字符if (!dict.containsKey(c)) { left++;continue;}// 跳过数量过多的目标字符if (map.get(c) > dict.get(c)) { map.compute(c, (k,v) -> {return v-1;});left++;}// 遇到了不能跳过的目标字符else {// 更新结果if (right - left + 1 < minLen) {ansl = left;ansr = right;minLen = right - left + 1;}break;}}// System.out.println("收缩完毕 " + map + result);}}return ansl == -1 ? "" : s.substring(ansl, ansr+1);}// 检查当前字符合集是否符合要求public boolean check(HashMap<Character, Integer> map, HashMap<Character, Integer> dict) {for (Map.Entry<Character, Integer> entry : map.entrySet()) {if (entry.getValue() < dict.get(entry.getKey())) return false; }return true;}
}
其他问题
54.螺旋矩阵
题目链接:54. 螺旋矩阵 - 力扣(LeetCode)
题目描述:
给你一个 m
行 n
列的矩阵 matrix
,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
实现思路:
模拟每一圈的打印模式,规定上下左右层的打印顺序和打印的数据长度。
当剩余的元素不能够组成一圈的时候,补充核心元素。
重点在于控制元素数量:
- 打印当前宽度-1个元素
- for (; i<colStart+rowWidth-1; i++)
- for (; j<rowStart+colWidtg-1; j++)
- 当某个维度剩余元素少于2个的时候,说明只剩下核心元素没有打印了
代码实现:
class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result = new LinkedList<>();// 上下的圈数int m = matrix[0].length; // 剩余的列int n = matrix.length; // 剩余的行int rowWidth = m, colWith = n;int rowStart = 0, colStart = 0,i = 0,j = 0;// 左闭右开区间while(rowWidth > 1 && colWith > 1) {int loop1 = rowWidth;int loop2 = colWith;i = colStart;j = rowStart;// 打印上层for (; i<colStart+loop1-1; i++) result.add(matrix[j][i]);// 打印右侧for (; j<rowStart+loop2-1; j++)result.add(matrix[j][i]);// 打印下侧for (; i>colStart; i--) result.add(matrix[j][i]);// 打印左侧for (; j>rowStart;j--) result.add(matrix[j][i]);rowWidth -= 2;colWith -= 2;rowStart++;colStart++;}// 填充中间剩余部分i = colStart;j = rowStart;;if (rowWidth == 1) { // 只剩下一列for (int ct=0;ct<colWith; ct++,j++) result.add(matrix[j][i]);}else if (colWith == 1) { // 只剩下一行for (int ct=0;ct<rowWidth; ct++,i++) result.add(matrix[j][i]); }return result;}
}
48.旋转图像
题目链接:48. 旋转图像 - 力扣(LeetCode)
题目描述:
给定一个 n × n 的二维矩阵 matrix
表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
实现思路:
翻转代理旋转,先水平反转,再对角反转。
对角线反转的代码其实很简单,但是我花了点时间才想明白。
代码实现:
class Solution {public void rotate(int[][] matrix) {int n = matrix.length;// 水平翻转for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < n; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - i - 1][j];matrix[n - i - 1][j] = temp;}}// 主对角线翻转for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}}
}