947. 移除最多的同行或同列石头
from collections import defaultdict
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
edge = defaultdict(list)
for i, (x0, y0) in enumerate(stones):
for j, (x1, y1) in enumerate(stones):
if x0 == x1 or y0 == y1:
edge[i].append(j)
vis = set()
ans = 0
for i in range(len(stones)):
if i not in vis:
ans += 1
self.dfs(vis, edge, i)
return len(stones) - ans
def dfs(self, vis: set, edge, index):
vis.add(index)
for i in edge[index]:
if i not in vis:
self.dfs(vis, edge, i)1022. 从根到叶的二进制数之和
class Solution:
def __init__(self):
self.ans = 0
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
self.dfs(root, str(root.val))
return self.ans
def dfs(self, node: Optional[TreeNode], bin_s):
if node.right:
self.dfs(node.right, bin_s + str(node.right.val))
if node.left:
self.dfs(node.left, bin_s + str(node.left.val))
if not node.left and not node.right:
self.ans += int(bin_s, 2)2227. 加密解密字符串
将dictionary中字符串加密后保存，解密直接返回数量。
from collections import defaultdict
class Encrypter:
def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
self.keys_c_index = {keys[i]: i for i in range(len(keys))}
self.values = values
self.res_cnt = defaultdict(int)
for i in range(len(dictionary)):
self.res_cnt[self.encrypt(dictionary[i])] += 1
def encrypt(self, word1: str) -> str:
ans = ''
for i in range(len(word1)):
if word1[i] not in self.keys_c_index:
return ''
ans += self.values[self.keys_c_index[word1[i]]]
return ans
def decrypt(self, word2: str) -> int:
return self.res_cnt[word2]使用深度优先搜索正向解密超时
from collections import defaultdict
class Encrypter:
def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
self.keys_c_index = {keys[i]: i for i in range(len(keys))}
self.keys = keys
self.values_count = defaultdict(list)
for i in range(len(values)):
self.values_count[values[i]].append(i)
self.values = values
self.dictionary = set(dictionary)
def encrypt(self, word1: str) -> str:
ans = ''
for i in range(len(word1)):
ans += self.values[self.keys_c_index[word1[i]]]
return ans
def decrypt(self, word2: str) -> int:
ans = 0
exist = set()
def dfs(now_s, word):
nonlocal exist, ans
if not word:
if now_s not in exist and now_s in self.dictionary:
ans += 1
exist.add(now_s)
else:
tmp_s = word[:2]
for i in range(len(self.values_count[tmp_s])):
dfs(now_s + self.keys[self.values_count[tmp_s][i]], word[2:])
dfs('', word2)
return ans946. 验证栈序列
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
pointer = 0
for i in range(len(pushed)):
stack.append(pushed[i])
while stack and stack[-1] == popped[pointer]:
stack.pop()
pointer += 1
return not bool(stack)1638. 统计只差一个字符的子串数目
枚举
class Solution:
def countSubstrings(self, s: str, t: str) -> int:
ans = 0
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
length = j - i
for k in range(len(t) - length + 1):
if self.check(s[i:j], t[k:k + length]):
ans += 1
return ans
def check(self, s0, s1):
diff = 0
for i in range(len(s0)):
if s0[i] != s1[i]:
diff += 1
if diff >= 2:
return False
return True if diff == 1 else FalseLCR 063. 单词替换
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
sentence = sentence.split(' ')
dictionary.sort(key=lambda x: len(x))
for i in range(len(sentence)):
for j in range(len(dictionary)):
if sentence[i].startswith(dictionary[j]):
sentence[i] = dictionary[j]
break
return ' '.join(sentence)2295. 替换数组中的元素
方法一：处理operations
class Solution:
def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
m = {}
for i in range(len(operations) - 1, -1, -1):
m[operations[i][0]] = m.get(operations[i][1], operations[i][1])
return [m.get(num, num) for num in nums]方法二
处理nums，生成索引
class Solution:
def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
index_dict = {nums[i]: i for i in range(len(nums))}
for i in range(len(operations)):
index = index_dict[operations[i][0]]
nums[index] = operations[i][1]
index_dict.pop(operations[i][0])
index_dict[operations[i][1]] = index
return nums
Comments | NOTHING