leetcode-279-283

leetcode279题283题

leetcode279题(完全平方数):

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例:

输出:n=12

输出:3

解释:12 = 4+4+4

输出:n=13

输出:2

解释:12 = 4+9

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
var numSquares = function(n) {//动态规划
var dp = [];
for(var i=0;i<=n;i++){
dp[i] = 0;
}
for(var i=1;i<=n;i++){
dp[i] = i;//下面取两个数中的最小值,因此此处需要定义结果最大值
for(var j=0;i-j*j>=0;j++){
dp[i] = Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
};

leetcode283题(移动零):

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入:[0,1,0,3,12]

输出:[1,3,12,0,0]

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var moveZeroes = function(nums) {//复杂度为O(n^2)的解法
for(var i=0;i<nums.length;i++){
if(nums[i]==0){//思想:统计某个为0的数字后面是否还有非零,如果有非零数字,那么执行splice+push的操作(此处需要i--,否则会跳过0后面的数字)
var count = 0;
for(var j=i;j<nums.length;j++){
if(nums[j]==0){
count++;
}
}
if(count!=nums.length-i){
nums.push(nums[i]);
nums.splice(i,1);
i--;
}

}
}
return nums;
};
1
2
3
4
5
6
7
8
9
10
11
12
var moveZeroes = function(nums) {//只设置一个指针,将碰到的非0数字用lastIndex的下标记录在nums中(这个时候前面的0与非0的元素都已经处理了,不会出现覆盖的情况),然后将其与nums原长度之差的最后的地方放置为0
var lastIndex = 0;
for(var i=0;i<nums.length;i++){
if(nums[i]!=0){
nums[lastIndex++] = nums[i];
}
}
for(var j=lastIndex;j<nums.length;j++){
nums[j] = 0;
}
return nums;
};
1
2
3
4
5
6
7
8
9
10
11
var moveZeroes = function(nums) {//采用双指针的方法,slow始终指向最开始的0
for(var slow=0,fast=0;fast<nums.length;fast++){
if(nums[fast]!=0){//fast指向0后面的第一个非零数进行处理
var temp = nums[fast];
nums[fast] = nums[slow];
nums[slow] = temp;
slow++;
}
}
return nums;
};

艾丽.范宁

分享到