977.有序數(shù)組的平方
題目：
給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums科展，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組均牢，要求也按 非遞減順序 排序。
示例 ：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后才睹，數(shù)組變?yōu)?[16,1,0,9,100]徘跪，排序后，數(shù)組變?yōu)?[0,1,9,16,100]
解題思路：
1. 暴力解法
最簡(jiǎn)單的方法就是每個(gè)數(shù)平方之后排序琅攘，一行代碼就可以搞定垮庐。
var sortedSquares = function (nums) {
return nums.map((item) => item * item).sort((a, b) => a - b)
};
2. 雙指針
數(shù)組平方的最大值就在數(shù)組的兩端，不是最左邊就是最右邊坞琴，不可能是中間哨查。因此可以從大到小來找對(duì)應(yīng)的元素，找到后把指針前移剧辐，循環(huán)終止條件是 left > right寒亥，這里還需要注意一點(diǎn)就是初始化數(shù)組的方式邮府。
var sortedSquares = function (nums) {
let count = nums.length - 1;
const arr = new Array(nums.length).fill(0);
let left = 0;
let right = count;
while(left <= right){
if(nums[left] * nums[left]>=nums[right] * nums[right]){
arr[count--] = nums[left] * nums[left];
left++;
}else{
arr[count--] = nums[right] * nums[right];
right--;
}
}
return arr;
};
209.長(zhǎng)度最小的子數(shù)組
題目：
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長(zhǎng)度最小的 連續(xù) 子數(shù)組溉奕，并返回其長(zhǎng)度褂傀。如果不存在符合條件的子數(shù)組，返回 0腐宋。
示例：
輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的子數(shù)組紊服。
解題思路：
1. 暴力解法
兩層for循環(huán)，外層記錄起始位置胸竞，內(nèi)層記錄終止位置欺嗤，一旦在內(nèi)層找到滿足條件的就break此時(shí)一定是當(dāng)前循環(huán)的最小值。
var minSubArrayLen = function (target, nums) {
let minLen = Infinity;
let sum = 0
for (let i = 0; i < nums.length; i++) {
sum = 0
for (let j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= target) {
const curLen = j - i + 1;
minLen = curLen < minLen ? curLen : minLen;
break;
}
}
}
return minLen === Infinity ? 0 : minLen
};
2. 滑動(dòng)窗口
這類解法的特點(diǎn)在于用一次循環(huán)就解決之前暴力解法需要兩輪for循環(huán)的問題卫枝。
需要考慮三個(gè)問題：
- 窗口范圍：窗口內(nèi)是滿足其和 ≥ s 的長(zhǎng)度最小的連續(xù)子數(shù)組煎饼。
- 窗口結(jié)束位置 j：窗口的結(jié)束位置就是遍歷數(shù)組的指針，也就是for循環(huán)里的索引校赤。
- 窗口起始位置 i：如果當(dāng)前窗口的值大于s了吆玖，窗口就要向前移動(dòng)了。這里還要注意窗口起始位置移動(dòng)需要再while循環(huán)里移動(dòng)马篮，因?yàn)橛锌赡茉?s = 5, nums = [1, 1, 1, 1, 5] 的情況沾乘，這時(shí)雖然已經(jīng)在 j = 4 的情況下第一次出現(xiàn)了 sum ≥ 5 的情況，但這個(gè)時(shí)候 i 仍然可以不斷向前移動(dòng)浑测，縮小區(qū)間翅阵。
var minSubArrayLen = function (target, nums) {
let minLen = Infinity;
let sum = 0
let i = 0;
for (let j = 0; j < nums.length; j++) {
sum += nums[j]
while (sum >= target) {
const curLen = j - i + 1;
minLen = curLen < minLen ? curLen : minLen;
sum -= nums[i]
i++;
}
}
return minLen === Infinity ? 0 : minLen
};
59.螺旋矩陣II
題目：
給定一個(gè)正整數(shù) n，生成一個(gè)包含 1 到 n^2 所有元素迁央，且元素按順時(shí)針順序螺旋排列的正方形矩陣掷匠。
示例：
輸入: 3
輸出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
解題思路：
1. 記錄四條邊所在的位置
在這種解法中分別定義 top、bottom岖圈、left讹语、right 四條邊所在的初始位置，然后依次進(jìn)行模擬蜂科，下面以 三階矩陣 為例來講解顽决。
- 對(duì)于top ，top行不變导匣，記錄從左到右的序號(hào)擎值，然后把top向下移動(dòng)。
[ [ 1, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
[ [ 1, 2, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
[ [ 1, 2, 3 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
- 對(duì)于 right逐抑，right列不變鸠儿，記錄從上到下的序號(hào)，然后把right向左移動(dòng)。
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 0, 0, 0 ] ]
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 0, 0, 5 ] ]
-對(duì)于bottom进每，bottom行不變汹粤，記錄從右到左的序號(hào)，然后把bottom向上移動(dòng)田晚。
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 0, 6, 5 ] ]
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 7, 6, 5 ] ]
-對(duì)于left嘱兼，left列不變，記錄從下到上的序號(hào)贤徒，然后把left向右移動(dòng)芹壕。
[ [ 1, 2, 3 ], [ 8, 0, 4 ], [ 7, 6, 5 ] ]
此時(shí)四個(gè)邊的值分別為1、1接奈、1踢涌、1，所以再執(zhí)行一次top的循環(huán)就會(huì)實(shí)現(xiàn)矩陣序宦。
[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
代碼如下：
var generateMatrix = function (n) {
const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
let top = 0;
let bottom = n - 1;
let left = 0;
let right = n - 1;
let cur = 1;
while (cur <= n * n) {
for (let i = left; i <= right; i++, cur++) {
matrix[top][i] = cur
}
top++;
for (let i = top; i <= bottom; i++, cur++) {
matrix[i][right] = cur
}
right--;
for (let i = right; i >= left; i--, cur++) {
matrix[bottom][i] = cur
}
bottom--;
for (let i = bottom; i >= top; i--, cur++) {
matrix[i][left] = cur
}
left++;
}
return matrix;
};
2. 記錄每輪的偏移量offset
這種方法遵循 左閉右開 原則睁壁，每輪對(duì)一圈進(jìn)行操作，并且區(qū)分奇偶數(shù)互捌。
var generateMatrix = function (n) {
const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
let loop = Math.floor(n / 2);
let mid = Math.floor(n / 2);
let count = 1;
let offset = 1;
let startx = 0;
let starty = 0;
while (loop--) {
let i = startx;
let j = starty;
for (j = startx; j < n - offset; j++) {
matrix[startx][j] = count++;
}
for (i = startx; i < n - offset; i++) {
matrix[i][j] = count++;
}
while (j > starty) {
matrix[i][j] = count++;
j--;
}
while (i > startx) {
matrix[i][j] = count++;
i--;
}
startx++;
starty++;
offset += 1;
}
if (n % 2) {
matrix[mid][mid] = count;
}
return matrix;
};
注意點(diǎn)：
- 二維數(shù)組的初始化方式：
const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
- 第一種方式不需要區(qū)分奇偶潘明，第二種方式需要。
