双指针(leetcode easy 977)、滑动窗口(leetcode medium 209)、模拟旋转前进(leetcode medium 59)

双指针

题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/

思路:

• 因题目所给数组为有序数组(有正有负), 所以平方后数值从大到小肯定是从数组两边向内收缩的趋势, 所以可以采用两个指针指向原数组两边, 并通过对比数组两边数字平方后大小(或者绝对值大小),取其中的更大值来填充结果数组的末尾.(时间复杂度O(n)、空间复杂度O(n)).

代码(java):

class Solution {
    public int[] sortedSquares(int[] nums) {
        int i = nums.length;
        int[] result = new int[i];
        int left = 0;
        int right = --i;
        while (i >= 0) {
            result[i--] = nums[left] * nums[left] > nums[right] * nums[right] ? nums[left] * nums[left++] : nums[right] * nums[right--];
        }
        return result;
    }
}

滑动窗口

题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/

思路:

• 因题目要求子数组在原数组中连续, 故而可以采用滑动窗口法, 窗口在数组内从左到右滑动(遍历数组). 当窗口内元素和小于target时: 窗口增大, 当窗口内元素和大于等于target时: 窗口缩小. 在滑动过程中记录最小窗口大小.(时间复杂度O(n), 空间复杂度O(1)).

注意事项:

• 循环条件的判断:
  1. 使用单层循环: 基础循环条件, 窗口右指针未到达数组最右侧. 特殊循环条件, 在右指针到达了最右侧的情况下, 如果窗口内元素和大于等于target, 需要继续进行循环移动左指针以缩小窗口继续寻找最小窗口(举个极端例子: 数组最后一个值大于等于target, 而此时窗口大小大于1).
  2. 使用 双层循环: 外循环用于扩大窗口, 内循环用于缩小窗口. 这种情况外循环只需要判断窗口右指针是否到达数组最右侧(外循环还有扩大窗口的作用), 内循环只需要判断窗口内元素和是否大于等于target, 满足条件则进行内循环缩小窗口.

代码(java):

//单层循环
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int slow = -1;
        int fast = -1;
        int minSize = nums.length + 1;
        int sum = 0;
        while (fast < nums.length - 1 || sum >= target) {
            if (sum < target) {
                sum += nums[++fast];
            } else {
                minSize = minSize < fast - slow ? minSize : fast - slow;
                sum -= nums[++slow];
            }
        }
        return minSize > nums.length ? 0 : minSize;
    }
}

//双层循环
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int size = nums.length + 1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= target) {
                size = size < i - left + 1 ? size : i - left + 1;
                sum -= nums[left++];
            }
        }
        return size == nums.length + 1 ? 0 : size;
    }
}

模拟旋转前进(暴力破解)

题目链接:https://leetcode.cn/problems/spiral-matrix-ii/

思路:

• 根据题目要求进行模拟旋转前进, 采用如下思路:
  1. 旋转填充数组的方向顺序为: →、↓、←、↑.
  2. 使用一个变量direction记录当前前进方向, 通过direction % 4判断当前方向. 结果0、1、2、3分别代表 →、↓、←、↑ 方向.
  3. 使用一个变量layer记录每个方向上已经填充的层数(因所有方向是依次增加一层).
  4. 转向条件(设置x、y初始值为0、0, x、y在填充当前位置后进行更新):
     · 向右时：x == n - 右层层数.
     · 向下时：y == n - 下层层数.
     · 向左时：x == 左层层数 - 1.
     · 向上时：y == 上层层数 - 1.

注意事项:

1. layer需要在向左前进完后增加, 因为接下来向上前进时在最开始向右前进时已经增加了一层.
2. 每次前进触底后, 需要更新当前x、y坐标.

代码(java):

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int direction = 0;
        int layer = 0;
        int x = 0;
        int y = 0;
        for (int i = 1; i <= n * n; i++) {
            switch (direction % 4) {//判断当前前进方向
                case 0:
                    result[y][x++] = i; // 填充数组
                    if (x == n - layer) { // 判断是否触底
                        // 切换转向后初始位置
                        x--;
                        y++;
                        // 转向
                        direction++;
                    }
                    break;
                case 1:
                    result[y++][x] = i;
                    if (y == n - layer) {
                        y--;
                        x--;
                        direction++;
                    }
                    break;
                case 2:
                    result[y][x--] = i;
                    if (x == layer - 1) {
                        x++;
                        y--;
                        direction++;
                        layer++;
                    }
                    break;
                case 3:
                    result[y--][x] = i;
                    if (y == layer - 1) {
                        y++;
                        x++;
                        direction++;
                    }
                    break;
            }
        }
        return result;
    }
}

注: 本方法稍显复杂, 我觉得算是暴力破解的办法, 推荐carl大佬的一种思路:https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html#%E6%80%9D%E8%B7%AF