备战菊厂笔试2-BFS记忆化MLE?用Set去重-Set会TLE？用SortedSet剪枝

目录

200.岛屿数量

不用getnei，直接在dfs判断，去掉解包

如果害怕栈溢出那么可以用bfs

2617.网格图中最少访问的格子数 

注意特判！

MLE主要是因为vis占用的内存过大

用SortedSet有序剪枝

什么是SortedSet？

基本性质

导入

常用操作

初始化

添加与删除

索引（因为有序的所以支持bisect，类似于list）

范围查询 irange( , ) !!!

我们可以用 list + bisect 实现类似SortedSet

本题题解

官方题解

单调栈优化DP

线段树

1702.修改后的最大二进制字符串

---

200.岛屿数量

很明显的DFS连通性判断 

遍历地图找1，然后开始传染（如果不想修改原本数据集可以用vis存储已访问数据）

class Solution:def numIslands(self, grid):lx=len(grid)ly=len(grid[0])d=[(0,1),(0,-1),(1,0),(-1,0)]def get_nei(x,y):neis=[]for dx,dy in d:nx,ny=x+dx,y+dyif 0<=nx<lx and 0<=ny<ly:neis.append((nx,ny))#tuple方便解包return neisdef dfs(x,y):if grid[x][y]=='1':grid[x][y]='0'for nx,ny in get_nei(x,y):dfs(nx,ny)#传染0ans=0for i in range(lx):for j in range(ly):if grid[i][j]=='1':dfs(i,j)ans+=1return ansif __name__=='__main__':grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]sol=Solution()#创建对象ans=sol.numIslands(grid)print(ans)

但是这样只击败35%的解法

不用getnei，直接在dfs判断，去掉解包

去掉getnei，去掉解包（解包的在数据很多时会影响时间复杂度）

def numIslands(self, grid):if not grid:return 0rows, cols = len(grid), len(grid[0])count = 0def dfs(r, c):# 边界条件或已访问过（水域）if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':return# 标记为已访问grid[r][c] = '0'# 直接检查四个方向dfs(r+1, c)dfs(r-1, c)dfs(r, c+1)dfs(r, c-1)for i in range(rows):for j in range(cols):if grid[i][j] == '1':count += 1dfs(i, j)return count

如果害怕栈溢出那么可以用bfs

from collections import dequedef numIslands(self, grid):if not grid:return 0rows, cols = len(grid), len(grid[0])count = 0for i in range(rows):for j in range(cols):if grid[i][j] == '1':count += 1grid[i][j] = '0'  # 标记为已访问# BFSqueue = deque([(i, j)])while queue:r, c = queue.popleft()directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]for dr, dc in directions:nr, nc = r + dr, c + dcif 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':queue.append((nr, nc))grid[nr][nc] = '0'  # 标记为已访问return count

2617.网格图中最少访问的格子数 

2617. 网格图中最少访问的格子数

分析题目，对于x，y点可以向右或者向下，其行动能力为该节点的权值 

我刚开始还想着用DFS表示着来做，但是这复杂度也太高了！

得利用BFS逐层拓展的性质，第一次碰到就是最短

得vis记忆化：之前层走的肯定是先到的

from collections import dequeclass Solution:def minimumVisitedCells(self, grid):if grid == [[0]]:return 1lx = len(grid)ly = len(grid[0])visited = [[False] * ly for _ in range(lx)]queue = deque()queue.append((0, 0, 1))  # (x, y, 当前步数)while queue:x, y, step = queue.popleft()if visited[x][y]:continuevisited[x][y] = True# 尝试向下跳for i in range(1, grid[x][y] + 1):nx = x + iif nx >= lx:breakif not visited[nx][y]:if nx == lx - 1 and y == ly - 1:return step + 1queue.append((nx, y, step + 1))# 尝试向右跳for i in range(1, grid[x][y] + 1):ny = y + iif ny >= ly:breakif not visited[x][ny]:if x == lx - 1 and ny == ly - 1:return step + 1queue.append((x, ny, step + 1))return -1

注意：得在类外面导入库!

注意特判！

起点就是终点的时候不是输出-1，而是输出1

        if grid==[[0]]:return 1

结果后面MLE了

