??41. 缺失的第一個正數

題目鏈接：41. 缺失的第一個正數

難度：困難

刷題狀態：1刷

新知識：

解題過程

思考

示例 1：

輸入：nums = [1,2,0]
輸出：3
解釋：范圍 [1,2] 中的數字都在數組中。

請你實現時間復雜度為?O(n)?并且只使用常數級別額外空間的解決方案。

重點是不能用這個 nums.sort((a,b)=>a-b)，不能排序

注意可能出現重復的數字

搞不出來看答案

題解分析

參考題解鏈接：缺失的第一個正數

第一：當nums[i]>n的時候，不用去考慮

比如nums = [7,8,9,11,12]，n=5，排滿的情況下[1,2,3,4,5],所以7，8，9，，，根本不用考慮

第二：假設nums[i]就應該待在nums[nums[i]-1]的位置，

nums[i]是值a，他現在的位置是i，他應該在的位置是nums[i]-1

但是現在在nums[i]-1位置上的是nums[nums[i]-1]值b，要交換ab的值，是值a呆在nums[i]-1位置上

也就是nums[i]=nums[nums[i]-1]

就是說理想的情況是[1,2,3,4],然后出現了[1,1,3,4],那么就可以判斷2是缺失的

詳細分析如下

第三，要用while而不是if，因為被換過來的值b現在待在i位置上，但b應該在的位置是b-1，兩者不一定相等，所以要循環直到經歷過該位置的數字都各歸各位

，代碼如下

var firstMissingPositive = function(nums) {let n=nums.lengthfor(let i=0;i<n;i++){while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){let tmp=nums[nums[i]-1]nums[nums[i]-1]=nums[i]nums[i]=tmp}}for(let i=0;i<n;i++){if(nums[i]!=i+1){return i+1}}return n+1
};

手搓答案（無非廢話版）

var firstMissingPositive = function(nums) {let n=nums.lengthfor(let i=0;i<n;i++){while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){let tmp=nums[nums[i]-1]nums[nums[i]-1]=nums[i]nums[i]=tmp}}for(let i=0;i<n;i++){if(nums[i]!=i+1){return i+1}}return n+1
};

總結

這題太巧妙了，雖然寫出來就幾行，但邏輯上要拐幾個彎（頭凸）

73. 矩陣置零

題目鏈接：73. 矩陣置零

難度：中等

刷題狀態：1刷

新知識：

解題過程

思考

示例 1：

輸入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
輸出：[[1,0,1],[0,0,0],[1,0,1]]

寫出來了，速度很慢

/*** @param {number[][]} matrix* @return {void} Do not return anything, modify matrix in-place instead.*/
var setZeroes = function(matrix) {let mm=[],nn=[],mok=0for(let m=0;m<matrix.length;m++){for(let n=0;n<matrix[m].length;n++){if(!matrix[m][n]){mm.push(m)nn.push(n)}}}for(let m=0;m<matrix.length;m++){mok=0for(let i of mm){if(m==i){let mok=1for(let n=0;n<matrix[m].length;n++){matrix[m][n]=0}break}}if(!mok){for(let n=0;n<matrix[m].length;n++){for(let j of nn){if(n==j){matrix[m][n]=0}}}}}
};

題解分析

參考題解鏈接：矩陣置零

改進的點主要在，建立row和col，直接表示二維數組，這樣在第二遍循環賦值的時候就直接判斷row，col就行

/*** @param {number[][]} matrix* @return {void} Do not return anything, modify matrix in-place instead.*/
var setZeroes = function(matrix) {let m=matrix.length,n=matrix[0].lengthlet row=Array(m).fill(1)let col=Array(n).fill(1)for(let i=0;i<m;i++){for(let j=0;j<n;j++){if(!matrix[i][j]){row[i]=0col[j]=0}}}for(let i=0;i<m;i++){for(let j=0;j<n;j++){if(row[i]==0||col[j]==0){matrix[i][j]=0}}}
};

手搓答案（無非廢話版）

/*** @param {number[][]} matrix* @return {void} Do not return anything, modify matrix in-place instead.*/
var setZeroes = function(matrix) {let m=matrix.length,n=matrix[0].lengthlet row=Array(m).fill(1)let col=Array(n).fill(1)for(let i=0;i<m;i++){for(let j=0;j<n;j++){if(!matrix[i][j]){row[i]=0col[j]=0}}}for(let i=0;i<m;i++){for(let j=0;j<n;j++){if(row[i]==0||col[j]==0){matrix[i][j]=0}}}
};

