网站找图片做海报侵权,喀喇沁旗网站建设公司,网站开发的人,如何做微信小程序店铺文章目录 1. 长度最小的子数组#xff08;模板#xff09;2. 无重复字符的最长字串3. 最小覆盖字串4. 加油站5. 替换字串得到平衡字符串 1. 长度最小的子数组#xff08;模板#xff09; 题目分析
直接用步骤分析示例1#xff0c;[]表示窗口#xff0c;min_length表示满… 文章目录 1. 长度最小的子数组模板2. 无重复字符的最长字串3. 最小覆盖字串4. 加油站5. 替换字串得到平衡字符串 1. 长度最小的子数组模板 题目分析
直接用步骤分析示例1[]表示窗口min_length表示满足条件的最短子数组sum表示窗口内元素的总值- [2],3,1,2,4,3 min_length100001sum2 target7- [2,3],1,2,4,3 min_length100001sum5 target7- [2,3,1],2,4,3 min_length100001sum6 target7- [2,3,1,2],4,3 min_length4 sum8 target7- PS只要sumtarget就尝试将左窗口向右移动若仍满足条件就更新min_length不行就继续- [2,3,1,2,4],3 min_length5 sum12 target7- 2,[3,1,2,4],3 min_length4 sum10 target7- 2,3,[1,2,4],3 min_length3 sum7 target7- 2,3,[1,2,4,3] min_length4 sum10 target7- 2,3,1,[2,4,3] min_length3 sum9 target7- 2,3,1,2,[4,3] min_length2 sum7 target7- 最后返回min_length2代码实现
def minSubArrayLen(target, nums)::type target: int:type nums: List[int]:rtype: intn len(nums)# l表示左窗口的位置r表示右窗口的位置l r 0# sum表示窗口内的元素总值sum nums[0]# 如果第一个元素的值就大于等于target直接返回if sum target: return 1# 设置成100001是因为测试用例的数组长度最长为100000min_length 100001# 循环n - 1次for i in range(1, n):# 右窗口肯定是要一直移动的不存在每次循环不移动的情况r 1sum nums[r]# 如果sum去掉靠近左窗口的那个元素后仍然大于sum就该减小窗口的长度了while sum - nums[l] target:sum - nums[l]l 1# 经过上述步骤后当来到右窗口此时的位置时满足条件的窗口长度就得到了if sum target:min_length min(min_length, r - l 1)# 数组所有元素的总和加起来都小于targetmin_length就返回0return 0 if min_length 100001 else min_length精简版
def minSubArrayLen(target, nums)::type target: int:type nums: List[int]:rtype: intn len(nums)l r 0min_length 100001sum 0while r n:sum nums[r]while sum - nums[l] target:sum - nums[l]l 1if sum target:min_length min(min_length, r - l 1)r 1return 0 if min_length 100001 else min_length2. 无重复字符的最长字串 注意s字符串包含字母、数字、符号和空格
题目分析
以abcabcbb为例max_length表示最长无重复字串字串l表示左窗口r表示右窗口- [a]bcabcbb max_length1- [ab]cabcbb max_length2- [abc]abcbb max_length3- [abca]bcbb- 下面这一步就很重要了lmax(l,a上一次出现位置1)- a[bca]bcbb max_length3- a[bcab]cbb lmax(l,b上一次出现位置1)- ab[cab]cbb max_length3- ab[cabc]bb lmax(l,c上一次出现位置1)- abc[abc]bb max_length3- abc[abcb]b lmax(l,b上一次出现位置1)- abcab[cb]b max_length3- abcab[cbb] lmax(l,b上一次出现位置1)- abcabcb[b] max_length3代码实现
def lengthOfLongestSubstring(s)::type s: str:rtype: intn len(s)# 字母、数字、空格和一些符号的ascii码都在0~255之间pos [-1] * 255l 0max_length 0for r in range(n):# 在r移动到下一个字符位置时一定要先让l获取上次这个字符出现的位置并且加1l max(l, pos[ord(s[r])] 1)# 然后再更新这个字符出现的位置pos[ord(s[r])] r# 最后通过比较获得wucmax_length max(max_length, r - l 1)return max_length3. 最小覆盖字串 题目分析
1. 拿一个cnts数组统计t串中字符的出现次数total记录t中每个字符出现次数的总和
2. 首先t中字符每出现一次cnts[ord(t[i])] - 1
3. 然后开始循环s字符串
4. 如果遇到出现次数小于0的total就减-1
5. 每循环一次该字符的出现次数就加1我们只关注t中的字符s中其它字符正常加就行了后面不会涉及到它们
6. 当total 0时也就是说当前窗口中已经包含了t中所有字符
7. 开始判断左窗口所指向的字符出现次数是否大于0大于0左窗口就可以向右移动了
8. PS当total第一次等于0时表示窗口中恰好有t中每个字符且它们的出现次数都为0后续可能会有多余的它们的出现次数就会大于0s中其它字符最开始都是0只要在窗口中它们的出现次数就会大于0
9. 然后判断当前窗口的长度跟最小覆盖字串的长度比较取较小的那个cnts是统计所有字符的出现次数初始化为0- 首先是将t串中每个字符的出现次数减1也就是说除了t串中的字符出现次数是负数其它字符的出现次数都是0- 然后就是只要有一个字符进窗口出现次数加1- 当左窗口字符出现次数大于0时就可以考虑将其删除了代码实现
def minWindow(s, t)::type s: str:type t: str:rtype: strn len(s)m len(t)# 如果s串长度小于m长度s就不可能有长度大于等于m的字串if n m:return total m# 计数数组cnts [0] * 255# 给t串中每种字符出现次数为负数for i in range(m):cnts[ord(t[i])] - 1l 0target min_length 100001# 开始遍历s串for r in range(n):# 能满足下面if语句条件的一定是t串中的字符if cnts[ord(s[r])] 0:total - 1# 不管是哪个串中的字符次数都要加1cnts[ord(s[r])] 1# total0表示窗口中已经包含了t串所有字符if total 0:# 开始判断左窗口可不可以移动while cnts[ord(s[l])] 0:cnts[ord(s[l])] - 1l 1# 取最小覆盖字串的长度if r - l 1 min_length:min_length r - l 1target s[l : r 1]return target4. 加油站 题目分析
用左窗口遍历一遍加油站即可此时左窗口就相当于起点右窗口就从左窗口开始向后遍历只要出现油不够的情况左窗口就向右移动。可以将gas和cost数组合并来看例如
gas [1,2,3,4,5]
cost [3,4,5,1,2]
combine [-2,-2,-2,3,3]
combine[0]表示从第0个加油站开到第1个加油站倒欠2升油所以无法以第0个加油站为起点开到第一个加油站
combine[3]表示从第4个加油站开到第5个加油站多出了3升油所以能以第4个加油站为起点开到第五个加油站代码
def canCompleteCircuit(gas, cost)::type gas: List[int]:type cost: List[int]:rtype: intn len(gas)# sum表示路上的总油量只要油量小于0了就不能走sum 0# len表示一共走了几个加油站length 0for l in range(n):while sum 0:# 如果从某个加油站出发能走完一圈就返回那个加油站的位置if length n:return lr (l length) % nlength 1sum gas[r] - cost[r]# 走到这说明sum0了那么左窗口就该移动了且sum要减去左窗口移动之前所在位置的那个值len也要减1sum - gas[l] - cost[l]length - 1# 如果以每个加油站为起点出发sum最后都会小于0就返回-1return -15. 替换字串得到平衡字符串 题目分析
思路
1. 先统计每种字符的出现次数
2. 然后用窗口框柱一段字符假设窗口外的每种字符出现次数不等于 n/4判断只替换窗口内的字符能否使窗口外的每种字符字符出现次数都变成n/4
3. 如果该窗口不行那么它的子窗口一定不行这里没想出为什么如果[l,r-1]不行[l,r]行那么[l1,r]也有可能行[l1,r-1]就一定不行4. 那么怎么实现第二步假如窗口长度为8窗口外面字符出现次数为Q-18,W-19,E-16,R-19要求是每种字符出现20次8-(20-18) 66-(20-19) 55-(20-16) 11-(20-19) 0最后剩余0表示能行如果外面某种字符超过了平均出现次数那么这个窗口一定不行代码实现
def balancedString(s)::type s: str:rtype: int# 这个函数就是实现上面分析的第四步# len表示窗口的大小也就是有len个元素可以替换看能不能使窗口外面的每种字符出现次数达到averdef ok(cnts, len, aver):for i in range(4):if cnts[i] aver:return Falselen - aver - cnts[i]return True if len 0 else Falsen len(s)aver n // 4# 将Q映射成0W映射成1E映射成2R映射成3data [Q, W, E, R]cnts [0] * 4for i in range(n):cnts[data.index(s[i])] 1# 作为替换字串的最小长度返回ans nr 0# 左窗口开始遍历sfor l in range(n):# l-r表示[l,r)范围# 如果当前窗口不行右窗口jiwhile ok(cnts, r - l, aver) False and r n:# 右窗口每次向右移动都会在窗口内新加入一个字符它在窗口外的出现次数要减1cnts[data.index(s[r])] - 1r 1# 这里是为了判断上面循环是因为第一个条件结束还是因为第二个条件结束的# 若是因为第二个条件结束的就说明这个窗口是合法的当然这里只能判断第一个条件# 因为第一个条件也有可能不符合if r ! n:ans min(ans, r - l)# 最后一次循环结束后左窗口会向右移动相当于会将它原来所在位置的字符排除到窗口外所以在窗口外这个字符的出现次数要加1cnts[data.index(s[l])] 1return ans
