337. 打家劫舍 III House Robber iii
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
- 树的节点数在
[1, 10^4]范围内 0 <= Node.val <= 10^4
相关：
213. 打家劫舍 II House Robber ii 🌟🌟
代码：
package main import "fmt" type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func rob(root *TreeNode) int { robResult, notRobResult := _rob(root) return max(robResult, notRobResult) } func _rob(node *TreeNode) (int, int) { if node == nil { return 0, 0 } leftRob, leftNotRob := _rob(node.Left) rightRob, rightNotRob := _rob(node.Right) robResult := node.Val + leftNotRob + rightNotRob notRobResult := max(leftRob, leftNotRob) + max(rightRob, rightNotRob) return robResult, notRobResult } func max(a, b int) int { if a > b { return a } return b } func listToTree(lst []interface{}) *TreeNode { if len(lst) == 0 { return nil } root := &TreeNode{Val: lst[0].(int)} queue := []*TreeNode{root} i := 1 for i < len(lst) { node := queue[0] queue = queue[1:] if lst[i] != nil { node.Left = &TreeNode{Val: lst[i].(int)} queue = append(queue, node.Left) } i++ if i < len(lst) && lst[i] != nil { node.Right = &TreeNode{Val: lst[i].(int)} queue = append(queue, node.Right) } i++ } return root } func main() { nums := []interface{}{3, 2, 3, nil, 3, nil, 1} root := listToTree(nums) fmt.Println(rob(root)) nums = []interface{}{3, 4, 5, 1, 3, nil, 1} root = listToTree(nums) fmt.Println(rob(root)) }
输出：
7
9
338. 比特位计数 Counting Bits
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
0 <= n <= 10^5
进阶：
- 很容易就能实现时间复杂度为
O(n log n)的解决方案，你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount）
代码：动态规划
package main import "fmt" func countBits(n int) []int { ans := make([]int, n+1) for i := 1; i <= n; i++ { ans[i] = ans[i&(i-1)] + 1 } return ans } func main() { fmt.Println(countBits(2)) fmt.Println(countBits(5)) }
输出：
[0 1 1]
[0 1 1 2 1 2]
逐位计算：
```golang func countBits(n int) []int { ans := make([]int, n+1) for i := 0; i <= n; i++ { count := 0 num := i for num != 0 { count += num & 1 num >>= 1 } ans[i] = count } return ans } ```
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
