leetcode刷题笔记
202. 快乐数 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
|
var getHappy = function(n){
let ans = 0;
while(n){
ans+= (n%10) ** 2;
n/=10;
}
return ans;
}
|
错误原因
在 JavaScript 中，使用/运算符进行除法运算时（如n /= 10这个操作），如果n原本是整数类型，这样的除法操作会将结果转换为浮点数类型。
例如，当n初始值为19，第一次执行n /= 10后，n会变成1.9，而后续在getHappy函数里期望对每一位数字进行处理（通过n % 10获取个位数字等操作），浮点数的取余等操作的行为和预期处理整数时不一致，并且不符合题目本意（通常是按整数的每一位来处理）。
要解决这个问题，应该使用Math.floor（向下取整）或者Math.trunc（去除小数部分）等方法来确保n在分割每一位数字的过程中依然保持整数类型，修改后的getHappy函数如下：
1
2
3
4
5
6
7
8
| var getHappy = function(n){
let ans = 0;
while(n){
ans+= (n%10) ** 2;
n = Math.trunc(n/10);
}
return ans;
}
|
15. 三数之和 - 力扣（LeetCode）
1
2
3
4
5
|
var threeSum = function(nums) {
nums.sort();
};
|
错误原因
Array.sort()默认排序是将元素转换为字符串，然后按照它们的 UTF-16 码元值升序排序，所以这样写会导致整数无法按大小排序。正确代码如下
1
2
3
4
| var threeSum = function(nums) {
nums.sort((a,b)=>a-b);
};
|
541. 反转字符串 II - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
|
var reverse = function(s,from,to){
while(from<to){
let temp = s[from];
s[from] = s[to];
s[t0] = temp;
from++,to--;
}
}
|
错误原因
JavaScript中字符串为按值传递，作为参数传递时无法改变值。应改为传递数组，正确代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var reverse = function(arr,from,to){
while(from<to){
let temp = arr[from];
arr[from] = arr[to];
arr[to] = temp;
from++,to--;
}
}
var reverseStr = function(s, k) {
const arr = Array.from(s);
for(let i=0;i<arr.length;i+=2*k){
reverse(arr,i,Math.min(arr.length-1,i+k-1));
}
return arr.join('');
};
|
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
KMP算法模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var strStr = function(haystack, needle) {
const m=haystack.length,n=needle.length;
if(n===0) return 0;
const next= new Array(n).fill(0);
for(let i=1,j=0;i<n;i++){
while(j>0&&needle[i]!==needle[j]) j=next[j-1];
if(needle[i]===needle[j]) j++;
next[i]=j;
}
for(let i=0,j=0;i<m;i++){
while(j>0&&haystack[i]!==needle[j]) j=next[j-1];
if(haystack[i]===needle[j]) j++;
if(j===n) return i-n+1;
}
return -1;
};
|
239. 滑动窗口最大值 - 力扣（LeetCode）
数组模拟栈：const stack = [];
- 入栈：stack.push(x);
- 出栈：stack.pop();
- 查看栈顶：stack.at(-1);
- 判断栈非空：stack.length
数组模拟队列：const queue = []
- 入队：queue.push(x)
- 出队：queue.shift()
- 查看队首：queue[0]
- 查看队尾：queue.at(-1)
- 判断队非空：queue.length
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var maxSlidingWindow = function(nums, k) {
let ans = [];
let queue = [];
for(let i=0;i<k-1;i++){
while(queue.length&&nums[queue.at(-1)]<nums[i]) queue.pop();
queue.push(i);
}
for(let i=k-1;i<nums.length;i++){
while(queue.length&&nums[queue.at(-1)]<nums[i]) queue.pop();
queue.push(i);
while(queue[0]<=i-k) queue.shift();
ans.push(nums[queue[0]]);
}
return ans;
};
|
77. 组合 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| //错误代码
const ans = [];
const path = [];
var backtracking = function(n,k,startIndex){
if(path.length===k){
ans.push(path);
return;
}
for(let i=startIndex;i<=n-k+path.length+1;i++){
path.push(i);
backtracking(n,k,i+1);
path.pop();
}
};
var combine = function(n, k) {
backtracking(n,k,1);
return ans;
};
|
错误原因
- ans和path需要初始化
- 需将path的副本加入ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| let ans = [];
let path = [];
var backtracking = function(n,k,startIndex){
if(path.length===k){
ans.push(path.concat());
return;
}
for(let i=startIndex;i<=n-k+path.length+1;i++){
path.push(i);
backtracking(n,k,i+1);
path.pop();
}
};
var combine = function(n, k) {
ans = [];
path = [];
backtracking(n,k,1);
return ans;
};
|
189. 轮转数组 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
var rotate = function(nums, k) {
const reverse = function(nums,from,to){
while(from<to){
let temp = nums[from];
nums[from] = nums [to];
nums[to] = temp;
from++,to--;
}
}
reverse(nums,0,nums.length-k-1);
reverse(nums,nums.length-k,nums.length-1);
reverse(nums,0,nums.length-1);
};
|
错误原因
元素左移、右移，传入翻转长度不能小于0或大于数组长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| var rotate = function(nums, k) {
k%=nums.length;
const reverse = function(nums,from,to){
while(from<to){
let temp = nums[from];
nums[from] = nums [to];
nums[to] = temp;
from++,to--;
}
}
reverse(nums,0,nums.length-k-1);
reverse(nums,nums.length-k,nums.length-1);
reverse(nums,0,nums.length-1);
};
|
121. 买卖股票的最佳时机 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
|
var maxProfit = function(prices) {
let preMin = 0,ans = 0;
for(let price of prices){
if(price > preMin) ans = Math.max(ans,price-preMin);
else preMin = price;
}
return ans;
};
|
错误原因
设置preMin为0会导致股票一定有price的收益，正确做法应该是设置成Number.MAX_SAFE_INTEGER
1
2
3
4
5
6
7
8
| var maxProfit = function(prices) {
let preMin = Number.MAX_SAFE_INTEGER,ans = 0;
for(let price of prices){
if(price > preMin) ans = Math.max(ans,price-preMin);
else preMin = price;
}
return ans;
};
|
6. Z 字形变换 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
var convert = function(s, numRows) {
let ans = "";
let temp = new Array(numRows).fill([]);
let index=0,flag =-1;
for(let ch of s){
if(index===0||index === numRows-1) flag = -flag;
temp[index].push(ch);
index+=flag;
}
for(let i=0;i<numRows;i++){
ans+=temp[i].join('');
}
return ans;
};
|
错误原因
new Array(numRows).fill([]) 这种方式会导致 temp 数组中的所有元素都引用同一个空数组，而不是每个元素都是独立的空数组。
同时，当rows===1是需要特殊处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var convert = function(s, numRows) {
if(numRows===1) return s;
let ans = "";
let temp = new Array(numRows).fill().map(()=>[]);
let index=0,flag =-1;
for(let ch of s){
if(index===0||index === numRows-1) flag = -flag;
temp[index].push(ch);
index+=flag;
}
for(let i=0;i<numRows;i++){
ans+=temp[i].join('');
}
return ans;
};
|
84. 柱状图中最大的矩形 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| //错误代码
var largestRectangleArea = function(heights) {
const n = heights.length;
const leftLowerIndex = new Array(n).fill(0);
const rightLowerIndex = new Array(n).fill(n-1);
let ans = 0;
let stack = [];
for(let i=0;i<n;i++){
while(stack.length>0&&heights[stack.at(-1)]>heights[i]){
const index = stack.pop();
rightLowerIndex[index]=i;
}
stack.push(i);
}
stack = [];
for(let i=n-1;i>=0;i--){
while(stack.length>0&&heights[stack.at(-1)]>heights[i]){
const index = stack.pop();
leftLowerIndex[index]=i;
}
stack.push(i);
}
for(let i=0;i<n;i++){
ans = Math.max(ans,heights[i]*(rightLowerIndex[i]-leftLowerIndex[i]-1));
}
return ans;
};
|
错误原因：
左边更低高度索引初值应设为-1；右边更低高度索引初值应设为n;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| //正确代码
var largestRectangleArea = function(heights) {
const n = heights.length;
const leftLowerIndex = new Array(n).fill(-1);
const rightLowerIndex = new Array(n).fill(n);
let ans = 0;
let stack = [];
for(let i=0;i<n;i++){
while(stack.length>0&&heights[stack.at(-1)]>heights[i]){
const index = stack.pop();
rightLowerIndex[index]=i;
}
stack.push(i);
}
stack = [];
for(let i=n-1;i>=0;i--){
while(stack.length>0&&heights[stack.at(-1)]>heights[i]){
const index = stack.pop();
leftLowerIndex[index]=i;
}
stack.push(i);
}
for(let i=0;i<n;i++){
ans = Math.max(ans,heights[i]*(rightLowerIndex[i]-leftLowerIndex[i]-1));
}
return ans;
};
|
343. 整数拆分 - 力扣（LeetCode）
考虑数值过小的边界情况，取整取余
1
2
3
4
5
6
7
8
9
| //正确代码
var integerBreak = function(n) {
if(n<=3) return n-1;
if(n%3===1){
return 3**(Math.floor(n/3)-1)*4;
}else{
return 3**(Math.floor(n/3))*2**Math.floor((n%3)/2);
}
};
|
96. 不同的二叉搜索树 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
| //计算组合数
var numTrees = function(n) {
let ans = 1,fz = 2*n,count = n-1,fm=n;
while(count--){
ans*=fz--;
while(ans%fm===0) ans/=fm--;
}
return ans;
};
|
494. 目标和 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var findTargetSumWays = function(nums, target) {
let sum = 0;
for(let num of nums) sum+=num;
if(sum+target<0||(sum+target)%2===1) return 0;
const m=nums.length,n=(sum+target)>>1;
const dp = new Array(m+1).fill().map(()=>new Array(n+1).fill(0));
dp[0][0]=1;
for(let i=1;i<=m;i++){
for(let j=0;j<=n;j++){
dp[i][j]+=dp[i-1][j];
if(nums[i-1]<=j) dp[i][j]+=dp[i-1][j-nums[i-1]];
}
}
return dp[m][n];
};
|
