LeetCode热题100JS（20/100）第四天|41. 缺失的第一个正数|73. 矩阵置零|54. 螺旋矩阵|48. 旋转图像

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}}
};