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

目录

• • • 3/6 1653. 使字符串平衡的最少删除次数
    • 3/7 1096. 花括号展开 II
    • 3/8 剑指 Offer 47. 礼物的最大价值
    • 3/9 2379. 得到 K 个黑块的最少涂色次数
    • 3/10 1590. 使数组和能被 P 整除
    • 3/11
    • 3/12

3/6 1653. 使字符串平衡的最少删除次数

左侧是a右侧是b
对于某一位置 可以删除右边的a+左边的b
从头遍历 对于每个位置判断 在当前满足条件的操作次数

def minimumDeletions(s):""":type s: str:rtype: int"""lb,ra = 0,s.count('a')ans = rafor c in s:if c=='a':ra -=1else:lb +=1ans = min(ans,ra+lb)return ans

3/7 1096. 花括号展开 II

递归解析
add用来生成两个set相加
如果遇到, 说明前后两部分相或
如果遇到{ 往后找到其对应的} 将这部分递归解析
如果前面为, 则将两部分相或 否则相加
其他符号则为表达式相连 根据前一个符号来决定相或 相加

def braceExpansionII(expression):""":type expression: str:rtype: List[str]"""def add(a,b):ans = set()for i in a:for j in b:ans.add(i+j)return ansdef check(ex):tmp = set()ans = set()loc = 0last = ","while loc0:if ex[x]=="{":cur+=1elif ex[x]=="}":cur-=1x+=1if last ==",":tmp = tmp | check(ex[loc+1:x-1])else:tmp = add(tmp,check(ex[loc+1:x-1]))loc = xlast = "}"else:s = ""while loci+s for i in tmp}last = ex[loc-1]return ans | tmpreturn sorted(check(expression))

3/8 剑指 Offer 47. 礼物的最大价值

每一格可由其左边或上边到达
从左上角开始 记录到达每个格子的最大价值

def maxValue(grid):""":type grid: List[List[int]]:rtype: int"""m, n = len(grid), len(grid[0])for j in range(1, n): # 初始化第一行grid[0][j] += grid[0][j - 1]for i in range(1, m): # 初始化第一列grid[i][0] += grid[i - 1][0]for i in range(1, m):for j in range(1, n):grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])return grid[-1][-1]

3/9 2379. 得到 K 个黑块的最少涂色次数

滑动窗口 长度为k
往右移动记录窗口内白色的数量

def minimumRecolors(blocks, k):""":type blocks: str:type k: int:rtype: int"""wnum = 0for i in range(k):if blocks[i]=='W':wnum +=1ans = wnumfor i in range(k,len(blocks)):if blocks[i]=='W':wnum +=1if blocks[i-k]=='W':wnum -=1print(i-k,i,wnum)ans = min(ans,wnum)return ans

3/10 1590. 使数组和能被 P 整除

value记录总和除以P的余数
mem[x]从头遍历记录余数x最近的位置
寻找当前位置为结尾能够取到value的最短长度

def minSubarray(nums, p):""":type nums: List[int]:type p: int:rtype: int"""value = sum(nums)%pif value==0:return 0mem = {}mem[0]=-1cur = 0ans = len(nums)for i,v in enumerate(nums):cur = (cur+v)%pif (cur-value)%p in mem:ans = min(ans,i-mem[(cur-value)%p])mem[cur] = iif ans