leetcode-494-538

leetcode 494 538题

leetcode 494题题目:

给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var findTargetSumWays = function(nums, S) {
var sum = 0;
for(var i=0;i<nums.length;i++){
sum = sum + nums[i];
}
if(sum<S||(sum+S)%2!=0){
return 0;
}
var arr = [];
var w = parseInt((sum+S)/2);
for(var j=0;j<w+1;j++){
arr[j] = 0;
}
arr[0] = 1;
for(var i=0;i<nums.length;i++){
for(var j=w;j>=nums[i];j--){
arr[j] = arr[j] + arr[j-nums[i]];
}
}
return arr[w];
};

leetcode538题题目:

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

示例

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var convertBST = function(root) {
var num = 0;
function convert1(root){
if(root==null){
return;
}
convert1(root.right);
root.val = root.val + num;
num = root.val;
convert1(root.left);
}
convert1(root);
return root;
};
分享到