LeetCode 每日一题 2024/9/23-2024/9/29

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

9/23 2414. 最长的字母序连续子字符串的长度

依次遍历 cur记录当前满足条件的字符串长度
如果当前字符s[i]比前一个字符字母序大1则满足条件 cur+1

def longestContinuousSubstring(s):""":type s: str:rtype: int"""ans = 1cur = 1for i in range(1,len(s)):if ord(s[i])-ord(s[i-1])==1:cur+=1else:cur=1ans=max(ans,cur)return ans

9/24 2207. 字符串中最多数目的子序列

为了使得增加一个字符增加的子序列最多
pattern[0]加在开头 pattern[1]加在结尾
从头遍历 统计pattern[0],[1]出现次数p0.p1
遇到pattern[1] 说明该字符可以与前边的pattern[0]组合成p0个子序列
最后 哪个多那就添加另外一个字符 增加max(p0,p1)个子序列

def maximumSubsequenceCount(text, pattern):""":type text: str:type pattern: str:rtype: int"""p0,p1=0,0ans =0for c in text:if c==pattern[1]:ans += p0p1+=1if c==pattern[0]:p0+=1return ans+max(p0,p1)

9/25 2306. 公司命名

首字母相同的公司必定不满足条件
按首字母将idea分类
m[h]存储以字母h为首字母的剩余字符
遍历所有首字母
h1,h2中有后续字符序列s1,s2
只有不在s1,s2交集中的序列才可以相互组合
(s1-s1&s2)*(s2-s1&s2)

def distinctNames(ideas):""":type ideas: List[str]:rtype: int"""from collections import defaultdictm = defaultdict(set)for s in ideas:m[s[0]].add(s[1:])ans = 0for h1,s1 in m.items():for h2,s2 in m.items():if h1==h2:continuesame = len(s1&s2)ans +=(len(s1)-same)*(len(s2)-same)return ans

9/26 2535. 数组元素和与数字和的绝对差

依次求出元素和 数字和

def differenceOfSum(nums):""":type nums: List[int]:rtype: int"""s0=0s1=0for num in nums:s0+=numwhile num:s1+=num%10num//=10return s0-s1

9/27 2516. 每种字符至少取 K 个

取走左右两侧 中间部分必定是连续的
可以用双指针考虑中间部分区间
中间部分越长 则取走的次数越少

def takeCharacters(s, k):""":type s: str:type k: int:rtype: int"""n=len(s)if n<3*k:return -1cnt={'a':0,'b':0,'c':0}for c in s:cnt[c]+=1if cnt['a']<k or cnt['b']<k or cnt['c']<k:return -1ans = len(s)l = 0for r,c in enumerate(s):cnt[c]-=1while l<r and (cnt['a']<k or cnt['b']<k or cnt['c']<k):cnt[s[l]]+=1l+=1if cnt['a']>=k and cnt['b']>=k and cnt['c']>=k:ans = min(ans,n-(r-l+1))return ans

9/28 2286. 以组为单位订音乐会的门票

线段树minT,sumT记录区间[l,r]排之间 每一排最小已坐位置 和 已坐位置数之和
见题解https://leetcode.cn/problems/booking-concert-tickets-in-groups/solutions/2930664/yi-zu-wei-dan-wei-ding-yin-le-hui-de-men-ay7o

class BookMyShow(object):def __init__(self, n, m):""":type n: int:type m: int"""self.n = nself.m = mself.minT = [0]*(4*n)self.sumT = [0]*(4*n)def modify(self,i,l,r,ind,val):if l==r:self.minT[i]=valself.sumT[i]=valreturnmid=(l+r)//2if ind<=mid:self.modify(i*2,l,mid,ind,val)else:self.modify(i*2+1, mid+1, r, ind, val)self.minT[i]=min(self.minT[i*2],self.minT[i*2+1])self.sumT[i]=self.sumT[i*2]+self.sumT[i*2+1]def queryMin(self,i,l,r,val):if l==r:return l if self.minT[i]<=val else self.nmid = (l+r)//2if self.minT[i*2]<=val:return self.queryMin(i*2,l,mid,val)else:return self.queryMin(i*2+1,mid+1,r,val)def querySum(self,i,l,r,l2,r2):if l2<=l and r<=r2:return self.sumT[i]mid=(l+r)//2s=0if mid>=l2:s+=self.querySum(i*2, l, mid, l2, r2)if mid+1<=r2:s+=self.querySum(i*2+1, mid+1, r, l2, r2)return sdef gather(self, k, maxRow):""":type k: int:type maxRow: int:rtype: List[int]"""i = self.queryMin(1, 0, self.n-1, self.m-k)if i>maxRow:return []used = self.querySum(1, 0, self.n-1, i, i)self.modify(1, 0, self.n-1, i, used+k)return [i,used]def scatter(self, k, maxRow):""":type k: int:type maxRow: int:rtype: bool"""total = self.querySum(1, 0, self.n-1, 0, maxRow)if (maxRow+1)*self.m-total<k:return Falsei = self.queryMin(1, 0, self.n-1, self.m-1)while True:used = self.querySum(1, 0, self.n-1, i, i)if self.m-used>=k:self.modify(1, 0, self.n-1, i, used+k)breakk-=self.m-usedself.modify(1, 0, self.n-1, i, self.m)i+=1return True

9/29 2073. 买票需要的时间

从头遍历
假设位置k需要买num张票
对于位置k前的人 必定买完或者最多买num张票
对于k后的人 买完或者最多买num-1张票

def timeRequiredToBuy(tickets, k):""":type tickets: List[int]:type k: int:rtype: int"""num=tickets[k]ans = numfor i in range(k):ans += min(tickets[i],num)for i in range(k+1,len(tickets)):ans += min(tickets[i],num-1)return ans