leetcode热题 - 5

可被三整除的最大和问题描述给你一个整数数组 nums请你找出并返回能被三整除的元素 最大和。真题链接可被三整除的最大和解题思路这题的题目很简单只需要在整数数组中找到可以被三整除的元素的最大和。最简单的方法我们先将所有本身就是3的倍数的元素全部取出再在剩下的元素中按照三个余数为1的、三个余数为2的或者一个余数为1一个余数为2的组合求出最大值即可。但是操作十分复杂。所以这里笔者采用了用空间换时间的做法先将所有元素都加起来同时采用两个数组记录一下余数为1和余数为2的两个“数组”再按照从小到大的顺序进行排序。随后我们将所有数相加之和对3进行取余倘若余数为1那么我们可以选择去除一个最小的余数为1的元素或者两个最小余数为2的元素再取这两种情况之中的最大值。余数为2的情况下同理。当我们理清这样一个思路之后代码就可以很轻易的写出相关代码了。代码实现classSolution{public:intmaxSumDivThree(vectorintnums){intsum0;vectorintre1,re2;for(intnum:nums){sumnum;if(num%31)re1.push_back(num);elseif(num%32)re2.push_back(num);}if(sum%30)returnsum;sort(re1.begin(),re1.end());sort(re2.begin(),re2.end());intans0;if(sum%31){// 情况1去掉1个最小的余数为1的数if(re1.size()1)ansmax(ans,sum-re1[0]);// 情况2去掉2个最小的余数为2的数if(re2.size()2)ansmax(ans,sum-re2[0]-re2[1]);}elseif(sum%32){// 情况1去掉1个最小的余数为2的数if(re2.size()1)ansmax(ans,sum-re2[0]);// 情况2去掉2个最小的余数为1的数if(re1.size()2)ansmax(ans,sum-re1[0]-re1[1]);}returnans;}};复杂度分析复杂度量级时间复杂度O(nlogn)空间复杂度O(n)总结这道题要求从整数数组中选出若干元素使得元素和能被 3 整除并求出满足条件的最大和。核心解题思路是先统计数组全部元素总和同时把元素按对 3 取余分为余 1、余 2 两类并分别排序再根据总和模 3 的余数分类讨论通过贪心剔除最小代价元素让剩余总和可以被 3 整除。若总和余 1可删 1 个最小余 1 元素或删 2 个最小余 2 元素若总和余 2可删 1 个最小余 2 元素或删 2 个最小余 1 元素取两种情况最大值即为答案。该方法本质是数学取余 贪心策略时间复杂度O(nlogn)仅需一次遍历 少量排序逻辑简洁、实现简单在常规数据规模下可以高效通过题目测试。仅含1的子串数问题描述给你一个二进制字符串 s仅由 ‘0’ 和 ‘1’ 组成的字符串。返回所有字符都为 1 的子字符串的数目。由于答案可能很大请你将它对 10^9 7 取模后返回真题链接仅含1的子串数解题思路如果一个子串全部由 ‘1’ 组成那么它一定是某个连续 1 段的一部分。对于长度为k的连续 1 段其包含的全 1 子串个数为k*(k1)/2算法步骤初始化 cnt 0最终答案k 0当前连续 1 的个数。遍历字符串 s 的每个字符如果当前字符是 ‘0’跳过因为 ‘0’ 会打断连续段。如果当前字符是 ‘1’则用一个循环统计该段连续 ‘1’ 的长度 k直到遇到 ‘0’ 或字符串结束。将当前段贡献的子串数 k*(k1)/2 累加到 cnt并取模。随后重置 k 0继续遍历下一段。最后返回 cnt。代码实现classSolution{public:intnumSub(string s){longlongcnt0,k0;for(inti0;is.size();i){if(s[i]0)continue;while(s[i]1is.size()){i;k;}cnt(k*(k1))/2;cnt%1000000007;k0;}returncnt;}};复杂度分析复杂度量级时间复杂度O(n)空间复杂度O(1)总结本题是典型的“统计连续相同字符子串”问题关键点在于连续段分解将问题转化为对每一段连续 ‘1’ 分别计算子串数。取模处理每一步累加后立即取模防止大数溢出。边界考虑当字符串尾部是 ‘1’ 时循环结束后需统计最后一段代码中通过 while 循环自然处理了。该解法易于扩展到其他“统计连续相同字符子串”的变体问题如统计全0子串等。