leetcode-322-337-338

leetcode 322题 337题 338题

leetcode332题:零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例:

输入:coins = [1,2,5],amount = 11

输出:3

解释:11 = 5+5+1

输入:coins = [2], amount = 3

输出:-1

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var coinChange = function(coins, amount) {
if(coins.length==0){
return -1;
}
var dp = [];
for(var i=1;i<=amount;i++){
dp[i] = Infinity;
}
dp[0] = 0;
for(var i=0;i<coins.length;i++){
for(var j=coins[i];j<=amount;j++){
if(dp[j-coins[i]]!=Infinity){
dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
}
}
}
if(dp[amount]!=Infinity){
return dp[amount];
}
return -1;
};

leetcode337题:打家劫舍III

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

示例:

示例1

示例2

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
var rob = function(root) {
if(root==null){
return 0;
}
var val = 0;
if(root.left!=null){
val = val + rob(root.left.left)+rob(root.left.right);
}
if(root.right!=null){
val = val + rob(root.right.left)+rob(root.right.right);
}
return Math.max(root.val+val,rob(root.left)+rob(root.right));
};

leetcode338题:比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例:

输入:2

输出:[0,1,1]

输入:5

输出:[0,1,1,2,1,2]

进阶:
  • 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗?
  • 要求算法的空间复杂度为O(n)。
  • 你能进一步完善解法吗?要求在C++或任何其他语言中不使用任何内置函数(如 C++ 中的 __builtin_popcount)来执行此操作。
解答:
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
//非进阶版
var countBits = function(num) {
var result = [];
for(var i=0;i<=num;i++){
var bits = i.toString(2);
var count = 0;
for(var j=0;j<bits.length;j++){
if(bits[j]=='1'){
count++;
}
}
result.push(count);
}
return result;
};
//进阶版
/*i & (i - 1)可以去掉i最右边的一个1(如果有),因此 i & (i - 1)是比 i 小的,而且i & (i - 1)的1的个数已经在前面算过了,所以i的1的个数就是 i & (i - 1)的1的个数加上1.*/
var countBits = function(num) {
var result = [];
result[0] = 0;
for(var i=1;i<=num;i++){
result[i] = result[i&(i-1)]+1;//&表示按位与
}
return result;
};
分享到