队列和栈

队列

1. 岛屿数量

给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
11110
11010
11000
00000

输出: 1

输入:
11000
11000
00100
00011

输出: 3

实现思路
使用队列都能解决,两者的思路是一样的,每次遍历将相连的陆地全部感染(将值置为0),而每次的第一次感染的时候岛屿数量加一。

BFS实现

BFS 用的是队列:

  • 遍历整块大陆,横竖遍历都可以
  • 第一次碰到陆地的时候,就知道这是一个岛屿了,所以将这块陆地放入到探险队列,岛屿数量加一
  • 然后我们将这块岛屿的陆地探索完,每一次将这块陆地周围(上下左右)的陆地放入队列,然后将这块陆地标记为已探索(这里直接将值置为0)
  • 当探险队列为空的时候,表示这块岛屿的陆地全部被探索完毕,我们继续下一个陆地探索
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
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if len(grid) == 0:
return 0
high = len(grid)
width = len(grid[0])
ans = 0
for i in range(high):
for j in range(width):
if grid[i][j] == '1':
ans += 1
pos = []
pos.append([i, j])
while(len(pos)):
x, y = pos.pop()
grid[x][y] = '0'
if (x + 1 < high and grid[x + 1][y] == '1'):
pos.append([x + 1, y])
grid[x + 1][y] = '0'
if (y + 1 < width and grid[x][y + 1] == '1'):
pos.append([x, y + 1])
grid[x][y + 1] = '0'
if (x - 1 > -1 and grid[x - 1][y] == '1'):
pos.append([x - 1, y])
grid[x - 1][y] = '0'
if (y - 1 > -1 and grid[x][y - 1] == '1'):
pos.append([x, y - 1])
grid[x][y - 1] = '0'
return ans

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
res = 0
rows = len(grid) # 计算网格的行数
if rows == 0:
return res
cols = len(grid[0]) # 计算网格的列数
if cols == 0:
return res

# 开始遍历每一个元素
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1': # 如果当前元素是陆地
res += 1
self.dfs(grid, i, j) # 递归查找这块陆地相连的陆地,并将其变为0
return res

def dfs(self, grid, i, j):
grid[i][j] = '0'
# 判断grid[i][j]上边的元素
if i > 0 and grid[i - 1][j] == '1':
self.dfs(grid, i-1, j)
# 判断grid[i][j]左边的元素
if j > 0 and grid[i][j - 1] == '1':
self.dfs(grid, i, j-1)
# 判断grid[i][j]下边边的元素
if i < len(grid) - 1 and grid[i + 1][j] == '1':
self.dfs(grid, i+1, j)
# 判断grid[i][j]右边的元素
if j < len(grid[0]) - 1 and grid[i][j + 1] == '1':
self.dfs(grid, i, j+1)

class Solution:
def numIslands(self, g: List[List[str]]) -> int:
m=len(g)
if m==0:
return 0
n=len(g[0])

g=[['0']*n]+g+[['0']*n]

for i in range(m+2):
g[i]=['0']+g[i]+['0']

def f(i,j):
g[i][j]='0'
if g[i-1][j]=='1':f(i-1,j)
if g[i+1][j]=='1':f(i+1,j)
if g[i][j+1]=='1':f(i,j+1)
if g[i][j-1]=='1':f(i,j-1)

k=0
for i in range(1,m+1):
for j in range(1,n+1):
if g[i][j]=='1':
k+=1
f(i,j)

return k

2. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。

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
输入:deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出:6
解释:
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的,
因为当拨动到 "0102" 时这个锁就会被锁定。

输入: deadends = ["8888"], target = "0009"
输出:1
解释:
把最后一位反向旋转一次即可 "0000" -> "0009"。

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出:-1
解释:
无法旋转到目标数字且不被锁定。

输入: deadends = ["0000"], target = "8888"
输出:-1

提示:

死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

实现思路
使用BFS来实现,需要一个队列和visited集合,通过step保存寻找了多少步,使用size保存当前有多少步可以搜索,使用j来遍历4个旋钮,使用看k = -, 1来表示正向搜索和反向搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
deadset = set(deadends)
if '0000' in deadset:
return -1

que = collections.deque()
que.append(['0000', 0])
cnt = 0

while que:
node, cnt = que.popleft()
if node == target:
return cnt

for i in range(4):
for j in range(-1, 2, 2):
next_node = node[:i] + str((int(node[i]) + j) % 10) + node[i + 1:]
if next_node not in deadset:
deadset.add(next_node) # 避免下次重复
que.append([next_node, cnt+1])
return -1

3. 完全平方数

给定正整数n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得他们的和等于n,你需要让组成完全平方和的个数最少。

1
2
3
4
5
6
7
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

实现思路
方法一:
利用队列和BFS的方法,队列以 [(当前节点, 步数)] 的方式存放,利用广度优先遍历最先到达终点的路线一定最短,从而得到最短步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def numSquares(self, n: int) -> int:
que = []
que.append([n, 0])
visited = [False for _ in range(n + 1)]
visited[n] = True
while que:
node, step = que.pop(0)
i = 1
temp = node - i**2
while temp >= 0:
if temp == 0:
return step + 1
if not visited[temp]:
que.append([temp, step + 1])
visited[temp] = True
i += 1
temp = node - i**2

