LeetCode 每日一题 2024/8/12-2024/8/18

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

---

8/12 676. 实现一个魔法字典

将单词按照长度分组
在相同长度的单词中寻找是否满足

class MagicDictionary(object):def __init__(self):"""Initialize your data structure here."""from collections import defaultdictself.dic=defaultdict(list)def buildDict(self, dict):"""Build a dictionary through a list of words:type dict: List[str]:rtype: None"""for w in dict:num = len(w)self.dic[num].append(w)def search(self, word):"""Returns if there is any word in the trie that equals to the given word after modifying exactly one character:type word: str:rtype: bool"""num = len(word)if num not in self.dic.keys():return Falsefor w in self.dic[num]:tag = 0for i in range(num):if w[i]!=word[i]:tag+=1if tag==1:return Truereturn False

---

8/13 3151. 特殊数组 I

相邻奇偶性不同 说明相邻两数相加为奇数

def isArraySpecial(nums):""":type nums: List[int]:rtype: bool"""for i in range(1,len(nums)):if (nums[i]+nums[i-1])%2==0:return Falsereturn True

---

8/14 3152. 特殊数组 II

如果[a:b]是特殊数组 那么它内部的任何子数组都是特殊数组
l[x]记录以x结尾的最长特殊数组
对于[i,j] 只需要l[j]>=j-i+1 说明[i,j]是特殊数组

def isArraySpecial(nums, queries):""":type nums: List[int]:type queries: List[List[int]]:rtype: List[bool]"""n=len(nums)l=[1]*nfor i in range(1,n):if (nums[i-1]+nums[i])%2==1:l[i] = l[i-1]+1ans = [False]*len(queries)for i,(x,y) in enumerate(queries):if l[y]>=y-x+1:ans[i] = Truereturn ans

---

8/15 3148. 矩阵中的最大得分

对于起点x0 经过x1,x2…到达xn
得到总分(x1-x0)+(x2-x1)+…+(xn-xn-1)=xn-x0
所以得分只和终点起点相关 终点在起点的右下侧
premin[i][j]记录在grid[0_i][0j]范围内的最小值
当前i,j的最大得分为当前值grid[i][j]-min(premin[i-1][j],premin[i][j-1])

def maxScore(grid):""":type grid: List[List[int]]:rtype: int"""m,n=len(grid),len(grid[0])premin = [[float("inf")]*n for _ in range(m)]ans = float("-inf")for i in range(m):for j in range(n):pre = float("inf")if i>0:pre = min(pre,premin[i-1][j])if j>0:pre = min(pre,premin[i][j-1])if i+j>0:ans = max(ans,grid[i][j]-pre)premin[i][j]=min(pre,grid[i][j])return ans

---

8/16 3117. 划分数组得到最小的值之和

dfs
i为nums下个元素 j为andValues下个元素 cur为当前子数组按位与的结果
如果cur<andValues[j] 匹配失败
cur>andValues[j] 继续与运算
cur=andValues[j] 可以继续与运算 也可以开始对andValues[j+1]进行匹配

def minimumValueSum(nums, andValues):""":type nums: List[int]:type andValues: List[int]:rtype: int"""inf = (1<<20)-1mem={}def dfs(i,j,cur):if (i,j,cur) in mem:return mem[(i,j,cur)]if i==len(nums) and j==len(andValues):return 0if i==len(nums) or j==len(andValues):mem[(i,j,cur)] = float("inf")return float("inf")cur &=nums[i]if cur & andValues[j]<andValues[j]:mem[(i,j,cur)] = float("inf")return float("inf")ans = dfs(i+1,j,cur)if cur==andValues[j]:ans = min(ans,dfs(i+1,j+1,inf)+nums[i])mem[(i,j,cur)]=ansreturn ansans = dfs(0,0,inf)if ans<float("inf"):return ansreturn -1

---

8/17 3137. K 周期字符串需要的最少操作次数

遍历记录每一个长度k的子串出现次数 n为word长度
需要操作次数=n/k-同一个子串最多出现次数

def minimumOperationsToMakeKPeriodic(word, k):""":type word: str:type k: int:rtype: int"""m={}n=len(word)num=0for i in range(0,n,k):s=word[i:i+k]m[s] = m.get(s,0)+1num=max(num,m[s])return n//k-num

---

8/18 551. 学生出勤记录 I

遍历 记录两个条件
numA 记录缺勤次数
conL 记录连续迟到天数

def checkRecord(s):""":type s: str:rtype: bool"""numA = 0conL = 0for c in s:if c=="L":conL +=1if conL>2:return Falseelse:conL = 0if c=="A":numA +=1if numA==2:return Falsereturn True

---