笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 117

https://leetcode.com/contest/weekly-contest-117

Univalued Binary Tree

原题地址 https://leetcode.com/contest/weekly-contest-117/problems/univalued-binary-tree/

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

1
2
Input: [1,1,1,1,1,null,1]
Output: true

Example 2:

1
2
Input: [2,2,2,5,2]
Output: false

Note:

  1. The number of nodes in the given tree will be in the range [1, 100].
  2. Each node’s value will be an integer in the range [0, 99].

BFS遍历所有值,找到与根结点不同的返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None


class Solution(object):
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
v = root.val
q = [root]

for i in q:
if i.val != v:
return False
if i.left:
q.append(i.left)
if i.right:
q.append(i.right)
return True

Numbers With Same Consecutive Differences

原题地址 https://leetcode.com/contest/weekly-contest-117/problems/numbers-with-same-consecutive-differences/

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

1
2
3
Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

1
2
Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

  1. 1 <= N <= 9
  2. 0 <= K <= 9

N=1时,无论K取多少,连续位之间的绝对差为K始终成立,因此0-9所有个位数都成立。N每增加1,需要对N-1时成立的所有结果,添加满足连续位差值的最后一位,该位取值如果还在0-9之间则放入新的结果中,如果第一位为0则不需要考虑,直接舍弃。需要注意如果K=0时只需要考虑一种添加末位的情况,避免重复计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def numsSameConsecDiff(self, N, K):
"""
:type N: int
:type K: int
:rtype: List[int]
"""
res = list(range(10))
for i in range(1, N):
new_res = []
for n in res:
if n / 10**(i - 1):
if 0 <= n % 10 - K <= 9:
new_res.append(n * 10 + n % 10 - K)
if 0 <= n % 10 + K <= 9 and K > 0:
new_res.append(n * 10 + n % 10 + K)
res = list(new_res)
return res

Vowel Spellchecker

原题地址 https://leetcode.com/contest/weekly-contest-117/problems/vowel-spellchecker/

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

  • Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
    • Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
    • Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
    • Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
  • Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
    • Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
    • Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
    • Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

  • When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
  • When the query matches a word up to capitlization, you should return the first such match in the wordlist.
  • When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
  • If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

1
2
Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Note:

  1. 1 <= wordlist.length <= 5000
  2. 1 <= queries.length <= 5000
  3. 1 <= wordlist[i].length <= 7
  4. 1 <= queries[i].length <= 7
  5. All strings in wordlist and queries consist only of english letters.

注意匹配的优先顺序,先找完全一致的,再找大小写不一致的里面最先出现的,最后找大小写不敏感且元音可以替代的里面最先出现的。因此可以建立3个hash表(dict)来一次匹配,第一次存放完全相同的词,第二个存放所有字母小写的词中最先出现的原词,第三个存放把元音位置改为通配符‘*’的小写单词匹配中最先出现的,注意这里用倒序遍历wordlist就是为了保证每个记录的值是最先出现的原词。对于queries出现的所有词都顺序寻找是否在这3个字典中出现过,第一次找到返回的值就是结果,如果都找不到返回""

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def spellchecker(self, wordlist, queries):
"""
:type wordlist: List[str]
:type queries: List[str]
:rtype: List[str]
"""
exact_words = {w: w for w in wordlist}
caps = {w.lower(): w for w in wordlist[::-1]}
delete_vowels = {re.sub("[aeiou]", "*", w.lower()): w for w in wordlist[::-1]}
return [exact_words.get(w) or caps.get(w.lower()) or delete_vowels.get(re.sub("[aeiou]", "*", w.lower())) or "" for w in queries]

Binary Tree Cameras

原题地址 https://leetcode.com/contest/weekly-contest-117/problems/binary-tree-cameras/

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

1
2
3
Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

1
2
3
Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

  1. The number of nodes in the given tree will be in the range [1, 1000].
  2. Every node has value 0.

从底层开始向上安装摄像头,可以保证需要的数量最少。

每个结点一共可能有3个状态:装了摄像头(2),没装摄像头但已经被其他结点的监控范围覆盖(1),没装摄像头且没被监控覆盖(0)。空结点属于没1的情况,实际上是不需要被监控。然后从下往上确定每个结点的状态

  • 如果一个结点的两个子结点有一个还没被监控覆盖,那么这个结点就需要装上摄像头,成为2
  • 如果两个子结点有一个装有摄像头,另一个也不需要再装摄像头来覆盖(12),那么该结点已经被监控覆盖,标记为1
  • 如果两个子结点都已经被它们的子结点的摄像头覆盖监控了,那么当前结点不需要装监控来向下覆盖,但也没被覆盖,标记为0

用DFS可以完成以上顺序的遍历,最后检查根结点是否已经被覆盖,如果没有则还需要在根结点上安装一个摄像头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None


class Solution(object):
def minCameraCover(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = 0

def dfs(root): # 1: no need 2: has a camera 0: no camera
if not root:
return 1
l, r = dfs(root.left), dfs(root.right)
if l == 0 or r == 0:
self.res += 1
return 2
elif l == 2 or r == 2:
return 1
else:
return 0

if dfs(root) == 0:
self.res += 1
return self.res