链接：LeetCode
有时间也要刷一下周赛，这周难度偏低，解析如下：
[Leetcode]1323. 6 和 9 组成的最大数字
给你一个仅由数字 6 和 9 组成的正整数 num。你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。返回你可以得到的最大数字。
判断有没有6，和第一个6的位置即可。
class Solution:
def maximum69Number (self, num: int) -> int:
nums = str(num)
res = list(nums)
for i in range(len(res)):
if res[i] == '6':
res[i] = '9'
break
return int(''.join(res))
[Leetcode]1324. 竖直打印单词
给你一个字符串 s。请你按照单词在 s 中的出现顺序将它们全部竖直返回。单词应该以字符串列表的形式返回，必要时用空格补位，但输出尾部的空格需要删除（不允许尾随空格）。每个单词只能放在一列上，每一列中也只能有一个单词。
示例：
输入：s = "HOW ARE YOU"
输出：(["HAY","ORO","WEU"])
解释：每个单词都应该竖直打印。
"HAY"
"ORO"
"WEU"
使用固定长列表填充即可，最后注意去除尾部的空格。
class Solution:
def printVertically(self, s: str) -> List[str]:
words = s.split()
len_word = max([len(x) for x in words])
res = [[] for _ in range(len_word)]
for word in words:
i = 0
while i<len(word):
res[i].append(word[i])
i+=1
while i<len(res):
res[i].append(' ')
i += 1
res = [''.join(x).rstrip() for x in res]
return res
[Leetcode]1325. 删除给定值的叶子节点
给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。
注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。
也就是说，你需要重复此过程直到不能继续删除。
这道题难度在于递归删除给定值的叶子节点，那么特别需要注意退出条件。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
if not root:
return
if root.val == target and not root.left and not root.right:
return
if root.val != target:
root.left = self.removeLeafNodes(root.left,target)
root.right = self.removeLeafNodes(root.right,target)
return root
else:
root.left = self.removeLeafNodes(root.left,target)
root.right = self.removeLeafNodes(root.right,target)
if not root.left and not root.right:
return
else:
return root
[Leetcode]1326. 灌溉花园的最少水龙头数目
在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。
花园里总共有 n + 1 个水龙头，分别位于 $[0, 1, ..., n] (。
给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]] 。
请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。
输入：)n = 5$, ranges = ([3,4,1,1,0,0])
输出：1
解释：
点 0 处的水龙头可以灌溉区间 ([-3,3])
点 1 处的水龙头可以灌溉区间 ([-3,5])
点 2 处的水龙头可以灌溉区间 ([1,3])
点 3 处的水龙头可以灌溉区间 ([2,4])
点 4 处的水龙头可以灌溉区间 ([4,4])
点 5 处的水龙头可以灌溉区间 ([5,5])
只需要打开点 1 处的水龙头即可灌溉整个花园 ([0,5]) 。
这道题普遍的解法是贪心或者动态规划。容易想到的是对于每一个位置的水龙头，我们先求出其最左/右边可以灌溉到的地方，并且由于我们只考虑0-n位置上的花园，如果最左边区间小于0，我们取0即可，最右边同理。那么，对于位置0来说，我们肯定会取能够灌溉到足够远区域的一个水龙头。如例子，点 0 处的水龙头可以灌溉区间 ([-3,3])，点 1 处的水龙头可以灌溉区间 ([-3,5])。我们考虑点1即可，这实际上是一个区间覆盖问题。这个很像[Leetcode]Jump Game II问题，于是可以将区间覆盖问题转化为一个跳跃问题，时间复杂度O(N)。
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
jumps = [0 for i in range(n+1)]
for i in range(n+1):
left = max(0,i-ranges[i])
right = min(n,i+ranges[i])
jumps[left] = right-left
return self.jump(jumps,n)
def jump(self, nums,n):
step = reach = max_num = 0
for i in range(len(nums)-1):
max_num = max(max_num,i+nums[i])
if i==reach:
step += 1
reach = max_num
if reach >= n:
return step
return -1