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

---

6/19 1262. 可被三整除的最大和

被三整除余数有三种情况0,1,2
余数为0可以直接加入到结果
余数为1可以和余数为2的一一匹配加入到结果
分别考虑从中不选取最小的三个数的情况 lo,lt分别代表选取的数位置
如果选出个数差为3的倍数 说明选出来的数都可以加入到结果

def maxSumDivThree(nums):""":type nums: List[int]:rtype: int"""ones,twos=[],[]three = 0for num in nums:y = num%3if y==0:three += numelif y==1:ones.append(num)else:twos.append(num)ones.sort(reverse=True)twos.sort(reverse=True)ans = 0lone,ltwo=len(ones),len(twos)for lo in [lone-2,lone-1,lone]:if lo>=0:for lt in [ltwo-2,ltwo-1,ltwo]:if lt>=0 and (lo-lt)%3==0:ans = max(ans,sum(ones[:lo])+sum(twos[:lt]))    return ans+three

---

6/20 1595. 连通两组点的最小成本

第一组有size1个数 第二组有size2个数
用长度size2的二进制数s来表示第一组中某个数与第二组的连接状态
dp[i][s]表示第一组前i个点与第二组s的连接最小成本

def connectTwoGroups(cost):""":type cost: List[List[int]]:rtype: int"""size1,size2=len(cost),len(cost[0])m = 1<<size2dp=[[float("inf")]*m for _ in range(size1+1)]dp[0][0]=0for i in range(1,size1+1):for s in range(m):for k in range(size2):if s&(1<<k)==0:continuedp[i][s] = min(dp[i][s],dp[i][s^(1<<k)]+cost[i-1][k])dp[i][s] = min(dp[i][s],dp[i-1][s]+cost[i-1][k])dp[i][s] = min(dp[i][s],dp[i-1][s^(1<<k)]+cost[i-1][k])return dp[size1][m-1]

---

6/21 LCP 41. 黑白翻转棋

遍历每一个.位置 变成黑子后是否有可以翻转的白子
BFS 将可以翻转的白子加入队列中 依次判断

def flipChess( chessboard):""":type chessboard: List[str]:rtype: int"""n,m = len(chessboard),len(chessboard[0])step = [-1,0,1]def check(board,x,y,dx,dy):x+=dxy+=dywhile 0<=x<n and 0<=y<m:if board[x][y]=="X":return Trueelif board[x][y]==".":return Falsex+=dxy+=dyreturn Falsedef bfs(chessboard,i,j):board = [list(x) for x in chessboard]l = [(i,j)]board[i][j]="X"cnt = 0while l:tmp = []for x,y in l:for dx in step:for dy in step:if dx==dy==0:continueif check(board,x,y,dx,dy):nx,ny = x+dx,y+dywhile board[nx][ny]!="X":tmp.append((nx,ny))board[nx][ny]="X"nx+=dxny+=dycnt+=1l=tmpreturn cntans = 0for i in range(n):for j in range(m):if chessboard[i][j]==".":ans = max(ans,bfs(chessboard,i,j))return ans

---

6/22 面试题 16.19. 水域大小

dfs 注意对角线也算

def pondSizes(land):""":type land: List[List[int]]:rtype: List[int]"""step = [(0,1),(1,0),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]n = len(land)m = len(land[0])def dfs(x,y):land[x][y] = 1ans = 1for i,j in step:if 0<=x+i<n and 0<=y+j<m:if land[x+i][y+j]==0:ans += dfs(x+i,y+j)return ansret = []for i in range(n):for j in range(m):if land[i][j]==0:v = dfs(i,j)ret.append(v)ret.sort()return ret

---

6/23 2496. 数组中字符串的最大值

判断如果是数字 则转换为数字
否则取长度

def maximumValue(strs):""":type strs: List[str]:rtype: int"""ans = 0for s in strs:if s.isdigit():ans = max(ans,int(s))else:ans = max(ans,len(s))return ans

---

6/24 1659. 最大化网格幸福感

每个网格有 无人 内向 外向 三种状态使用0,1,2表示
每一行n格 可以用n位三进制表示状态
dfs(i,pre,inum,enum) 表示从i行开始上一行状态pre 还剩下inum个内向 enum个外向
最大幸福值 求dfs(0,0,inCount,exCount)
如果i=m 或者 inum=0 and enum=0 说明分配中结束 返回0
枚举当前行的状态0~3^n
ix[cur] 表示当前状态cur中内向人数
ex[cur] 表示当前状态cur中外向人数
f[cur] 表示状态cur中人的初始幸福值
g[pre][cur]表示两个相邻状态行的贡献

def getMaxGridHappiness(m, n, introvertsCount, extrovertsCount):""":type m: int:type n: int:type introvertsCount: int:type extrovertsCount: int:rtype: int"""mx = 3**nf = [0]*mxg = [[0]*mx for _ in range(mx)]h=[[0,0,0],[0,-60,-10],[0,-10,40]]bits=[[0]*n for _ in range(mx)]ix=[0]*mxex=[0]*mxmem = {}def dfs(i,pre,inum,enum):if (i,pre,inum,enum) in mem:return mem[(i,pre,inum,enum)]if i==m or (inum==0 and enum==0):mem[(i,pre,inum,enum)] = 0return 0ans = 0for cur in range(mx):if ix[cur]<=inum and ex[cur]<=enum:a = f[cur]+g[pre][cur]b = dfs(i+1,cur,inum-ix[cur],enum-ex[cur])ans = max(ans,a+b)mem[(i,pre,inum,enum)] = ansreturn ansfor i in range(mx):mask = ifor j in range(n):mask,x = divmod(mask, 3)bits[i][j] = xif x==1:ix[i]+=1f[i]+=120elif x==2:ex[i]+=1f[i]+=40if j:f[i]+=h[x][bits[i][j-1]]for i in range(mx):for j in range(mx):for k in range(n):g[i][j] += h[bits[i][k]][bits[j][k]]return dfs(0,0,introvertsCount,extrovertsCount)

---

6/25 1401. 圆和矩形是否有重叠

与圆心的距离如果小于等于半径 说明在圆内
在矩形中找一个点(x,y) 使得
a=|x-xCenter| b=|y-yCenter|
a^2+b2<=radius^2 则有重叠

def checkOverlap(radius, xCenter, yCenter, x1, y1, x2, y2):""":type radius: int:type xCenter: int:type yCenter: int:type x1: int:type y1: int:type x2: int:type y2: int:rtype: bool"""def check(i,j,k):if i<=k<=j:return 0return i-k if k<i else k-ja = check(x1,x2,xCenter)b = check(y1,y2,yCenter)return a**2+b**2<=radius**2

---