leetcode-39-42-46

leetcode39题42题46题:

leetcode39题(组合总和):

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var combinationSum = function(candidates, target) {
var res = [];
var start = 0;
var path = [];
candidates = candidates.sort(compare);
generateCombinationSum(candidates,start,path,target,res);
return res;
};
function generateCombinationSum(candidates,start,path,residue,res){
if(residue==0){
var arr = JSON.parse(JSON.stringify(path));
res.push(arr);
}
for(var i=start;i<candidates.length&&residue-candidates[i]>=0;i++){
path.push(candidates[i]);
generateCombinationSum(candidates,i,path,residue-candidates[i],res);
path.pop();
}
}
function compare(a,b){
return a-b;
}

leetcode42题(接雨水):

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

图

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var trap = function(height) {//按照列求
var sum = 0;
for(var i=1;i<height.length-1;i++){//不用遍历最左边一个和最右边一个,因为它们上面不可能有水
var left_max = 0;//求其左边的最高高度
for(var j=0;j<i;j++){
if(height[j]>left_max){
left_max = height[j];
}
}
var right_max = 0;//求其右边的最高高度
for(var j=i+1;j<height.length;j++){
if(height[j]>right_max){
right_max = height[j];
}
}
var min_max = Math.min(left_max,right_max);
if(min_max>height[i]){
sum = sum + (min_max-height[i]);
}
}
return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//改进的方法
var trap = function(height) {//按照列求,同时添加动态规划
var sum = 0;
var left = [];
left[0] = 0;
for(var i=1;i<height.length-1;i++){
left[i] = Math.max(left[i-1],height[i-1]);
}
var right = [];
right[height.length-1] = 0;
for(var i=height.length-2;i>=1;i--){
right[i] = Math.max(right[i+1],height[i+1]);
}
for(var i=1;i<height.length-1;i++){
var min_max = Math.min(left[i],right[i]);
if(min_max>height[i]){
sum = sum + (min_max-height[i]);
}
}
return sum;
}

leetcode46(全排列):

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解答:
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
28
var permute = function(nums) {
var res = [];
var visited = [];
for(var i=0;i<nums.length;i++){
visited[i] = false;
}
var curSize = 0;
var len = nums.length;
var path = [];
generatePermute(nums,visited,curSize,len,res,path);
return res;
};
function generatePermute(nums,visited,curSize,len,res,path){
if(curSize==len){
var arr = JSON.parse(JSON.stringify(path));
res.push(arr);
return;
}
for(var i=0;i<len;i++){
if(!visited[i]){
path.push(nums[i]);
visited[i] = true;
generatePermute(nums,visited,curSize+1,len,res,path);
path.pop();
visited[i] = false;
}
}
}
分享到