（这道题不用dijkstra，因为每步代价是一样的）

MLE主要是因为vis占用的内存过大

用set去重：

用两个二维数组，一个存储每一行未被访问的列，另一个存储每一列未被访问的行

那么就从原来的加入到 vis 变成从 set remove

from collections import dequeclass Solution:def minimumVisitedCells(self, grid):if grid == [[0]]:return 1lx = len(grid)ly = len(grid[0])#每一行未被访问的列lie=[set(range(ly)) for i in range(lx)]hang=[set(range(lx)) for i in range(ly)]#每一列未被访问的行lie[0].remove(0)hang[0].remove(0)queue=deque()queue.append((0,0,1))while queue:x,y,step=queue.popleft()for i in range(1,grid[x][y]+1):nx=x+iif nx>=lx:breakif nx in hang[y]:if nx==lx-1 and y==ly-1:return step+1queue.append((nx,y,step+1))hang[y].remove(nx)for i in range(1,grid[x][y]+1):ny=y+iif ny>=ly:breakif ny in lie[x]:if x==lx-1 and ny==ly-1:return step+1queue.append((x,ny,step+1))lie[x].remove(ny)return -1

但是这样TLE了

用SortedSet有序剪枝

什么是SortedSet？

和set类似，但会保持元素始终按顺序排列，支持范围查询和有序操作，非常适合搜索剪枝优化、模拟平衡树等

基本性质

和set一样不允许重复元素

元素自动排序（默认升序）

支持快速：

        插入和删除

        查找、区间查询、二分查找

导入

从 sortedcontainers 排序容器导入

from sortedcontainers import SortedSet  # 第三方库，需pip安装

常用操作

初始化

ss=SortedSet([1,9,2,8])ss=SortedSet(列表名)

添加与删除

s.add( 元素值 )s.discard( 元素值 )

索引（因为有序的所以支持bisect，类似于list）

print(s[0])     # 输出最小值（1）
print(s[-1])    # 输出最大值（9）
print(s.bisect_left(5))  # 2，表示第一个 ≥5 的位置
print(s.bisect_right(5)) # 3，表示第一个 >5 的位置

范围查询 irange( , ) !!!

# 获取大于等于 2 且小于等于 7 的所有元素（闭区间）
print(list(s.irange(2, 7)))  # [5, 7]
# 获取大于 3 的元素（开区间）
print(list(s.irange(3, 9, inclusive=(False, True)))  # [5, 7, 9]

所以这题里面我们可以用 irange快速找到可以跳远的位置

我们可以用 list + bisect 实现类似SortedSet

就是要注意列表的查重

本题题解

from collections import deque
from bisect import bisect_right
from sortedcontainers import SortedSet  # 第三方库，需安装class Solution:def minimumVisitedCells(self, grid):if grid == [[0]]:return 1m, n = len(grid), len(grid[0])row = [SortedSet(range(n)) for _ in range(m)]col = [SortedSet(range(m)) for _ in range(n)]queue = deque([(0, 0, 1)])row[0].discard(0)col[0].discard(0)while queue:x, y, step = queue.popleft()max_jump = grid[x][y]# 向右推进candidates = list(row[x].irange(y + 1, y + max_jump))for ny in candidates:if x == m - 1 and ny == n - 1:return step + 1queue.append((x, ny, step + 1))row[x].discard(ny)# 向下推进candidates = list(col[y].irange(x + 1, x + max_jump))for nx in candidates:if nx == m - 1 and y == n - 1:return step + 1queue.append((nx, y, step + 1))col[y].discard(nx)return -1

官方题解

和Dijkstra一样都贪心先处理小的-最小堆

class Solution:def minimumVisitedCells(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])dist = [[-1] * n for _ in range(m)]dist[0][0] = 1row, col = [[] for _ in range(m)], [[] for _ in range(n)]def update(x: int, y: int) -> int:return y if x == -1 or y < x else xfor i in range(m):for j in range(n):while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:heapq.heappop(row[i])if row[i]:dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:heapq.heappop(col[j])if col[j]:dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)if dist[i][j] != -1:heapq.heappush(row[i], (dist[i][j], j))heapq.heappush(col[j], (dist[i][j], i))return dist[m - 1][n - 1]

