1. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：
输入：root = [1,2], targetSum = 0
输出：false
提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
出处：
https://edu.csdn.net/practice/23951365
代码：
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def hasPathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: bool """ if root is None: return False if sum == root.val and root.left is None and root.right is None: return True return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val) def listToTree(lst: list) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [5,4,8,11,null,13,4,7,2,null,null,null,1] root = listToTree(nums) print(s.hasPathSum(root, 22)) nums = [1,2,3] root = listToTree(nums) print(s.hasPathSum(root, 5)) nums = [1,2] root = listToTree(nums) print(s.hasPathSum(root, 0))
输出：
True
Fasle
Fasle
代码2： 递归法2
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def hasPathSum(self, root: TreeNode, targetSum: int) -> bool: def dfs(node, path_sum = 0): if node is None: return False path_sum += node.val if not node.left and not node.right: return path_sum == targetSum return dfs(node.left, path_sum) or dfs(node.right, path_sum) return dfs(root) def listToTree(lst: list) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [5,4,8,11,null,13,4,7,2,null,null,null,1] root = listToTree(nums) print(s.hasPathSum(root, 22)) nums = [1,2,3] root = listToTree(nums) print(s.hasPathSum(root, 5)) nums = [1,2] root = listToTree(nums) print(s.hasPathSum(root, 0))
代码3：迭代法
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def hasPathSum(self, root: TreeNode, targetSum: int) -> bool: if not root: return False stack = [(root, root.val)] while stack: node, path_sum = stack.pop() if not node.left and not node.right: if path_sum == targetSum: return True if node.left: stack.append((node.left, path_sum + node.left.val)) if node.right: stack.append((node.right, path_sum + node.right.val)) return False def listToTree(lst: list) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [5,4,8,11,null,13,4,7,2,null,null,null,1] root = listToTree(nums) print(s.hasPathSum(root, 22)) nums = [1,2,3] root = listToTree(nums) print(s.hasPathSum(root, 5)) nums = [1,2] root = listToTree(nums) print(s.hasPathSum(root, 0))
2. 将数据流变为多个不相交区间
给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
实现 SummaryRanges 类：
SummaryRanges() 使用一个空数据流初始化对象。
void addNum(int val) 向数据流中加入整数 val 。
int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。
示例：
输入：
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出：
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
解释：
SummaryRanges summaryRanges = new SummaryRanges(); summaryRanges.addNum(1); // arr = [1] summaryRanges.getIntervals(); // 返回 [[1, 1]] summaryRanges.addNum(3); // arr = [1, 3] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr = [1, 2, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
提示：
0 <= val <= 10^4
最多调用 addNum 和 getIntervals 方法 3 * 10^4 次
进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?
出处：
https://edu.csdn.net/practice/23951364
代码：
from typing import List class SummaryRanges: def __init__(self): self.rec = set() self.s = list() def binarySearch_l(self, x: int): s = self.s l, r = 0, len(s) - 1 while l < r: mid = l + r >> 1 if s[mid][0] >= x: r = mid else: l = mid + 1 return l def binarySearch(self, x: int): s = self.s l, r = 0, len(s) - 1 while l < r: mid = l + r >> 1 if s[mid][1] >= x: r = mid else: l = mid + 1 return l def addNum(self, val: int) -> None: rec, s = self.rec, self.s if val in rec: return else: if val - 1 not in rec and val + 1 not in rec: s.append([val, val]) s.sort() elif val - 1 in rec and val + 1 not in rec: p = self.binarySearch(val - 1) s[p][1] = val elif val - 1 not in rec and val + 1 in rec: p = self.binarySearch_l(val + 1) s[p][0] = val else: p = self.binarySearch(val) s[p - 1][1] = s[p][1] s.pop(p) rec.add(val) def getIntervals(self) -> List[List[int]]: return self.s # %% res = [] summaryRanges = SummaryRanges(); summaryRanges.addNum(1); # arr = [1] s = summaryRanges.getIntervals(); # 返回 [[1, 1]] print(s) summaryRanges.addNum(3); # arr = [1, 3] s = summaryRanges.getIntervals(); # 返回 [[1, 1], [3, 3]] print(s) summaryRanges.addNum(7); # arr = [1, 3, 7] s = summaryRanges.getIntervals(); # 返回 [[1, 1], [3, 3], [7, 7]] print(s) summaryRanges.addNum(2); # arr = [1, 2, 3, 7] s = summaryRanges.getIntervals(); # 返回 [[1, 3], [7, 7]] print(s) summaryRanges.addNum(6); # arr = [1, 2, 3, 6, 7] s = summaryRanges.getIntervals(); # 返回 [[1, 3], [6, 7]] print(s)
输出：
[[1, 1]]
[[1, 1], [3, 3]]
[[1, 1], [3, 3], [7, 7]]
[[1, 3], [7, 7]]
[[1, 3], [6, 7]]
3. 文本左右对齐
给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
说明:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
示例:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 输出: [ "This is an", "example of text", "justification. " ]
示例 2:
输入: words = ["What","must","be","acknowledgment","shall","be"] maxWidth = 16 输出: [ "What must be", "acknowledgment ", "shall be " ] 解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be" 因为最后一行应为左对齐，而不是左右两端对齐，第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:
输入: words = ["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"] maxWidth = 20 输出: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]
出处：
https://edu.csdn.net/practice/23951366
代码：
class Solution(object): def fullJustify(self, words, maxWidth): """ :type words: List[str] :type maxWidth: int :rtype: List[str] """ res = [] res_list = [] curr = [] count, pos = 0, 0 while pos < len(words): word = words[pos] if len(word) > maxWidth: pos += 1 if len(word) + count + len(curr)<= maxWidth: count += len(word) curr.append(word) pos += 1 else: res_list.append(curr) curr = [] count = 0 if len(curr) > 0: res_list.append(curr) for index, curr in enumerate(res_list): text = '' remain = sum([len(t) for t in curr]) if len(curr) == 1: text = curr[0] + ' ' * (maxWidth - remain) elif index == len(res_list) - 1: text = ' '.join(curr) text += ' ' * (maxWidth - remain - len(curr) + 1) else: step = (maxWidth - remain) / (len(curr) - 1 ) extra = (maxWidth - remain) % (len(curr) - 1 ) for index in range(len(curr) - 1): text += curr[index] + ' ' * int(step) if extra > 0: text += ' ' extra -= 1 text += curr[-1] res.append(text) return res if __name__ == '__main__': s = Solution() words = ["This", "is", "an", "example", "of", "text", "justification."] for line in s.fullJustify(words, 16): print(line) print() words = ["What","must","be","acknowledgment","shall","be"] for line in s.fullJustify(words, 16): print(line) print() words = ["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"] for line in s.fullJustify(words, 20): print(line)
输出：
This is an example of text justification. What must be acknowledgment shall be Science is what we understand well enough to explain to a computer. Art is everything else we do
标准格式如下：
This is an example of text justification. What must be acknowledgment shall be Science is what we understand well enough to explain to a computer. Art is everything else we do
代码2： 优化
class Solution: def fullJustify(self, words, maxWidth): res, curr = [], [] curr_len = 0 # 当前行单词总长度 for w in words: if curr_len + len(curr) + len(w) > maxWidth: # 当前行放不下当前单词 if len(curr) == 1: # 特殊情况：当前行只有一个单词 res.append(curr[0] + ' '*(maxWidth-len(curr[0]))) else: space_num = maxWidth - curr_len # 空格总数 space_avg = space_num // (len(curr)-1) # 平均每个单词之间的空格数 space_extra = space_num % (len(curr)-1) # 额外的空格数 for i in range(len(curr)-1): if space_extra > 0: curr[i] += ' ' space_extra -= 1 curr[i] += ' '*space_avg res.append(''.join(curr)) curr, curr_len = [], 0 curr.append(w) curr_len += len(w) # 处理最后一行 res.append(' '.join(curr) + ' '*(maxWidth-curr_len-len(curr)+1)) return res if __name__ == '__main__': s = Solution() words = ["This", "is", "an", "example", "of", "text", "justification."] for line in s.fullJustify(words, 16): print(line) print() words = ["What","must","be","acknowledgment","shall","be"] for line in s.fullJustify(words, 16): print(line) print() words = ["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"] for line in s.fullJustify(words, 20): print(line)
