1. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:[[1,2,2],[5]]
出处：
https://edu.csdn.net/practice/26142804
代码：
class Solution(object): def combinationSum2(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ candidates.sort() dp = [[] for _ in range(target + 1)] dp[0].append([]) for i in range(1, target + 1): for j in range(len(candidates)): if candidates[j] > i: break for k in range(len(dp[i - candidates[j]])): temp = dp[i - candidates[j]][k][:] if len(temp) > 0 and temp[-1] >= j: continue temp.append(j) dp[i].append(temp) res = [] check = {} for temp in dp[target]: value = [candidates[t] for t in temp] try: check[str(value)] += 1 except KeyError: check[str(value)] = 1 res.append(value) return res # %% s = Solution() print(s.combinationSum2(candidates = [10,1,2,7,6,1,5], target = 8)) print(s.combinationSum2(candidates = [2,5,2,1,2], target = 5))
输出：
[[1, 2, 5], [1, 1, 6], [2, 6], [1, 7]]
[[1, 2, 2], [5]]
2. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
出处：
https://edu.csdn.net/practice/26142805
代码：
class Solution(object): def plusOne(self, digits): ls = len(digits) for index in reversed(range(ls)): if digits[index] < 9: digits[index] += 1 return digits else: digits[index] = 0 digits.insert(0, 1) return digits # %% s = Solution() print(s.plusOne(digits = [1,2,3])) print(s.plusOne(digits = [4,3,2,1])) print(s.plusOne(digits = [0])) print(s.plusOne(digits = [9,9,9]))
输出：
[1, 2, 4]
[4, 3, 2, 2]
[1]
[1, 0, 0, 0]
3. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
出处：
https://edu.csdn.net/practice/26142806
代码：
from typing import List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def levelOrder(self): if not self: return [] res, que = [], [self] while que: cur = que.pop(0) if cur: res.append(cur.val) que.append(cur.left) que.append(cur.right) else: res.append(None) while res[-1] is None: res.pop() return res class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: def build_tree(in_left, in_right, post_left, post_right): if in_left > in_right: return post_root = post_right root = TreeNode(postorder[post_root]) in_root = inorder_map[root.val] size_of_left = in_root - in_left root.left = build_tree( in_left, in_root - 1, post_left, post_left + size_of_left - 1 ) root.right = build_tree( in_root + 1, in_right, post_left + size_of_left, post_root - 1 ) return root size = len(inorder) inorder_map = {} for i in range(size): inorder_map[inorder[i]] = i return build_tree(0, size - 1, 0, size - 1) #%% inorder = [9,3,15,20,7] postorder = [9,15,7,20,3] s = Solution() print(s.buildTree(inorder, postorder).levelOrder())
输出：
[3, 9, 20, None, None, 15, 7]