方法二:
四平方和定理
拉格朗日四平方和定理:任何一个正整数都可以表示成为不超过四个整数的平方之和,满足四平方和定理的数n(这里要满足由四个数构成,小于四个不行),必定满足 n = 4^a(8*b + 7)
我们首先将输入的n迅速缩小。然后我们再判断,这个缩小后的数是否可以通过两个平方数的和或一个平方数组成,不能的话我们返回3,能的话我们返回平方数的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
#四平方定理
#Lagrange's Four Square theorem:
# 每个正整数均可表示为4个整数(包括0)的平方和,
# 所以只有四种可能结果,即[1,2,3,4]
#Legendre's three-square theorem:
# 非4^a(8b+7)型的正整数都可以用三个整数的平方和表示,
# 所以对于可以写成4^a(8b+7)类型的n,其结果只能为4
#https://blog.csdn.net/qq_17550379/article/details/80875782
def numSquares(self, n):
while n%4 == 0:
n /= 4
if n % 8== 7:
return 4

a = 0
while a*a <= n:
b = int((n- a*a)**0.5)
if a*a + b*b == n:
return (not not a) + (not not b) #新技能,get!!!
a += 1

return 3

  1. 每日温度
    根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

实现思路
最简单的当然是双层循环,但是这个会导致时间过长而超时,所以可以使用一个栈结构来存放天数的索引,然后比较当前的气温和之前天的温度,从而修改之前天的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
# n = len(T)
# res = [0] * n
# for i in range(n):
# cnt = 0
# for j in range(i+1, n):
# if T[i] < T[j]:
# res[i] = cnt + 1
# break
# cnt += 1
# return res

# 上面的双层循环会导致超时,所以使用栈结构来解决
n = len(T)
stack = []
res = [0 for _ in range(n)]

for i in range(n):
while len(stack) != 0 and T[i] > T[stack[-1]]:
top = stack.pop()
res[top] = i - top
stack.append(i)
return res

2. 逆波兰表达式

根据逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

实现思路
逆波兰表达式是经典的 四则运算问题的解法,我们需要创建一个栈结构,存储数字,当碰到运算符的时候,每次弹出两个数进行运算,将结果再压入栈中。

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
32
33
34
35
36
37
38
39
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack=[]
if not tokens:
return 0
for c in tokens:
if c in ('+','-','*','/'):
num=int(stack.pop())
if c=='+':
stack[-1]+=num
elif c=='-':
stack[-1]-=num
if c=='*':
stack[-1]*=num
if c=='/':
stack[-1]=int(stack[-1]/num)
else:
stack.append(int(c))
return stack[-1]

class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
sign = ['+', '-', '*', '/']
for char in tokens:
if char not in sign:
stack.append(int(char))
else:
top_1 = stack.pop()
top_2 = stack.pop()
if char == '+':
stack.append(top_2 + top_1)
elif char == '-':
stack.append(top_2 - top_1)
elif char == '*':
stack.append(top_2 * top_1)
elif char == '/':
stack.append(int(top_2 / top_1))
return stack.pop()

栈和深度优先搜索

1. 克隆图

给定无向图连通图中的一个节点的引用,返回改图的神深拷贝(克隆),图中的每个节点都包含它的值 valint)和其邻居的列表(list[Node])。

1
2
3
4
5
6
7
8
输入:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释:
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。

提示:

  • 节点数介于 1 到 100 之间。
  • 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
  • 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
  • 必须将给定节点的拷贝作为对克隆图的引用返回。

实现思路
利用一个哈希表,键存储遍历到的店的val,值存储这个点的地址,如果遍历到的点在哈希表中已经存在,说明已经复制过了,直接返回,如果没有,那么就复制当前节点并添加到哈希表中,然后遍历当前节点的neighbors添加到新建节点的neighbors

方法一:
BFS广度优先搜索,建立队列,循环找到的node内所有neighbor,并且将所有的neighbor设为visited,以此循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
# Definition for a Node.
class Node:
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None

new_node = Node(node.val, [])
visited = {node:new_node}
que = [node]

while que:
now = que.pop(0)
for neighbor in now.neighbors:
if neighbor not in visited:
visited[neighbor] = Node(neighbor.val, [])
que.append(neighbor)
visited[now].neighbors.append(visited[neighbor])
return new_node

方法二:
DFS深度优先遍历,直接遍历一个neighbor内部所有的neighbor情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
# Definition for a Node.
class Node:
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None

new = Node(node.val, [])
visited = {node:new}
self.dfs(visited, node)
return new

def dfs(self, visited, node):
for i in node.neighbors:
if i in visited:
visited[i] = Node(i.val, [])
self.dfs(visited, i)
visited[node].neighbors.append(visited[i])

2. 目标和

给定一个非副整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

1
2
3
4
5
6
7
8
9
10
11
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

注意:

  • 数组的长度不会超过20,并且数组中的值全为正数。
  • 初始的数组的和不会超过1000。
  • 保证返回的最终结果为32位整数。

实现思路
使用动态规划,原题转化为一个正子集和一个负子集,使得总和为target
我们假设P是正子集,N是负子集 例如: 假设nums = [1, 2, 3, 4, 5],target = 3,一个可能的解决方案是+1-2+3-4+5 = 3 这里正子集P = [1, 3, 5]和负子集N = [2, 4]

那么我们可以将其转换成求子集和的问题。

1
2
3
             	  sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)

因此,原来的问题已转化为一个求子集的和问题: 找到nums的一个子集 P,使得sum(P PP)= (target + sum(nums)) / 2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
sum_nums = sum(nums)
if sum_nums < S or (S + sum_nums) % 2 != 0:
return 0

p = (S + sum_nums) >> 1
mem = [0 for _ in range(p + 1)]
mem[0] = 1
for num in nums:
for i in range(p, num - 1, -1):
mem[i] += mem[i - num]
return mem[p]