代码随想录

LeetCode 977 有序数组的平方

carl

数组 #双指针

思路

• 利用有序条件，新的大值在旧数组的两端产生，因此考虑相向指针

细节

• 涉及3个指针，注意每个指针的更新时机

LeetCode 209 长度最小的子数组

carl

滑动窗口 #数组 #双指针

思路

• 求解连续变化区间的最值，适合用滑动窗口
• 滑动窗口快慢指针的变化条件，一个负责增大，一个负责减少

细节

• 使用下标间距计数，单独定义count反而容易出错，因为要多更新一个变量

LeetCode 59 螺旋矩阵 II

carl

数组 #二维数组 #循环不变量 #区间

思路

• 循环不变量思想确实能避免出错，很好用
• 找规律，上下左右起始下标与边长和深度的关系
• 用边长写循环，每次减2，只要边长大于0就循环，深度就是(n - side) / 2，一定除得尽
• 胜过用深度写循环，因为边长奇偶未知导致要考虑边长计算时，整型除法取整是否正确

细节

• 循环不变量，很受用，让所有区间的左右开闭保持一致
  ![[Pasted image 20221013221913.png]]

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
		// -------------------------------------------- 细节1 二维vector如何初始化
        vector<vector<int>> matrix(n, (vector<int>(n, 0)));

        int count = 1;
        for(int side = n; side > 0; side -= 2){ // ---- 细节2 使用边长作循环
            int depth = (n - side) / 2;
            if(side == 1){ // ------------------------- 边界条件
                matrix[depth][depth] = count;
                break;
            }

            // up
            for(int i = 0; i < side - 1; ++i){
                matrix[depth][depth + i] = count++;
            }

            // right
            for(int i = 0; i < side - 1; ++i){
                matrix[depth + i][depth + side - 1] = count++;
            }

            // down
            for(int i = 0; i < side - 1; ++i){
                matrix[depth + side - 1][depth + side - 1 - i] = count++;
            }

            // left
            for(int i = 0; i < side - 1; ++i){
                matrix[depth + side - 1 - i][depth] = count++;
            }
        }
        return matrix;
    }
};