2020 第39周 LeetCode 记录

1588. Sum of All Odd Length Subarrays

处理当长度为 1 时特殊情况,其他都遍历长度为奇数情况然后求和。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
res = 0
for i in range(len(arr)+1):
if i % 2:
if i == 1:
res += sum(arr)
else:
j = 0
while j + i <= len(arr):
res += sum(arr[j:j+i])
j += 1
return res

1592. Rearrange Spaces Between Words

统计空格出现的次数,然后求出平均空格数进行字符串拼接。

1
2
3
4
5
6
7
8
class Solution:
def reorderSpaces(self, text: str) -> str:
cnt=text.count(" ")
n = text.split()
if len(n)==1:
return text.strip()+cnt*" "
space,last = divmod(cnt,len(n)-1)
return (" "*space).join(n)+" "*last

1593. Split a String Into the Max Number of Unique Substrings

回溯法,使用集合记录出现过的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def maxUniqueSplit(self, s: str) -> int:
self.ans = 0
d = set()

def helper(num, sub):
if not sub:
self.ans = max(num, self.ans)
return

if sub in d: return

for i in range(1, len(sub) + 1):
if sub[:i] not in d:
d.add(sub[:i])
helper(num + 1, sub[i:])
d.remove(sub[:i])

helper(0, s)

return self.ans

814. Binary Tree Pruning

如果叶子节点的左子树和右子树为空且当前值为 0,则将其置为空,递归剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pruneTree(self, root: TreeNode) -> TreeNode:
if root is None:
return root
root.left = self.pruneTree(root.left)
root.right = self.pruneTree(root.right)
if root.left is None and root.right is None and root.val == 0:
return None
return root

1008. Construct Binary Search Tree from Preorder Traversal

提供先序遍历,构造二叉树,先序遍历的第一个元素是 root 节点,分别遍历之后元素,如果元素比 root 小,则记录到root 左子树中,反之记录到 root 右子树中,递归构造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
leftList = []
rightList = []
root = TreeNode(preorder[0])
for num in preorder[1:]:
if num < preorder[0]:
leftList.append(num)
elif num > preorder[0]:
rightList.append(num)
root.left = self.bstFromPreorder(leftList)
root.right = self.bstFromPreorder(rightList)
return root