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.length
for(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.length
for(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=0
for(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=0
for(let i of mm){
if(m==i){
let mok=1
for(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].length
let 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]=0
col[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].length
let 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]=0
col[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].length
while(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.length
let cols=ma[0].length
let 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.length
for(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.length
for(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