977.有序数组的平方
思路
-
最直观的解法：
暴力解题，每个数先平方，然后再快速排序，时间复杂度为 O(n + nlog n)
-
规律：
该数组本身是非递减顺序，在平方后其实依然有顺序，左右两边大中间小。
双指针
利用观察到的规律，可以利用双指针在数组的两头寻找最大的元素，将其放到新创建的数组中
解法：
-
定义两个指针，i 指向起始位置，j 指向终止位置
-
定义一个新数组 result，长度和 nums 一样，让 k 指向 result数组的终止位置
-
循环条件为 i <= j ，保证最后一个元素能够被处理移至新数组
-
若
nums[i] * nums[i] > nums[j] * nums[j]那么result[k--] = nums[i] * nums[i++]若
nums[i] * nums[i] <= nums[j] * nums[j]那么result[k--] = nums[j] * nums[j--]
代码实现
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int i = 0;
int j = nums.length - 1;
int k = nums.length - 1;
while (i <= j) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
result[k--] = nums[i] * nums[i];
i++;
} else {
result[k--] = nums[j] * nums[j];
j--;
}
}
return result;
}
}
209.长度最小的子数组
滑动窗口
- 滑动窗口：就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。
滑动窗口其实也可以理解为双指针的一种，只不过这种解法更像是一个窗口在移动，所以叫滑动窗口更合适一点
本题中实现滑动窗口，主要是确定如下三点：
-
窗口内是什么？
-
如何移动窗口的结束位置（快指针）？
-
如何移动窗口的起始位置（慢指针）？
解决思路：
- 窗口：满足 其和 >= target 的长度最小的连续子数组
- 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里面的索引
- 窗口的起始位置如何移动：如果窗口内的值 >= target 了，窗口的起始位置就要向前移动直到窗口内的值 < target
while (sum >= target) {
tmp = fast - slow + 1;
min = Math.min(min, tmp);
sum -= nums[slow++];
}
如何动态调节滑动窗口的起始位置是本题的精华
代码实现
时间复杂度：O(n) 2 * n
空间复杂度：O(1)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int min = Integer.MAX_VALUE;
int slow = 0;
int sum = 0;
int tmp = 0;
for (int fast = 0;fast < nums.length;fast++) {
sum += nums[fast];
while (sum >= target) {
tmp = fast - slow + 1;
min = Math.min(min, tmp);
sum -= nums[slow++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
59.螺旋矩阵 Ⅱ
思路
-
难点：本题不涉及什么算法，但十分考察过程，对于每一圈的边界不好处理
-
解决方式：坚持 循环不变量原则 ，类似 二分法 中坚持 左闭右开
-
过程：由外向内地循环每一圈 ，下面四个循环的边界都坚持左闭右开，这样可以避免重复填充或露填充
- 左上到右上
[不变][递增] - 右上到右下
[递增][不变] - 右下到左下
[不变][递减] - 左下到左上
[递减][不变]
- 左上到右上
这里引用carl哥的图来解释说明：（图画的贼清晰）
这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
代码实现
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int count = 1; // 递增计数
int start = 0; // 每一圈的起始位置,每圈从(start, start)开始
int i,j; // 方便写下面四个循环
for (int loop = 1;loop <= n / 2;loop++) {
// 模拟上侧从左到右
for (j = start;j < n - loop;j++) {
result[start][j] = count++;
}
// 模拟右侧从上到下
for (i = start;i < n - loop;i++) {
result[i][j] = count++;
}
// 模拟下侧从右到左
for (;j >= loop;j--) {
result[i][j] = count++;
}
// 模拟左侧从下到上
for (;i >= loop;i--) {
result[i][j] = count++;
}
start++;
}
// 如果n为奇数，需要单独给最中间的位置赋值
if (n % 2 == 1) {
result[start][start] = count;
}
return result;
}
}