代码随想录算法训练营 day 2 | 有序数组 长度最小子数组 螺旋矩阵

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int size = nums.size();
        int tmp;
        for (int i = 0; i < size; i++)
            nums[i] = nums[i] * nums[i];
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) { //时间复杂度O(n^2)
                if (nums[i] > nums[j]) {
                    tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
        return nums;
    }
};

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

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int len = 1;
        int ret = 0;
        for (int len = 1; len <= size; len++) { // O(n^3)
            for (int i = 0; i + len - 1 < size; i++) {
                int localSum = 0;
                for (int j = i; j <= i + len - 1; j++) {
                    localSum += nums[j];
                    if (localSum >= target) {
                        ret = len;
                        goto end_loop;
                    }
                }
            }
        }
        end_loop:
            return ret;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sublength = INT32_MAX; //这里容易设置为0
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            int sum = 0;
            for (int j = i; j < size; j++) {
                sum += nums[j];
                if (sum >= target) {
                    sublength = (j - i + 1) < sublength ? (j - i + 1) : sublength; // sublength设置为零，则结果一直为0
                    break;
                }
            }
        }
        return sublength == INT32_MAX ? 0 : sublength;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sublength = INT32_MAX; 
        int size = nums.size();
        int sum = 0;
        for (int i = 0; i < size; i++) { //多个慢指针：对每一个终止位置的最大区间进行缩小
            sum += nums[i];
            int j = 0;  //这里设置为零，其实做了重复的工作，比如 1 + （2 + 3） + 4 + 5
            int tmp = sum;  
            while (tmp >= target) {
                sublength = (i - j + 1) < sublength ? (i - j + 1) : sublength; // sublength设置为零，则结果一直为0
                tmp -= nums[j++]; //缩小法
            }
        }
        return sublength == INT32_MAX ? 0 : sublength;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sublength = INT32_MAX; 
        int size = nums.size();
        int sum = 0;
        int j = 0;
        for (int i = 0; i < size; i++) { //多个慢指针：对每一个终止位置的最大区间进行缩小
            sum += nums[i];
           // int j = 0;
           // int tmp = sum;  
            while (sum >= target) {
                sublength = (i - j + 1) < sublength ? (i - j + 1) : sublength; // sublength设置为零，则结果一直为0
                sum -= nums[j++]; //缩小法 《体现滑动》 
            }
        }
        return sublength == INT32_MAX ? 0 : sublength;
    }
};

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int u = 0, d = n - 1, l = 0, r = n - 1;
        int sum = n * n;
        vector<vector<int>> vec(n, vector<int>(n)); //初始化方式
        int i = 1;
        while (i <= sum) {
            for (int j = l; j <= r; j++) { //判断条件易写错，比如l <= r
                vec[u][j] = i++;
            }
            u++;
            for (int k = u; k <= d; k++) {
                vec[k][r] = i++;
            }
            r--;
            for (int x = r; x >= l; x--) {
                vec[d][x] = i++;
            }
            d--;
            for (int y = d; y >= u; y--) {
                vec[y][l] = i++;
            }
            l++;
        }
        return vec;
    }
};