class Solution(object):

def exist(self, board, word):

m, n = len(board), len(board[0])

d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def dfs(x, y, word, board):

# 递归终止条件，全部搜索完成

if not word:

return True

# 记录字符，然后变换该字符，避免重用

c = board[x][y]

board[x][y] = '.'

# 遍历搜索四个方向的字符

for dx, dy in d:

nx, ny = x+dx, y+dy

if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == word[0] and dfs(nx, ny, word[1:], board):

return True

# 四个方向都不满足条件，回溯，返回False

board[x][y] = c

return False

# 遍历二维矩阵每个字符，深度优先搜索

for i in range(m):

for j in range(n):

# 有一条路径满足条件

if board[i][j] == word[0] and dfs(i, j, word[1:], board):

return True

# 全部不满足条件

return False

class WordDictionary(object):

def __init__(self):

from collections import defaultdict

self.d = defaultdict(list)

def addWord(self, word):

self.d[len(word)] += [word]

def search(self, word):

n = len(word)

for w in self.d[n]:

for i in range(n):

if word[i] == '.':

continue

if word[i] != w[i]:

break

else:

return True

return False

class WordDictionary(object):

def __init__(self):

# {'b': {'a': {'d': {'#': {}}}}, 'd': {'a': {'d': {'#': {}}}}, 'm': {'a': {'d': {'#': {}}}}}

self.lookup = {}

def addWord(self, word):

tree = self.lookup

for a in word:

tree = tree.setdefault(a, {})

tree["#"] = {}

def search(self, word):

def helper(word, tree):

# 递归终止条件

if not word:

# 搜索完最后一个字符

if "#" in tree:

return True

# 未搜索完

return False

# 如果字符是'.'，需要遍历判断每个字典树

if word[0] == ".":

for t in tree:

if helper(word[1:], tree[t]):

return True

# 如果字符在字典中，只需要判断该字符的字典树

elif word[0] in tree:

if helper(word[1:], tree[word[0]]):

return True

# 字符不在字典中

return False

return helper(word, self.lookup)

from collections import Counter

class Solution(object):

def topKFrequent(self, nums, k):

# {1: 3, 2: 2, 3: 1} → [(1, 3), (2, 2)]

return [item[0] for item in Counter(nums).most_common(k)]

s = Solution()

nums = [1,1,1,2,2,3]

k = 2

res = s.topKFrequent(nums, k)

print(res)

class Solution(object):

def eraseOverlapIntervals(self, intervals):

if not intervals:

return 0

intervals = sorted(intervals, key=lambda k: k[1])

end, count, n = intervals[0][1], 1, len(intervals)

for i in range(1, n):

if intervals[i][0] < end:

continue

count += 1

end = intervals[i][1]

return n-count

class Solution(object):

def updateMatrix(self, matrix):

m, n = len(matrix), len(matrix[0])

# 结果矩阵初始化为-1，表示未搜索

q, res = [], [[-1]*n for _ in range(m)]

d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 从值为0开始搜索，将其添加到队列

for i in range(m):

for j in range(n):

if matrix[i][j] == 0:

res[i][j] = 0

q += [(i, j)]

# 搜索四个方向

for x, y in q:

for dx, dy in d:

nx, ny = x + dx, y + dy

# 将未搜索的区域赋值，值为上个区域值加1，并将新区域添加到队列中继续搜素偶

if 0 <= nx < m and 0 <= ny < n and res[nx][ny] == -1:

res[nx][ny] = res[x][y] + 1

q += [(nx, ny)]

return res

class Solution(object):

def leastInterval(self, tasks, n):

d = {}

# 统计每个任务的次数，并按次数归类存放在字典中

for task in set(tasks):

count = tasks.count(task)

if count not in d:

d[count] = [task]

else:

d[count] += [task]

# 获取最大次数

max_count = max(d.keys())

# 计算最短时间

res = (max_count - 1) * (n + 1) + len(d[max_count])

# 当出现次数最多的任务中间的单位时间填满后，仍有其他次数小的任务需要执行

# 用上面的计算方法会使最短次数比原数组长度短，此时应返回原数组长度

if res < len(tasks):

return len(tasks)

return res

class Solution(object):

def shortestBridge(self, A):

m, n = len(A), len(A[0])

d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 深度优先搜索，将一片岛屿置为-1

def dfs(x, y):

A[x][y] = -1

for dx, dy in d:

nx, ny = x + dx, y + dy

if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 1:

dfs(nx, ny)

# 找到一个1，将其所在的A岛屿置为-1

flag = 0

for i in range(m):

for j in range(n):

if A[i][j] == 1:

dfs(i, j)

flag = 1

if flag:

break

if flag:

break

# 将B岛屿每个位置添加到队列中

q = []

for i in range(m):

for j in range(n):

if A[i][j] == 1:

q.append((i, j, 0))

# 广度优先搜索，B岛屿中某个位置先到达A岛屿，则返回其路径长度

while q:

x, y, r = q.pop(0)

for dx, dy in d:

nx, ny = x + dx, y + dy

if 0 <= nx < m and 0 <= ny < n:

if A[nx][ny] == 0:

A[nx][ny] = 1

q.append((nx, ny, r + 1))

if A[nx][ny] == -1:

return r

class Solution(object):

def deckRevealedIncreasing(self, deck):

# 将原数组倒序排序

deck.sort(reverse=True)

res = []

while deck:

# 如果新数组有元素，则将最后一个元素移到首位

if res:

res = [res[-1]] + res[:-1]

# 再插入新元素到首位

res.insert(0, deck.pop(0))

return res