代码随想录算法训练营Day02 | LeetCode977 有序数组的平方、LeetCode209 长度最小的子数组、LeetCode59 螺旋矩阵II

今日学习的视频和文章

代码随想录有序数组的平方
代码随想录长度最小的子数组
代码随想录螺旋矩阵
@YouLookDeliciousC 的题解：54. 螺旋矩阵 - 力扣（Leetcode）

LeetCode977 有序数组的平方

977. 有序数组的平方 - 力扣（Leetcode）

初见题目的想法

一开始我想的是设置一个left指针和一个right指针，从数组“中间”开始向两边比较。这个逻辑是错误的，应该是找到平方值最小的那个元素的位置作为双指针的起始位置，而不是取数组的“中间”。
那么，应该遍历一遍数组，找到合适的起始位置。变量寻找合适的起始位置的代码如下

int n = nums.size();
vector<int> res;

int start = 0;
int curPowMin = pow(nums[start], 2);
for (int i = 1; i < n; i++) {
    if (pow(nums[i], 2) < curPowMin) {
        curPowMin = pow(nums[i], 2);
        start = i;
    }
}
int left = start;
int right = start + 1;

找到合适的起始位置后，用left和right分别向左和向右取数组元素，比较平方值，将平方值较小的元素放入答案数组中。

while (0 <= left || right < n) {
    int powLeft = 0 <= left ? pow(nums[left], 2) : INT_MAX;
    int powRight = right < n ? pow(nums[right], 2) : INT_MAX;
    if (powLeft < powRight) {
        res.push_back(powLeft);
        left--;
    }
    else {
        res.push_back(powRight);
        right++;
    }
}

完整题解代码如下：

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> res;

    int start = 0;
    int curPowMin = pow(nums[start], 2);
    for (int i = 1; i < n; i++) {
        if (pow(nums[i], 2) < curPowMin) {
            curPowMin = pow(nums[i], 2);
            start = i;
        }
    }
    int left = start;
    int right = start + 1;

    while (0 <= left || right < n) {
        int powLeft = 0 <= left ? pow(nums[left], 2) : INT_MAX;//三目表达式防止下标越界
        int powRight = right < n ? pow(nums[right], 2) : INT_MAX;
        if (powLeft < powRight) {
            res.push_back(powLeft);
            left--;
        }
        else {
            res.push_back(powRight);
            right++;
        }
    }

    return res;
}

分别遍历了两次数组，时间复杂度应为O(n)。

看了代码随想录讲解后自己的一些体会

以前写题的时候也看过代码随想录的讲解，感觉比大学课堂里的讲解清楚很多。最近考研复习也在复习高数，所以联想到了二次函数的图像，最小的平方值相对来说在数组的“中间”，最大的平方值相对来说在数组的“两边”。既然要比较“两边”谁大谁小，自然就想到了双指针来向两边取元素。

不过我自己写的方法和代码随想录里的比起来还是不够简洁，我的方法里“找起始位置“这一步，其实是没有必要的。只需要让left从最左边开始，right从最右边开始，将平方值较大的数，从答案数组的最大下标向最小下标开始填充就可以了。

改良后的题解代码如下，甚至可以用三目表达式一条语句搞定。

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    for (int l = 0, r = n - 1, k = r; l <= r; ) {
        res[k--] = pow(nums[l], 2) > pow(nums[r], 2) ? 
                pow(nums[l++], 2) : pow(nums[r--], 2);
    }
    return res;
}

LeetCode209 长度最小的子数组

209. 长度最小的子数组 - 力扣（Leetcode）

初见题目时的想法
- 用left保存子数组在原数组中的起始下标，用right保存子数组在原数组中的结束下标。
- 让right先向右移动，如果出现了[left, right]的子数组的元素之和大于等于target，就让left向右移动，然后让right继续向右移动，继续寻找元素之和大于等于target的连续子数组。
- 然后我就在边界条件的调试上卡了很久，最后还是直接看讲解了。
看了讲解之后的体会：
- 外层循环的边界条件一定是right移动到右边界，如果是left移动到右边界的话就和暴力解法没有区别了。我自己做题的时候一直没有明确这一点，还在考虑left == right且right移动到右边界的情况，实际上这和滑动窗口的思想就矛盾了。

完整题解代码如下

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    int res = INT_MAX;

    int l = 0;
    int r = 0;
    int sum = 0;
    while (r < n) {
        sum += nums[r];
        while (sum >= target) {
            res = min(res, r - l + 1);
            sum -= nums[l++];
        }
        r++;
    }

    return res == INT_MAX ? 0 : res;
}

这题卡了比较久，还是要常回头看，并且多练类似思想的题目。
另外还闹了个乌龙，这题是在外面听讲座的时候做的，读题目时，电脑开了节电模式，没看清要求是”大于等于 target“而不是”等于 target“。这种细节问题也是要注意的，如果代码逻辑对了，但是还是不能AC，那可能就要看看自己是不是看错题目了……

LeetCode59 螺旋矩阵II

59. 螺旋矩阵 II - 力扣（Leetcode）

