Day2 | 977.有序数组的平方 | 209.长度最小的子数组 | 59.螺旋矩阵II

Day2 | 977.有序数组的平方 | 209.长度最小的子数组 | 59.螺旋矩阵II

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路：双指针，可以从最大的开始确定

理解：之所以可以用双指针，必须从大的开始添加到结果中，因为给的数组就是 非递减顺序的

func sortedSquares(nums []int) []int {
    // 思路：双指针，可以从最大的开始确定
    size := len(nums) 
    if size == 0 {
        return nil
    }
    res := make([]int, size)
    i, j := 0, size - 1
    k := size - 1
    for i <= j {
        if nums[i] * nums[i] >= nums[j] * nums[j] {
            res[k] = nums[i] * nums[i]
            i ++
        }else {
            res[k] = nums[j] * nums[j]
            j --
        }
        k --
    }
    return res
}

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res(nums.size(), 0);
        int left = 0, right = nums.size() - 1, k = right;
        while(left <= right) {
            if(nums[right] * nums[right] > nums[left] * nums[left]) {
                res[k--] = nums[right] * nums[right];
                right --;
            }else {
                res[k --] = nums[left] * nums[left];
                left ++;
            }
        }
        return res;
    }
};

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路：维护一个滑动窗口，里面的和小于target就加入元素，否则从前面踢出

满足条件的所有取最小值

理解：因为是连续子数组，所以不需要排序。INT32_MAX最大值

func minSubArrayLen(target int, nums []int) int {
    // 思路：维护一个滑动窗口，里面的和小于target就加入元素，否则从前面踢出
    // 满足条件的所有取最小值
    res := math.MaxInt64
    size := len(nums)
    if size == 0 {
        return 0
    }
    sum := 0
    i := 0
    for j := 0; j < size; j ++{
        // 不管怎样先加入进去
        sum += nums[j]
        for sum >= target {
            res = min(res, j - i + 1)
            sum -= nums[i]
            i ++
        }
    }
    if res == math.MaxInt64 {
        return 0
    }
    return res

}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int slow = 0, sum = 0, res = INT32_MAX;
        for(int fast = 0; fast < nums.size(); fast ++ ) {
            sum += nums[fast];
            // 循环
            while(sum >= target) {
                res = min(res, fast - slow + 1);
                sum -= nums[slow];
                slow ++;
            }
        }
        return res == INT32_MAX ? 0 : res;
    }
};

举一反三：239. 滑动窗口最大值

func maxSlidingWindow(nums []int, k int) []int {
    // 思路：维护一个单调递减队列，这样每次取最大就是队头元素
    // 队头元素出队列取决于是否在窗口内
    res := make([]int, 0)
    que := make([]int, 0)
    for i := 0; i < len(nums); i ++ {
        if len(que) != 0 && i - que[0] >= k {
            que = que[1:]
        }
        // 最后一个元素比较
        for len(que) != 0 && nums[i] >= nums[que[len(que) - 1]] {
            que = que[:len(que) - 1]
        }
        que = append(que, i)
        // 判断是否形成窗口
        if i + 1 >= k {
            res = append(res, nums[que[0]])
        }
    }
    return res
}

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

func generateMatrix(n int) [][]int {
    // 思路：填充矩阵每个位置的值，通过方向数组来控制移动
    res := make([][]int, n)
    for i := 0; i < n; i ++ {
        res[i] = make([]int, n)
    }
    dx := [4]int{0, 1, 0, -1}
    dy := [4]int{1, 0, -1, 0}
    i, j, d := 0, 0, 0
    for k := 1; k <= n * n; k ++ {
        res[i][j] = k
        // 下一个填充的位置
        a := i + dx[d]
        b := j + dy[d]
        // 处理越界 三种情况
        if a >= n || b >= n || a < 0 || b < 0 || res[a][b] != 0 {
            d = (d + 1) % 4
            a = i + dx[d]
            b = j + dy[d]
        }
        i, j = a, b
    }
    return res
}

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        // 当前位置
        int x = 0, y = 0;
        // 方向数组
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
        // 使用数组
        for(int k = 1, x = 0, y = 0, d = 0; k <= n * n; k ++) {
            res[x][y] = k;
            // 下一个位置的坐标
            int a = x + dx[d], b = y + dy[d];
            // 改变方向
            if(a < 0 || a >= n || b < 0 || b >= n || res[a][b]) {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

数组总结

数组用到的算法主要是二分，双指针，快慢指针，滑动窗口，单调队列单调栈，方向数组。

还有就是通过 模拟的方法解决

寻找有序数组的指定值用到了二分和双指针方法，删除数组的元素用到了双指针的方法，滑动窗口用在需要对一个区间进行处理的情况，最后在矩阵中学会了使用方向数组，这也算是一个小技巧