单调栈优化DP

class Solution:def minimumVisitedCells(self, grid: List[List[int]]) -> int:m, n = len(grid), len(grid[0])col_stacks = [[] for _ in range(n)]  # 每列的单调栈for i in range(m - 1, -1, -1):row_st = []  # 当前行的单调栈for j in range(n - 1, -1, -1):g = grid[i][j]col_st = col_stacks[j]mn = inf if i < m - 1 or j < n - 1 else 1if g:  # 可以向右/向下跳# 在单调栈上二分查找最优转移来源k = bisect_left(row_st, -(j + g), key=lambda p: p[1])if k < len(row_st):mn = row_st[k][0] + 1k = bisect_left(col_st, -(i + g), key=lambda p: p[1])if k < len(col_st):mn = min(mn, col_st[k][0] + 1)if mn < inf:# 插入单调栈while row_st and mn <= row_st[-1][0]:row_st.pop()row_st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_leftwhile col_st and mn <= col_st[-1][0]:col_st.pop()col_st.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_leftreturn mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]

线段树

区间查询+单点更新

import sys
sys.setrecursionlimit(1 << 25)INF = float('inf')class SegmentTree:def __init__(self, size):self.N = sizeself.tree = [INF] * (4 * size)def update(self, o, l, r, idx, val):if l == r:self.tree[o] = valreturnm = (l + r) // 2if idx <= m:self.update(o * 2, l, m, idx, val)else:self.update(o * 2 + 1, m + 1, r, idx, val)self.tree[o] = min(self.tree[o * 2], self.tree[o * 2 + 1])def query(self, o, l, r, L, R):if L > R:return INFif L <= l and r <= R:return self.tree[o]m = (l + r) // 2res = INFif L <= m:res = min(res, self.query(o * 2, l, m, L, R))if R > m:res = min(res, self.query(o * 2 + 1, m + 1, r, L, R))return resclass Solution:def minimumVisitedCells(self, grid):m, n = len(grid), len(grid[0])minl = [SegmentTree(m) for _ in range(n)]  # 每一列的线段树ans = INFfor i in reversed(range(m)):minh = SegmentTree(n)  # 当前行的线段树for j in reversed(range(n)):mn = INFg = grid[i][j]if i == m - 1 and j == n - 1:mn = 1if j + 1 <= min(j + g, n - 1):mn = min(mn, minh.query(1, 1, n, j + 2, min(j + g + 1, n)) + 1)if i + 1 <= min(i + g, m - 1):mn = min(mn, minl[j].query(1, 1, m, i + 2, min(i + g + 1, m)) + 1)if mn < INF:minh.update(1, 1, n, j + 1, mn)minl[j].update(1, 1, m, i + 1, mn)if i == 0 and j == 0:ans = mnreturn -1 if ans == INF else ans

1702.修改后的最大二进制字符串

1702. 修改后的最大二进制字符串

猜了一波然后错了 

        '''猜错了！l=len(binary)if binary=='01':return '01'if int(binary)==0:s='1'*(l-1)+'0'return sif sum(map(int,list(binary)))==l:return binaryx=int(l/2)s='1'*x+'0'+'1'*(l-x-1)return s'''

然后我开始观察这两个操作对二进制串的影响

操作1.将00转为10，可以变大

操作2.将10转为01，这会变小啊？

所以操作2存在的意义就是为了操作1 :将0往前推，从而产生操作1的条件

于是自以为是的我就直接把0全往开头放然后进行操作1

        '''c0=binary.count('0')#特判！！????if c0==1:return binaryif c0==0:return binaryc1=binary.count('1')s='1'*(c0-1)+'0'+'1'*c1return s'''

但是有没有一种可能原本前面1呆的好好的被你往后推了？

比如111000变成000111变成

        110111，明显变小了因为第三位的变化，所以这是明显不可取的

我们得从第一个0开始变

class Solution:def maximumBinaryString(self, binary: str) -> str:l=len(binary)c0=bianry.count('0')c1=binary.count('1')if c0==0:return binaryfor i in range(l):#找第一个0if binary[i]=='0':x=ibreakc12=c1-xs=x*'1'+'1'*(c0-1)+'0'+'1'*c12return s