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

---

1/15 82. 删除排序链表中的重复元素 II

判断下一个节点是否存在重复

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next
def deleteDuplicates(head):""":type head: ListNode:rtype: ListNode"""top =ListNode(float("-inf"))top.next = headpre = topcur = pre.nextloc = topwhile cur:nex = cur.nextif not nex:if pre.val<cur.val:loc.next = curelse:loc.next = nexbreakif pre.val<cur.val and cur.val<nex.val:loc.next = curloc = curpre = curcur = cur.nextreturn top.next

---

1/16 2719. 统计整数数目

数位dp
枚举每一个数位能够取到的范围
s记录当前数位和

def count(num1, num2, min_sum, max_sum):""":type num1: str:type num2: str:type min_sum: int:type max_sum: int:rtype: int"""n = len(num2)MOD = 10**9+7num1 = '0'*(n-len(num1))+num1@cachedef dfs(i,s,limitlow,limithigh):if s>max_sum:return 0if i==n:return s>=min_sumlo = int(num1[i]) if limitlow else 0hi = int(num2[i]) if limithigh else 9ans = 0for d in range(lo,hi+1):ans += dfs(i+1,s+d,limitlow and d==lo,limithigh and d==hi)return ansreturn dfs(0,True,True)%MOD

---

1/17 2744. 最大字符串配对数目

从头遍历 hash表保存已有字符串
判断当前字符串倒序后是否在hash表中

def maximumNumberOfStringPairs(words):""":type words: List[str]:rtype: int"""m = {}ans = 0for w in words:if w[::-1] in m:ans +=1m[w]=1return ans

---

1/18 2171. 拿出最少数目的魔法豆

将豆子从小到大排序
如果要全部取出必定先取少的
从头依次判断
left记录较少的豆子全部取出的数量
cnt 记录当前剩余总豆子即右侧的总豆子
计算右侧豆子数量和当前位置一致时需要取出的豆子和right
left+right即为当前满足条件的豆子数

def minimumRemoval(beans):""":type beans: List[int]:rtype: int"""cnt = sum(beans)left = 0ans = cntbeans.sort()n = len(beans)for i,b in enumerate(beans):right = cnt-(n-i)*bans = min(ans,left+right)left += bcnt -=breturn ans

---

1/19 2809. 使数组和小于等于 x 的最少时间

如果不去除 则每一秒增加sum(nums2)
在nums1中每一个只去除1次 如果两次的话那第一次无用
s1=sum(nums1) s2=sum(nums2)
在t秒是 s1+s2*t 为总数为了使其最小
需要找到减去的值最大
即nums1[k1]+(nums1[k2]+nums2[k2]*1)+(nums1[k3]+nums2[k3]*2)+…
dp[i+1][j]表示从0…i中选取j即经过的时间t个和最大的值
dp[i+1][j] = max(dp[i][j],dp[i][j-1]+nums1[i]+nums2[i]*j)
最后从小到大考虑每一秒t的情况

def minimumTime(nums1, nums2, x):""":type nums1: List[int]:type nums2: List[int]:type x: int:rtype: int"""n= len(nums1)s1=sum(nums1)s2=sum(nums2)p = sorted(zip(nums1,nums2),key=lambda x:x[1])dp=[0]*(n+1)for i,(a,b) in enumerate(p):for j in range(i+1,0,-1):dp[j] = max(dp[j],dp[j-1]+a+b*j)for t,v in enumerate(dp):if s1+s2*t-v<=x:return treturn -1

---

1/20 2788. 按分隔符拆分字符串

依次处理

def splitWordsBySeparator(words, separator):""":type words: List[str]:type separator: str:rtype: List[str]"""ans = []for w in words:l = w.split(separator)for c  in l:if c!="":ans.append(c)return ans

---

1/21 410. 分割数组的最大值

动态规划dp[i][j]代表前i个数分为j段的最小值
s[i]表示0~i此区间内的数之和
对于dp[i][j] 遍历每一个0~i的位置x
取x~i为最后一段 所以x前的j-1段最小的最大值为dp[x][j-1]
最后一段的和为s[i]-s[x] 取两值的最大值为此状态下的值

def splitArray(nums, k):""":type nums: List[int]:type k: int:rtype: int"""n=len(nums)dp=[[float('inf')]*(k+1) for _ in range(n+1)]s=[0]for num in nums:s.append(s[-1]+num)dp[0][0]=0for i in range(1,n+1):for j in range(1,min(i,k)+1):for x in range(i):dp[i][j] = min(dp[i][j],max(dp[x][j-1],s[i]-s[x]))return dp[n][k]

---