day02 - 数组

zqh2023 / 2023-08-10 / 原文

977. 有序数组的平方

//双指针
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i = 0;
        int j = nums.size() - 1;
        int k = j;
        vector<int> result(nums.size(), 0);
        for(; i <= j; ){
            if(nums[i] * nums[i] < nums[j] * nums[j]){
                result[k--] = nums[j] * nums[j];
                j--;
            }else{
                result[k--] = nums[i] * nums[i];
                i++;
            }
        }
        return result;
    }
};

209. 长度最小的子数组

//滑动
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int min_len = INT32_MAX;
        int i = 0, sum = 0;
        for(int j=0; j< nums.size(); j++){
            sum += nums[j];
            while(sum >= target){
                int sub_len = j - i + 1;
                min_len = min(min_len, sub_len);
                sum -= nums[i++];
            }
        }
        return min_len == INT32_MAX? 0:min_len;
    }
};

59. 螺旋矩阵 II

//模拟
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int direction[4][2] = {
            {0, 1},//右
            {1, 0},//下
            {0, -1},//左
            {-1, 0}//上
        };

        int now_direction = 0;

        vector<vector<int>> result(n, vector<int>(n, 0));

        int x = 0, y = 0;
        result[x][y] = 1;
        for(int k = 2; k <= n*n; k++){
            int new_x = x + direction[now_direction][0];
            int new_y = y + direction[now_direction][1];
            cout << x << "," << y << endl;
            if(new_x >= n || new_x < 0 || new_y >=n || new_y < 0 || result[new_x][new_y] > 0){
                now_direction = (++now_direction)%4;//拐弯
                cout << "now_direction:" << now_direction << endl;
                k--;//回退
                continue;
            }else{
                x = new_x;
                y = new_y;
                cout << "---" << x << "," << y << " = " << k << endl;
                result[x][y] = k;
            }
        }


        return result;
    }
};