手机版网站开发教程,网站建设目的,专业微网站建设公司首选公司,华企网站建设记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 9/23 2414. 最长的字母序连续子字符串的长度9/24 2207. 字符串中最多数目的子序列9/25 2306. 公司命名9/26 2535. 数组元素和与数字和的绝对差9/27 2516. 每种字符至少取 K…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 9/23 2414. 最长的字母序连续子字符串的长度9/24 2207. 字符串中最多数目的子序列9/25 2306. 公司命名9/26 2535. 数组元素和与数字和的绝对差9/27 2516. 每种字符至少取 K 个9/28 2286. 以组为单位订音乐会的门票9/29 9/23 2414. 最长的字母序连续子字符串的长度 依次遍历 cur记录当前满足条件的字符串长度 如果当前字符s[i]比前一个字符字母序大1则满足条件 cur1 def longestContinuousSubstring(s)::type s: str:rtype: intans 1cur 1for i in range(1,len(s)):if ord(s[i])-ord(s[i-1])1:cur1else:cur1ansmax(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: intp0,p10,0ans 0for c in text:if cpattern[1]:ans p0p11if cpattern[0]:p01return ansmax(p0,p1) 9/25 2306. 公司命名 首字母相同的公司必定不满足条件 按首字母将idea分类 m[h]存储以字母h为首字母的剩余字符 遍历所有首字母 h1,h2中有后续字符序列s1,s2 只有不在s1,s2交集中的序列才可以相互组合 (s1-s1s2)*(s2-s1s2) def distinctNames(ideas)::type ideas: List[str]:rtype: intfrom 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 h1h2:continuesame len(s1s2)ans (len(s1)-same)*(len(s2)-same)return ans 9/26 2535. 数组元素和与数字和的绝对差 依次求出元素和 数字和 def differenceOfSum(nums)::type nums: List[int]:rtype: ints00s10for num in nums:s0numwhile num:s1num%10num//10return s0-s1 9/27 2516. 每种字符至少取 K 个 取走左右两侧 中间部分必定是连续的 可以用双指针考虑中间部分区间 中间部分越长 则取走的次数越少 def takeCharacters(s, k)::type s: str:type k: int:rtype: intnlen(s)if n3*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 lr and (cnt[a]k or cnt[b]k or cnt[c]k):cnt[s[l]]1l1if cnt[a]k and cnt[b]k and cnt[c]k:ans min(ans,n-(r-l1))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: intself.n nself.m mself.minT [0]*(4*n)self.sumT [0]*(4*n)def modify(self,i,l,r,ind,val):if lr:self.minT[i]valself.sumT[i]valreturnmid(lr)//2if indmid:self.modify(i*2,l,mid,ind,val)else:self.modify(i*21, mid1, r, ind, val)self.minT[i]min(self.minT[i*2],self.minT[i*21])self.sumT[i]self.sumT[i*2]self.sumT[i*21]def queryMin(self,i,l,r,val):if lr:return l if self.minT[i]val else self.nmid (lr)//2if self.minT[i*2]val:return self.queryMin(i*2,l,mid,val)else:return self.queryMin(i*21,mid1,r,val)def querySum(self,i,l,r,l2,r2):if l2l and rr2:return self.sumT[i]mid(lr)//2s0if midl2:sself.querySum(i*2, l, mid, l2, r2)if mid1r2:sself.querySum(i*21, mid1, 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 imaxRow:return []used self.querySum(1, 0, self.n-1, i, i)self.modify(1, 0, self.n-1, i, usedk)return [i,used]def scatter(self, k, maxRow)::type k: int:type maxRow: int:rtype: booltotal self.querySum(1, 0, self.n-1, 0, maxRow)if (maxRow1)*self.m-totalk: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-usedk:self.modify(1, 0, self.n-1, i, usedk)breakk-self.m-usedself.modify(1, 0, self.n-1, i, self.m)i1return True 9/29
