有序数组的平方和滑动窗口和螺旋矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了有序数组的平方和滑动窗口和螺旋矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.有序数组的平方

leetcode

代码如下（示例）：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
    int i = 0;
    int j = nums.size() - 1;
    vector<int> A(nums.size(), 0);
    int k = nums.size() - 1;
    int a,b = 0;
    while ( i <= j ) {
        a = nums[i] * nums[i];
        b = nums[j] * nums[j];
        if (a < b) {
            A[k] = b;
            j--;
            k--;
        }
        else {
            A[k] = a;
            i++;
            k--;
        }


    }

    return A;
    }
};

负数的平方是要比较小正数平方大的
可以先求出所有数的平方，在排序，较麻烦
采用双指针
头指针 i 和尾指针 j 和记数组元素个数的 k
将头指针和尾指针所指元素平方进行比较较大一个放到新数组的尾部指针减一直到i=j

2.滑动窗口

leetcode

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int j = 0;
        int result = INT32_MAX;
        int sum = 0;
        int i = 0;

        for ( ; j < nums.size() ; j++) {
            sum += nums[j];
            while ( sum >= target) {
                int length = j - i + 1;
                result = result > length ? length : result;
                sum -= nums[i];
                i++;
            }
        }

          return result = result == INT32_MAX ? 0 : result;
    }
  
};

j 为窗口尾部   i为窗口头部
用j依次往后遍历     计算  从头到尾的sum 与所给val比较   如果大于
看从头到尾的长度  即j-i+1    是否为最小
之后进入头部滑动  先在sum中剪掉 num【i】  之后 i－－

3.螺旋矩阵

leetcode

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> A(n, vector<int>(n, 0));
        int startx , starty = 0;
        int count = 1;
        int num = n/2;
        int i , j = 0;
        int change = 1;
        while ( num-- ) {
            for ( j = starty ; j < n - change ; j++ ) {
                A[startx][j] = count++;
            }
            for ( i = startx ; i < n - change ; i++ ) {
                A[i][j] = count++;
            }
            for (  ; j > starty ; j-- ) {
                A[i][j] = count++;
            }
            for (  ; i > startx ; i-- ) {
                A[i][j] = count++;
            }
            startx++;
            starty++;
            change++;    
        }
        if ( n % 2 == 1 ) {
            A[num][num] = n *n ;
        } 
        return A;
    }
};

循环圈数为什么是n/2 可以就看第一行第一圈是n 第二圈是n-2 第三圈是 n - 4 可以看出一共可以转n/2圈

采用左闭右开的数组循环，每次对于最后一个都不进行赋值，保持循环不变量。

此题对于 n 为奇数形式答案会报错，暂时看不出来，求个大佬解答

文章来源地址https://www.toymoban.com/news/detail-463016.html

到了这里，关于有序数组的平方和滑动窗口和螺旋矩阵的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！