yub’s Algorithmic Adventures_Day3

有序数组的平方

link：977. 有序数组的平方 - 力扣（LeetCode）
非递减顺序
一个数列中的元素从左到右依次不减，或者说不降序排列.
比如：1233445，12345.

思路分析

如果看到数组能条件反射到双指针那已经是win了.
根据题意平方之后的数一定在数组的两端.两个指针一首一尾，从后往前更新数组.

class Solution {public int[] sortedSquares(int[] nums) {//非递减数组可得最大值平方后会出现在数组两头int left = 0;int right = nums.length - 1;int[] result = new int[nums.length];int index = result.length - 1 ;while(left <= right) {if(nums[left]*nums[left] > nums[right]*nums[right]) {result[index--] = nums[left] * nums[left++];// left++;}else{result[index--] = nums[right] * nums[right--];//right--;}}return result;}
}

长度最小的子数组

link：209. 长度最小的子数组 - 力扣（LeetCode）

双指针变形——滑动窗口
其实也可以理解成给入队的队列一个给定的大小变成窗口，先入队元素，然后和target进行比较，大于等于target就出队先进的元素，再进新元素并且标记好原来大于等于target的数组长度.

class Solution {public int minSubArrayLen(int target, int[] nums) {int begin = 0;//起始位置int sum = 0;//滑动窗口值总和int result = Integer.MAX_VALUE;//定义最大值 遍历不出错for(int end = 0; end < nums.length;end++) {sum += nums[end];while(sum >= target) {result = Math.min(result, end - begin + 1);//最小长度sum -= nums[begin++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}

关键点：如何移动起始位置
如果循环中的标记位在起始位置，起始位置和终止位置都需要移动一遍和暴力解法无差别，所以我们的标记位一定是终止位.

螺旋矩阵 II

link：59. 螺旋矩阵 II - 力扣（LeetCode）
奇怪的代码掌控力… 主要问题在边界处理

顺序解决

按照本来的逻辑

class Solution {public int[][] generateMatrix(int n) {int l = 0,r = n - 1,t = 0,b = n-1;int[][] result = new int[n][n];int num = 1;int tar = n * n;while(num <= tar) {//第一行开始for(int i = l;i <= r;i++){result[t][i] = num++;}t++;for(int i = t; i <= b; i++){result[i][r] = num++;}r--;for(int i = r; i >=l; i--){result[b][i] = num++;}b--;for(int i = b;i >= t;i--) {result[i][l] = num++;}l++;}return result;}
}

改编版本

class Solution {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;}
}

Tips

1.遇到有序数组考虑二分法.
2.双指针（找准循环不变量中的不变量）.
3.求连续子数组的总和可用滑动窗口解决.