初见题目时的想法
- 这道题目以前写过类似的，而且看到了一个思路非常简洁清晰的题解，其中“移动边界”来操作螺旋的思想令我印象深刻。
- 54. 螺旋矩阵 - 力扣（Leetcode）
- @YouLookDeliciousC 的题解：54. 螺旋矩阵 - 力扣（Leetcode）

按照循环不变量原则，我在这里记录一下自己的体会：

首先是如何定义螺旋，代码随想录里是这样定义的（如图）：

image.png
每条边都是一个左闭右开区间，对于方阵而言，这是非常清晰、明确的“螺旋”的定义。但是我在写 LeetCode54 题时，继续按照这个定义去处理“螺旋”，就碰到了很多边界条件的问题。
因为 LeetCode54 并没有限制矩阵是方阵，按照左闭右开区间的定义，在处理只有一行或者一列的矩阵的时候，就会出现一些奇怪的情况，因为左闭右开区间，在矩阵只剩一行或一列的还没被访问的时候，就有可能出现因为区间右边不能取等号而遗漏元素的情况。
以下是我磕磕绊绊修修补补才通过的 LeetCode54 的代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        int rowNum = matrix.size();
        int colNum = matrix[0].size();
        int sumNum = rowNum * colNum;
        int x = 0;
        int y = 0;
        int loop = rowNum / 2;
        int count = 1;
        while(count <= loop) {
            for (; x < colNum - count; x++) {
                result.push_back(matrix[y][x]);
                if(result.size() == sumNum) return result;
            }
            
            for (; y < rowNum - count; y++) {
                result.push_back(matrix[y][x]);
                if(result.size() == sumNum) return result;
            }
            if(result.size() == sumNum) return result;
            
            for (; x >= count; x--) {
                result.push_back(matrix[y][x]);
                if(result.size() == sumNum) return result;
            }
            
            for (; y >= count; y--) {
                result.push_back(matrix[y][x]);
                if(result.size() == sumNum) return result;
            }
            if(result.size() == sumNum) return result;
                        
            count++;
            x++;
            y++;
        }

        if (rowNum <= colNum) {
            for (; x <= colNum - count; x++) {
                result.push_back(matrix[y][x]);
                if(result.size() == sumNum) return result;
            }
        }

        if (rowNum > colNum) {
            for (; y <= rowNum - count; y++) {
                result.push_back(matrix[y][x]);
                if(result.size() == sumNum) return result;
            }
        }

        return result;
    }
};

所以，在坚持循环不变量原则的同时，如何找或者说如何去定义循环不变量也影响我们如何去写代码。如果我们这样去定义“螺旋”，所有区间都取闭区间，就可以避免一些由于开区间而导致的边界条件判断。
1. 从左到右访问完矩阵的第一行，然后重新定义上边界，体现在代码上就是矩阵的“上边界”+1。
2. 判断上下边界是否交错即（上边界 > 下边界）。
3. 从上到下访问完矩阵的最后一列，然后重新定义右边界，体现在代码上就是矩阵的“右边界”-1。
4. 判断左右边界是否交错即（左边界 > 右边界）。
5. 从右到左访问完矩阵的最后一行，然后重新定义下边界，体现在代码上就是矩阵的“下边界”-1。
6. 判断左右边界是否交错即（左边界 > 右边界）。
7. 从下到上访问完矩阵的第一列，然后重新定义左边界，体现在代码上就是矩阵的“左边界”+1。
8. 判断上下边界是否交错即（上边界 > 下边界）。
9. 不断重复以上步骤，直到左右边界交错或者上下边界交错。
为什么这样做可以所有的区间都只用闭区间来定义“螺旋”呢？按照之前提到左闭右开的定义，我们对于“螺旋”的定义是静态的，没有考虑每访问一条边之后矩阵的变化。而按照 @YouLookDeliciousC 的方法，对于“螺旋”的定义是动态的，考虑了每访问一条边之后矩阵的变化，从而能只用闭区间来定义“螺旋”。

IMG_20230406_210212.jpg

LeetCode59 完整的题解代码如下：

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n, vector<int>(n));
    int top = 0;
    int bottom = n - 1;
    int left = 0;
    int right = n - 1;

    int count = 1;
    while (count <= n * n) {
        for (int x = left, y = top; x <= right; x++) {
            res[y][x] = count++; 
        }
        if (++top > bottom) break;

        for (int x = right, y = top; y <= bottom; y++) {
            res[y][x] = count++;
        }
        if (--right < left) break;

        for (int x = right, y = bottom; x >= left; x--) {
            res[y][x] = count++;
        }
        if (--bottom < top) break;

        for (int x = left, y = bottom; y >= top; y--) {
            res[y][x] = count++;
        }
        if (++left > right) break;
    }

    return res;
}

代码随想录算法训练营Day02 | LeetCode977 有序数组的平方、LeetCode209 长度最小的子数组、LeetCode59 螺旋矩阵II

今日学习的视频和文章

LeetCode977 有序数组的平方

LeetCode209 长度最小的子数组

LeetCode59 螺旋矩阵II

推荐阅读更多精彩内容