代码随想录算法训练营第二天 | 977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵Ⅱ

977. 有序数组的平方

题目链接：977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

文章讲解：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

思路

最直接的想法，把数组分为两个部分，小于零的部分以及大于等于零的部分，分别求平方，然后将小于零的子数组反转，最后将两个子数组归并。

看了卡哥的教程后，发现还可以采用双指针法。定义一个新数组result，和A数组一样大小，当前位置k指向result数组的终止位置。同时对于数组A，用两个指针i、j分别指向数组的起始位置和终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j];

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i];

C++实现

// 自己的实现思路
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> neg_parts, pos_parts;

        for(int i = 0;i<nums.size();i++){
            if(nums[i] < 0){
                neg_parts.emplace_back(nums[i] * nums[i]);
            }
            else{
                pos_parts.emplace_back(nums[i] * nums[i]);
            }
        }

        reverse(neg_parts.begin(), neg_parts.end());

        vector<int> results;

        int neg = 0, pos = 0;
        while(neg < neg_parts.size() && pos < pos_parts.size()){
            if(neg_parts[neg] < pos_parts[pos]){
                results.emplace_back(neg_parts[neg++]);
            }
            else{
                results.emplace_back(pos_parts[pos++]);
            }
        }

        while(neg < neg_parts.size()) results.emplace_back(neg_parts[neg++]);
        while(pos < pos_parts.size()) results.emplace_back(pos_parts[pos++]);
        return results;
    }
};

// 双指针法
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

        for(int i = 0;i<nums.size();i++){
            nums[i] = nums[i] * nums[i];
        }

        vector<int> result(nums.size(), 0);
        int i = 0, j = nums.size() - 1, k = result.size() - 1;

        while(i <= j){
            if(nums[i] < nums[j]){
                result[k--] = nums[j--];
            }
            else{
                // nums[i] >= nums[j]
                result[k--] = nums[i++];
            }
        }
        return result;
    }
};

209. 长度最小的子数组

题目链接：209.长度最小的子数组

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

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

文章讲解：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/BV1tZ4y1q7XE

思路

看到题目的第一个想法是，能够采用动态规划的方式？想了一下，递推公式不知道咋推，不大靠谱。

应该还是用双指针来解决。题目已经说明数组里都是正整数，那么可以定义一前一后两个指针i和j，当指针内的和小于target时，j++，当指针内的和大于target时，i++，指针内的和等于target时，记录下j - i + 1的值，然后再让j++。

看错了，题目条件是大于等于target，所以当指针内的和小于target时，j++，当指针内的和大于等于target时，记录当前j - i + 1的值，然后i++。

卡哥的文章讲解里说这是滑动数组，我觉得这里的滑动数组和双指针是一个东西。。

C++实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0, j = 0;
        int curr_sum = nums[i];
        int min_length = nums.size() + 1;

        while(j < nums.size()){

            if(curr_sum < target){
                j++;
                if(j >= nums.size()) break;
                curr_sum += nums[j];
            }
            else{
                min_length = min(min_length, j - i + 1);
                curr_sum -= nums[i];
                i++;
            }
        }
        return (min_length == nums.size() + 1) ? 0 : min_length;
    }
};

59. 螺旋矩阵Ⅱ

题目链接：59.螺旋矩阵Ⅱ

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

文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

思路

确定一个方向数组，按序存储右、下、左、上四个方向。按照当前的方向将数字元素填入数组，如果继续沿着当前方向会导致”撞墙“，即超过矩阵边界或者与已填入数字元素冲突，则根据方向数组改换方向。

C++实现

class Solution {
private:
    vector<pair<int,int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    bool isLegal(pair<int,int> curr, pair<int,int> dir, vector<vector<int>>& matrix){
        // 判断是否撞墙或冲突
        int n = matrix.size();
        int new_i = curr.first + dir.first, new_j = curr.second + dir.second;

        if(new_i < 0 || new_i >= n || new_j < 0 || new_j >= n) return false;
        if(matrix[new_i][new_j] != 0) return false;
        return true;
    }

public:
    vector<vector<int>> generateMatrix(int n) {
        int square_n = n * n;
        
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        pair<int,int> curr = {0, 0};
        int curr_dir = 0;

        for(int i = 1;i<=square_n;i++){
            matrix[curr.first][curr.second] = i;

            int step = 0;
            while(!isLegal(curr, dirs[curr_dir], matrix) && step < 4){
                curr_dir = (curr_dir + 1) % 4;
                step++;
            }
            curr.first += dirs[curr_dir].first;
            curr.second += dirs[curr_dir].second;
        }

        return matrix;
    }
};

总结

对数组部分做一个小总结。

数组是存放在连续内存空间上的相同类型数据的集合。数组是一种非常常用的数据结构，插入和删除的时间复杂度都为O(n)，查找的时间复杂度为O(1)。

这两天刷的数组题目主要包括这几个部分：二分、双指针、滑动数组、模拟。

二分题目在处理时需要注意区间的定义，有许多题目是基础二分的变体，需要多刷题把握。

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

滑动窗口在处理时需要注意如何移动窗口的起始位置，滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置，从而将O(n^2)的暴力解法降为O(n)。

对于模拟而言，我认为还是需要多练。