记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

8/25 498. 对角线遍历

对角线有两种走法
一种斜向上stepx=-1,stepy=1
一种斜向下stepx=1,stepy=-1
更新当前位置x,y
如果x,y在矩阵内 则不需要改变行进方向
如果走出矩阵 则根据x,y位置进行对应更新
特殊判断左下 右上角落情况

def findDiagonalOrder(mat):""":type mat: List[List[int]]:rtype: List[int]"""m,n = len(mat),len(mat[0])ans = []x,y = 0,0sx,sy = -1,1for _ in range(m*n):ans.append(mat[x][y])curx,cury = x+sx,y+sychange = Trueif 0<=curx<m and 0<=cury<n:x = curxy = curychange = Falseelif 0<=curx<m:x +=1elif 0<=cury<n:y +=1else:if curx>0:y +=1if cury>0:x +=1if change:sx = -sxsy = -syreturn ans

---

8/26 3000. 对角线最长的矩形的面积

依次遍历

def areaOfMaxDiagonal(dimensions):""":type dimensions: List[List[int]]:rtype: int"""cur=0ans=0for x,y in dimensions:if x*x+y*y>=cur:if x*x+y*y==cur:ans=max(ans,x*y)else:ans=x*yreturn ans

---

8/27 3459. 最长 V 形对角线段的长度

记忆化搜索

def lenOfVDiagonal(grid):""":type grid: List[List[int]]:rtype: int"""steps=[(1,1),(1,-1),(-1,-1),(-1,1)]m,n=len(grid),len(grid[0])mem={}def dfs(x,y,d,turn,target):if (x,y,d,turn,target) in mem:return mem[(x,y,d,turn,target)]nx,ny=x+steps[d][0],y+steps[d][1]if nx<0 or ny<0 or nx>=m or ny>=n or grid[nx][ny]!=target:return 0maxstep = dfs(nx,ny,d,turn,2-target)if turn:maxstep = max(maxstep,dfs(nx,ny,(d+1)%4,False,2-target))mem[(x,y,d,turn,target)]=maxstep+1return maxstep+1ans=0for i in range(m):for j in range(n):if grid[i][j]==1:for d in range(4):ans=max(ans,dfs(i,j,d,True,2)+1)return ans

---

8/28 3446. 按对角线进行矩阵排序

获得每条对角线数值 排序

def sortMatrix(grid):""":type grid: List[List[int]]:rtype: List[List[int]]"""n=len(grid)for i in range(n):tmp=[grid[i+j][j] for j in range(n-i)]tmp.sort(reverse=True)for j in range(n-i):grid[i+j][j]=tmp[j]for j in range(1,n):tmp=[grid[i][j+i] for i in range(n-j)]tmp.sort()for i in range(n-j):grid[i][j+i]=tmp[i]return grid

---

8/29 3021. Alice 和 Bob 玩鲜花游戏

要摘完所有花 所以为了A赢 必须x+y为奇数

def flowerGame(n, m):""":type n: int:type m: int:rtype: int"""return m*n//2

---

8/30 36. 有效的数独

遍历横竖
每一个小格子

def isValidSudoku(board):""":type board: List[List[str]]:rtype: bool"""from collections import defaultdictfor i in range(9):heng,shu =defaultdict(int),defaultdict(int)for j in range(9):if heng[board[i][j]]>0:return Falseif shu[board[j][i]]>0:return Falseif board[i][j]!=".":heng[board[i][j]] = 1if board[j][i]!=".":shu[board[j][i]] = 1m = defaultdict(int)for i in range(3):for j in range(3):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1m = defaultdict(int)for i in range(3):for j in range(3,6):print(board)if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1 m = defaultdict(int)for i in range(3):for j in range(6,9):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1m = defaultdict(int)for i in range(3,6):for j in range(3):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1m = defaultdict(int)for i in range(3,6):for j in range(3,6):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1 m = defaultdict(int)for i in range(3,6):for j in range(6,9):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1m = defaultdict(int)for i in range(6,9):for j in range(3):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1m = defaultdict(int)for i in range(6,9):for j in range(3,6):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1 m = defaultdict(int)for i in range(6,9):for j in range(6,9):if m[board[i][j]]>0:return Falseif board[i][j]!=".":m[board[i][j]]=1return True

---

8/31 37. 解数独

rowset[i]维护第i行填入的数字
colset[j]维护第j行数字
boxset[i][j]维护i,j宫内数字
hp维护所有空位置 可以填的数字个数 从最少的可能数位置开始

def solveSudoku(board):""":type board: List[List[str]]:rtype: None Do not return anything, modify board in-place instead."""import heapqrowset=[set() for _ in range(9)]colset=[set() for _ in range(9)]boxset=[[set() for _ in range(3)]for _ in range(3)]eptpos=[]for i,row in enumerate(board):for j,b in enumerate(row):if b=='.':eptpos.append((i,j))else:x=int(b)rowset[i].add(x)colset[j].add(x)boxset[i//3][j//3].add(x)get_candidates = lambda i, j: 9 - len(rowset[i] | colset[j] | boxset[i // 3][j // 3])hp = [(get_candidates(i, j), i, j) for i, j in eptpos]heapq.heapify(hp)def dfs():if not hp:return True_,i,j=heapq.heappop(hp)candi=0for x in range(1,10):if x in rowset[i] or x in colset[j] or x in boxset[i//3][j//3]:continueboard[i][j]=str(x)rowset[i].add(x)colset[j].add(x)boxset[i//3][j//3].add(x)if dfs():return Truerowset[i].remove(x)colset[j].remove(x)boxset[i//3][j//3].remove(x)candi+=1heapq.heappush(hp,(candi,i,j))return Falsedfs()

---