總結

?不難，多刷多記

?54. 螺旋矩陣

題目鏈接：???????54. 螺旋矩陣

難度：中等

刷題狀態：1刷

新知識：

解題過程

思考

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,3,6,9,8,7,4,5]

我的理解是，每次第一行的數值遍歷完之后，剩下的數組進行轉置，（456789長方體逆時針旋轉90°）然后下一次循環遍歷還是從新的數組的第一行開始

一遍過哈哈！

題解分析

參考題解鏈接：螺旋矩陣

手搓答案（無非廢話版）

/*** @param {number[][]} matrix* @return {number[]}*/
var spiralOrder = function(matrix) {let res=[]let n=matrix.length*matrix[0].lengthwhile(res.length<n){for(let i=0;i<matrix[0].length;i++){res.push(matrix[0][i])}matrix.shift()if(res.length<n) matrix=zzh(matrix)}return res
};
function zzh(ma){let rows=ma.lengthlet cols=ma[0].lengthlet trans=[]for(let i=0;i<cols;i++){trans[i]=[]for(let j=0;j<rows;j++){trans[i][j]=ma[j][cols-1-i]}}return trans
}

總結

?由轉置矩陣的代碼要知道是怎么寫的，先生成cols個[[],[],[],,,,]空子集，再往里面賦值

????????48. 旋轉圖像

題目鏈接：???????48. 旋轉圖像

難度：中等

刷題狀態：1刷

新知識：

解題過程

思考

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[[7,4,1],[8,5,2],[9,6,3]]

你必須在?原地?旋轉圖像，這意味著你需要直接修改輸入的二維矩陣。請不要?使用另一個矩陣來旋轉圖像。

這題是順時針旋轉90°

1現在在[0,0]，應該在[0,2]? ? ? ? 2現在在[0,1]，應該在[1,2]? ? ? ? 3現在在[0,2]，應該在[2,2]

4現在在[1,0]，應該在[0,1]? ? ? ? 5現在在[1,1]，應該在[1,1]? ? ? ? 6現在在[1,2]，應該在[2,1]

7現在在[2,0]，應該在[0,0]? ? ? ? 8現在在[2,1]，應該在[1,0]? ? ? ? 9現在在[2,2]，應該在[2,0]

找規律

發現matrix[i][j]=matrix[n-1-j][i]

但我沒寫出來，看答案

題解分析

參考題解鏈接：旋轉圖像

舉個例子吧

開始循環的時候，

7到1的位置00了，matrix[i][j]=matrix[n-1-j][i]

然后9應該到7的位置20，matrix[n-1-j][i]=matrix[n-1-i][n-1-j]

然后3應該到9的位置22，matrix[n-1-i][n-1-j]=matrix[j][n-1-i]

然后1應該到3的位置02，matrix[j][n-1-i]=matrix[i][j]

至此一次循環完成，可以理解為從外到內每次完成第一排(n+1)/2個元素（0，1）的旋轉交換位置，然后第二排(n+1)/2個元素，直到第n/2排，

或者也可以理解為每次完成第一排n/2個元素的旋轉交換位置，然后第二排n/2個元素，直到第（n+1）/2排，

所以

/*** @param {number[][]} matrix* @return {void} Do not return anything, modify matrix in-place instead.*/
var rotate = function(matrix) {let n=matrix.lengthfor(let i=0;i<Math.floor(n/2);i++){for(let j=0;j<Math.floor((n+1)/2);j++){let tmp=matrix[i][j]matrix[i][j]=matrix[n-1-j][i]matrix[n-1-j][i]=matrix[n-1-i][n-1-j]matrix[n-1-i][n-1-j]=matrix[j][n-1-i]matrix[j][n-1-i]=tmp}}
};

手搓答案（無非廢話版）

/*** @param {number[][]} matrix* @return {void} Do not return anything, modify matrix in-place instead.*/
var rotate = function(matrix) {let n=matrix.lengthfor(let i=0;i<Math.floor((n+1)/2);i++){for(let j=0;j<Math.floor(n/2);j++){let tmp=matrix[i][j]matrix[i][j]=matrix[n-1-j][i]matrix[n-1-j][i]=matrix[n-1-i][n-1-j]matrix[n-1-i][n-1-j]=matrix[j][n-1-i]matrix[j][n-1-i]=tmp}}
};

總結

?注意上面i，j的不同，i，j都是相對于當前的mat