吴江企业网站建设微信公众账号登录官网

滑动窗口问题

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;}}}
}