代码随想录算法训练营Day2|977 有效数组的平方，59螺旋矩

977.有效数组的平方

题目描述：

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

解题心路历程

• 暴力解法，先平方，后排序，也不是不行，不是最优解
• 看题解说利用双指针法（这题目和双指针有什么关系么？？？如下）
• 非递减序列，平方后，最大值或最小值在开始或结尾位置，肯定不会是出现在中间的元素，left和right分别指向起始位置和结束位置，对应值进行比较，构建新数组作为返回结果。

注意
1 需要遍历整个数组；
2 新数组长度与原数组长度保持一致，并从末尾开始填充 ;
3 左、右指针对应的值被赋值给新数组后，才发生移动，并不是同时发生位置移动；

• 时间复杂度：O(n)
• 空间复杂度：O(1)

var sortedSquares = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    let res = [];
    let index = right
    for(let i = 0; i<nums.length; i++){
        let lval = Math.pow(nums[left], 2);
        let rval = Math.pow(nums[right], 2);
        if (lval < rval) {
            res[index] = rval
            right--
        } else {
            res[index] = lval
            left++
        }
        index--
    }
    return res
};

59.螺旋矩阵 ||

题目描述：

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n=1
输出：[[1]]

解题心路历程

• 一言难尽，怎么写都不对
• 需要模拟整个填充过程
• 循环结束条件竟然是计算圈数，比如n=2，圈数为1且刚刚好画完，n=3，圈数为1，缺少了中间元素，n=4，圈数为2且刚好画完整，n=5，圈数为2，缺少了中间元素，以此类推......所以，圈数为奇数时，需要手动填充中心坐标值

注意
1 遍历顺序完全同模拟过程一致：左 - > 右，上 -> 下，右 -> 左， 下 -> 上；
2 填充循环的区间保持统一，要不全部左闭右开，要不全部左开右闭;
3 循环1圈结束后，起始位置坐标要移动到下1圈中，即分别startX++，startY++，相应的可填充的个数减少1；
4 js中圈数loop 和中心坐标mid要用Math.floor(n / 2)取值，得到整数；

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

var generateMatrix = function(n) {
    let startX = 0;
    let startY = 0; // 起始位置
    let loop = Math.floor(n / 2); // 循环圈数
    let mid = Math.floor(n / 2); // 中心坐标
    let res = new Array(n).fill(0).map(() => new Array(n).fill(0));
    let offset = 1; // 控制每行填充元素的个数
    let count = 1; // 填充元素值
    while(loop--) {
        let row = startX;
        let col = startY;
        for (; col < n-offset; col++) {
            res[row][col] = count++
        }
        for (; row < n-offset; row++) {
            res[row][col] = count++
        }
        for (; col > startY; col--) {
            res[row][col] = count++
        }
        for (; row > startX; row--) {
            res[row][col] = count++
        }
        startX++
        startY++

        offset += 1
    }
    if (n % 2 === 1) {
        res[mid][mid] = count
    }
    return res;
};