leecode刷题笔记（一）

2020-06-18

根据不同的解答方法，总结leecode不同题型。

方法一：队列

队列是一种先进先出的数据结构，称为 First In First Out，简称 FIFO（队尾进，队首出）。

python实现

Python标准库中包含了四种队列，分别是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque。

区别：collections.deque在数据结构层面实现了队列，但是并没有应用场景方面的支持，可以看做是一个基础的数据结构。queue模块实现了面向多生产线程、多消费线程的队列，asyncio.queue模块则实现了面向多生产协程、多消费协程的队列，而multiprocessing.queue模块实现了面向多成产进程、多消费进程的队列。

具体对比：https://cloud.tencent.com/developer/article/1355340

具体用法（queue.Queue()）：

from queue import Queue

q = Queue()

for i in range(2):
    q.put(i)

while not q.empty():
    print(q.get())

（collections.deque()）：

deq = deque()

for i in range(2):
    deq.append(i)

while deq:
    print(deq.popleft())

应用

队列经常用在图的广度优先搜索（BFS）中，具体步骤：

class Solution(object):
    def BFS(self):
	# 1.使用 queue.Queue 初始化队列
	# 2.选择合适的根节点压入队列

	# 3.使用 wile 进入队列循环，直到搜索完毕
	# {
	#   4.取出一个节点
	#   5.放入这个节点周围的节点
	# }

200. 岛屿的个数

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例：

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解答：

from queue import Queue

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        try:
            m,n = len(grid),len(grid[0])
            num = 0
            around = ((1,0),(-1,0),(0,1),(0,-1))
        except:
            return 0

        def bfs(i,j):
            q = Queue()
            q.put((i,j))
            grid[i][j] = '0'
            while not q.empty():
                a,b = q.get()
                for a2,b2 in around:
                    a2 += a; b2+=b
                    if 0 <= a2 < m and 0 <= b2 < n and grid[a2][b2]=='1':
                        q.put((a2,b2))
                        grid[a2][b2] = '0'

        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    bfs(i,j)
                    num += 1
        return num

总结：

首先用try判断是否空list
对于每一个非0元素，采用bfs广度遍历周边所有非0元素，并赋值为0，并计数
bfs中，每一个非0元素，先进入队列，并赋值为0；

若队列非空，队首元素可以出队列，并把周边非0元素进入队列，并赋值为0。

Tips:

之前尝试用max(a2, 0)不如判断省时间。

279. 完全平方数

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

示例：

1
2
3

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

解答：

from queue import Queue

class Solution:
    def numSquares(self, n: int) -> int:
        if n==1:
            return 1
        
        s = []
        visit = set()
        for i in range(1,int(math.sqrt(n))+1):
            s.append(i**2)
        if n in s:
            return 1
        
        q = Queue()
        q.put((n,1))
        while not q.empty():
            a,b = q.get()
            for i in s:
                if a-i == 0:
                    return b
                if a-i not in visit and a-i>0:
                    q.put((a-i,b+1))
                    visit.add(a-i)

解答（使用deque）：

from collections import deque

class Solution:
    def numSquares(self, n: int) -> int:
        
        s = []
        visit = set()
        for i in range(1,int(math.sqrt(n))+1):
            s.append(i**2)
        if n in s:
            return 1
        
        deq = deque()
        deq.append((n,1))
        while deq:
            a,b = deq.popleft()
            for i in s:
                if a-i == 0:
                    return b
                if a-i not in visit and a-i>0:
                    deq.append((a-i,b+1))
                    visit.add(a-i)

Tips:

deque好像快一些

752. 打开转盘锁

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

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

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

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

示例：

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

解答：

from queue import Queue

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        d = set(deadends)
        nums = 0
        if "0000" in d:
            return -1
        if '0000' == target:
            return 0
        q = Queue()
        q.put(('0000',nums))
        d.add('0000')
        while not q.empty():
            k,k2 = q.get()
            
            for x in (-1,1):
                i1 = (int(k[0])+x)%10
                
                if str(i1)+k[1]+k[2]+k[3] == target:
                    return k2+1
                if str(i1)+k[1]+k[2]+k[3] not in d:
                    q.put((str(i1)+k[1]+k[2]+k[3],k2+1))
                    d.add(str(i1)+k[1]+k[2]+k[3])
                
                i1 = (int(k[1])+x)%10
                if k[0]+str(i1)+k[2]+k[3] == target:
                    return k2+1
                if k[0]+str(i1)+k[2]+k[3] not in d:
                    q.put((k[0]+str(i1)+k[2]+k[3],k2+1))
                    d.add(k[0]+str(i1)+k[2]+k[3])
                
                i1 = (int(k[2])+x)%10
                if k[0]+k[1]+str(i1)+k[3] == target:
                    return k2+1
                if k[0]+k[1]+str(i1)+k[3] not in d:
                    q.put((k[0]+k[1]+str(i1)+k[3],k2+1))
                    d.add(k[0]+k[1]+str(i1)+k[3])
                
                i1 = (int(k[3])+x)%10
                if k[0]+k[1]+k[2]+str(i1) == target:
                    return k2+1
                if k[0]+k[1]+k[2]+str(i1) not in d:
                    q.put((k[0]+k[1]+k[2]+str(i1),k2+1))
                    d.add(k[0]+k[1]+k[2]+str(i1))
        return -1

Tips:

想要把字符串和次数同时加入队列，应该使用tuple整合起来
可以用如下代码来求得更改之后的密码：

1	cur = node[:i] + str((int(node[i]) + add) % 10) + node[i+1:]

总结

队列步骤：

初始化队列
判断根节点，入队
如果队列非空，循环：
- 队首元素出队，并获取。
- 广度遍历图
  - 如果是满足条件的问题，此判断是否满足条件
  - 元素入队
  - 元素标记，set.append()