目錄
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 count2617.網格圖中最少訪問的格子數?
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 ans1702.修改后的最大二進制字符串
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
