代码随想录-算法训练营day02【滑动窗口、螺旋矩阵】

专栏笔记：https://blog.csdn.net/weixin_44949135/category_10335122.html

https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG?u=c71ed002e4554fee8c262b2a4a4935d8977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II ，总结 建议大家先独立做题，然后看视频讲解，然后看文章讲解，然后在重新做一遍题，把题目AC，最后整理成今日当天的博客拓展题目可以先不做详细布置977.有序数组的平方 题目建议： 本题关键在于理解双指针思想 题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep 209.长度最小的子数组题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。  拓展题目可以先不做。 题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE59.螺旋矩阵II题目建议：  本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。 题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/总结 题目建议：希望大家 也做一个自己 对数组专题的总结文章链接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html

0977_有序数组的平方【双指针】

0209_长度最小的子数组【滑动窗口】

0904_水果成篮

0076_最小覆盖子串

0059_螺旋矩阵2

0054_螺旋矩阵

LCR 146. 螺旋遍历二维数组

0977_有序数组的平方【双指针】

class Solution {public int[] sortedSquares(int[] nums) {for (int i = 0; i < nums.length; i++) {nums[i] = nums[i] * nums[i];}Arrays.sort(nums);return nums;}public int[] sortedSquares2(int[] nums) {//双指针法int left = 0, right = nums.length - 1, index = nums.length - 1;int res[] = new int[nums.length];while (left <= right) {if (Math.abs(nums[left]) > Math.abs(nums[right])) {res[index--] = nums[left] * nums[left];left++;} else {res[index--] = nums[right] * nums[right];right--;}}return res;}
}

0209_长度最小的子数组【滑动窗口】

class Solution {public int minSubArrayLen(int target, int[] nums) {//滑动窗口int sum = 0, index = 0, res = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {sum += nums[i];while (sum >= target) {//int len = i - index + 1;res = Math.min(res, i - index + 1);sum -= nums[index++];}}return res == -1 ? 0 : res;}public int minSubArrayLen2(int target, int[] nums) {//滑动窗口int result = Integer.MAX_VALUE;int sum = 0; // 滑动窗口数值之和int i = 0; // 滑动窗口起始位置int subLength = 0; // 滑动窗口的长度for (int j = 0; j < nums.length; j++) {sum += nums[j];//注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件while (sum >= target) {subLength = (j - i + 1); // 取子序列的长度result = result < subLength ? result : subLength;sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）}}//如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == Integer.MAX_VALUE ? 0 : result;}public int minSubArrayLen3(int s, int[] nums) {//滑动窗口int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= s) {result = Math.min(result, right - left + 1);sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}

0904_水果成篮

class Solution0904 {public int totalFruit(int[] fruits) {int n = fruits.length;Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();//创建一个空的哈希表int left = 0, ans = 0;for (int right = 0; right < n; ++right) {//把水果加入哈希表中，你可以这么看cnt.put(水果类型，水果个数)，key存储水果类型，而key对应的value存储对应的水果类型个数cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);//当哈希表中的键值大于2时，也就是水果类型大于2时，进入while循环while (cnt.size() > 2) {//从哈希表中减去一个key==fruits[left]类型的水果，当key==fruits[left]这种类型的水果数等于0时，删除这种类型水果cnt.put(fruits[left], cnt.get(fruits[left]) - 1);if (cnt.get(fruits[left]) == 0) {cnt.remove(fruits[left]);}++left;}ans = Math.max(ans, right - left + 1);}return ans;}
}

0076_最小覆盖子串

class Solution {Map<Character, Integer> ori = new HashMap<Character, Integer>();Map<Character, Integer> cnt = new HashMap<Character, Integer>();public String minWindow(String s, String t) {int tLen = t.length();for (int i = 0; i < tLen; i++) {char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = -1;int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;int sLen = s.length();while (r < sLen) {++r;if (r < sLen && ori.containsKey(s.charAt(r))) {cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);}while (check() && l <= r) {if (r - l + 1 < len) {len = r - l + 1;ansL = l;ansR = l + len;}if (ori.containsKey(s.charAt(l))) {cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);}++l;}}return ansL == -1 ? "" : s.substring(ansL, ansR);}public boolean check() {Iterator iter = ori.entrySet().iterator();while (iter.hasNext()) {Map.Entry entry = (Map.Entry) iter.next();Character key = (Character) entry.getKey();Integer val = (Integer) entry.getValue();if (cnt.getOrDefault(key, 0) < val) {return false;}}return true;}
}

0059_螺旋矩阵2

class Solution0059 {public int[][] generateMatrix(int n) {int loop = 0;//控制循环次数int[][] res = new int[n][n];int start = 0;//每次循环的开始点(start, start)int count = 1;//定义填充数字int i, j;while (loop++ < n / 2) {//判断边界后，loop从1开始//模拟上侧从左到右for (j = start; j < n - loop; j++) {res[start][j] = count++;}//模拟右侧从上到下for (i = start; i < n - loop; i++) {res[i][j] = count++;}//模拟下侧从右到左for (; j >= loop; j--) {res[i][j] = count++;}//模拟左侧从下到上for (; i >= loop; i--) {res[i][j] = count++;}start++;}if (n % 2 == 1) {res[start][start] = count;}return res;}
}

0054_螺旋矩阵

class Solution0054 {public List<Integer> spiralOrder(int[][] matrix) {int m = matrix.length, n = matrix[0].length;List<Integer> res = new ArrayList<>();int u = 0, d = m - 1, l = 0, r = n - 1;while (true) {for (int i = l; i <= r; i++) res.add(matrix[u][i]);if (++u > d) break;for (int i = u; i <= d; i++) res.add(matrix[i][r]);if (--r < l) break;for (int i = r; i >= l; i--) res.add(matrix[d][i]);if (--d < u) break;for (int i = d; i >= u; i--) res.add(matrix[i][l]);if (++l > r) break;}return res;}
}

LCR 146. 螺旋遍历二维数组

class Solution_LCR_0146 {public int[] spiralArray(int[][] array) {if (array == null || array.length == 0 || array[0].length == 0) {return new int[0];}int rows = array.length, columns = array[0].length;boolean[][] visited = new boolean[rows][columns];int total = rows * columns;int[] order = new int[total];int row = 0, column = 0;int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int directionIndex = 0;for (int i = 0; i < total; i++) {order[i] = array[row][column];visited[row][column] = true;int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {directionIndex = (directionIndex + 1) % 4;}row += directions[directionIndex][0];column += directions[directionIndex][1];}return order;}
}