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

---

6/24 503. 下一个更大元素 II

循环数组 拼接两个数组即可
单调栈保存下标 遇到栈顶小于当前值
则栈顶下标结果为当前值

def nextGreaterElements(nums):""":type nums: List[int]:rtype: List[int]"""n=len(nums)ans=[-1]*nst = []for i in range(2*n-1):while st and nums[st[-1]]<nums[i%n]:ans[st.pop()]=nums[i%n]st.append(i%n)return ans

---

6/25 2732. 找到矩阵中的好子集

将每一行看做一个二进制数
如果答案至少有一行 那么这一行都为0
如果答案至少两行 那么每一列最多一个1 这两行二进制and为0
如果答案至少3行 每一列最多为1 和两行相同
如果答案至少4行 每一列和不超过2
因为两行找不到答案说明任选两行至少存在一列这两行都为1 但其他两行必须为0
若要满足这个条件至少需要4列 但题目矩阵列数n<=5 所以不存在
只考虑答案为1行或2行的情况即可

def goodSubsetofBinaryMatrix(grid):""":type grid: List[List[int]]:rtype: List[int]"""m = {}for i,row in enumerate(grid):mask = 0for j,v in enumerate(row):mask |= v<<jif mask ==0:return [i]m[mask]=ifor x,i in m.items():for y,j in m.items():if (x&y)==0:return sorted([i,j])return []

---

6/26 2741. 特别的排列

长度<14 用一个最长14位的二进制数s 描述当前可以用的数值位置
dfs(s,i) 搜索当前集合s的情况下 选取i位置的数值放在当前位置的情况

def specialPerm(nums):""":type nums: List[int]:rtype: int"""MOD=10**9+7mem={}def dfs(s,i):if (s,i) in mem:return mem[(s,i)]if s==0:return 1res = 0pre = nums[i]for j,x in enumerate(nums):if s>>j &1 and(pre%x==0 or x%pre==0):res = (res+dfs(s^(1<<j),j))%MODmem[(s,i)]=resreturn resn = len(nums)ans = 0u = (1<<n)-1for i in  range(n):ans = (ans+dfs(u^(1<<i),i))%MODreturn ans

---

6/27 2734. 执行子串操作后的字典序最小字符串

除了a 别的字符执行都会变小 所以从左到右遇到第一个非a字符开始执行操作
遇到a停止操作
如果全是a 则将最后一个操作一次为 z

def smallestString(s):""":type s: str:rtype: str"""l=list(s)for i,c in enumerate(l):if c=='a':continuefor j in range(i,len(l)):if l[j]=='a':breakl[j]=chr(ord(l[j])-1)return ''.join(l)l[-1]='z'return ''.join(l)

---

6/28 2742. 给墙壁刷油漆

dp[i,j]表示前i面墙 免费工作次数为j的最小开销
对于第i堵墙
如果付费将花费cost[i] 并且获得time[i]次免费油漆匠工作机会
如果免费 将减少1次免费工作机会
j最多可以为n 最小为-n
使用0~2n来代替
因为依次判断i 所以dp[i,j]只会影响dp[i+1,x]
所以只需要一维dp[j]即可

def paintWalls(cost, time):""":type cost: List[int]:type time: List[int]:rtype: int"""n= len(cost)dp=[float('inf')]*(2*n+1)dp[n]=0for (c,t) in zip(cost,time):g=[float('inf')]*(2*n+1)for j in range(2*n+1):g[min(j+t,2*n)]=min(g[min(j+t,2*n)],dp[j]+c)if j>0:g[j-1]=min(g[j-1],dp[j])dp=greturn min(dp[n:])

---

6/29 2710. 移除字符串中的尾随零

从后往前判断 如果遇到0则往前一步

def removeTrailingZeros(num):""":type num: str:rtype: str"""for i in range(len(num)):if num[-1-i]!='0':breakreturn num if i==0 else num[:-i]

---

6/30 494. 目标和

1.dp 动态规划
dp[i][value] 前i个数 答案为value的可能情况
因为-1000<=value<=1000
方便起见 全部加1000 => 0<=value<=2000
v为当前位置数值 j为当前考虑value值
dp[i][j] = dp[i-1][j-v] + dp[i-1][j+v]
2.dp 动态规划
总和为total 变负数的总和绝对值为neg 正数总和total-neg target=total-2*neg
转化为neg = (total-target)/2 选取若干个数 总和为neg
dp[i][j] 前i个数 总和可以为j的可能方式
num = nums[i]
dp[i+1][j] = dp[i][j]+dp[i][j-num]

def findTargetSumWays(nums, target):""":type nums: List[int]:type target: int:rtype: int"""total = sum(nums)if target>total or target<-total:return 0n = len(nums)m = 2001dp = [[0]*m for _ in range(n+1)]dp[0][nums[0]+1000]+=1dp[0][1000-nums[0]]+=1for i in range(1,n):v = nums[i]for j in range(m):if j-v>=0 and dp[i-1][j-v]>0:dp[i][j] += dp[i-1][j-v]if j+v<m and dp[i-1][j+v]>0:dp[i][j]+=dp[i-1][j+v]return dp[n-1][target+1000]def findTargetSumWays2(nums, target):""":type nums: List[int]:type target: int:rtype: int"""            diff = sum(nums) - targetif diff<0 or diff%2==1:return 0n = len(nums)neg = diff//2dp = [[0]*(neg+1) for _ in range(n+1)]dp[0][0]=1for i in range(n):num = nums[i]for j in range(neg+1):dp[i+1][j]=dp[i][j]if j>=num:dp[i+1][j] += dp[i][j-num]return dp[n][neg]

---