leetcode热题 - 5

可被三整除的最大和

问题描述

给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。
（真题链接：可被三整除的最大和）

解题思路

这题的题目很简单，只需要在整数数组中找到可以被三整除的元素的最大和。最简单的方法，我们先将所有本身就是3的倍数的元素全部取出，再在剩下的元素中按照三个余数为1的、三个余数为2的或者一个余数为1一个余数为2的组合求出最大值即可。但是操作十分复杂。所以，这里笔者采用了用空间换时间的做法：
先将所有元素都加起来，同时采用两个数组记录一下余数为1和余数为2的两个“数组”，再按照从小到大的顺序进行排序。随后，我们将所有数相加之和对3进行取余，倘若余数为1，那么我们可以选择去除一个最小的余数为1的元素或者两个最小余数为2的元素，再取这两种情况之中的最大值。余数为2的情况下同理。
当我们理清这样一个思路之后，代码就可以很轻易的写出相关代码了。

代码实现

classSolution{public:intmaxSumDivThree(vector<int>&nums){intsum=0;vector<int>re1,re2;for(intnum:nums){sum+=num;if(num%3==1)re1.push_back(num);elseif(num%3==2)re2.push_back(num);}if(sum%3==0)returnsum;sort(re1.begin(),re1.end());sort(re2.begin(),re2.end());intans=0;if(sum%3==1){// 情况1：去掉1个最小的余数为1的数if(re1.size()>=1)ans=max(ans,sum-re1[0]);// 情况2：去掉2个最小的余数为2的数if(re2.size()>=2)ans=max(ans,sum-re2[0]-re2[1]);}elseif(sum%3==2){// 情况1：去掉1个最小的余数为2的数if(re2.size()>=1)ans=max(ans,sum-re2[0]);// 情况2：去掉2个最小的余数为1的数if(re1.size()>=2)ans=max(ans,sum-re1[0]-re1[1]);}returnans;}};

复杂度分析

总结

这道题要求从整数数组中选出若干元素，使得元素和能被 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*(k+1)/2
算法步骤
初始化 cnt = 0（最终答案），k = 0（当前连续 1 的个数）。
遍历字符串 s 的每个字符：
如果当前字符是 ‘0’，跳过（因为 ‘0’ 会打断连续段）。
如果当前字符是 ‘1’，则用一个循环统计该段连续 ‘1’ 的长度 k，直到遇到 ‘0’ 或字符串结束。
将当前段贡献的子串数 k*(k+1)/2 累加到 cnt，并取模。
随后重置 k = 0，继续遍历下一段。
最后返回 cnt。

代码实现

classSolution{public:intnumSub(string s){longlongcnt=0,k=0;for(inti=0;i<s.size();i++){if(s[i]=='0')continue;while(s[i]=='1'&&i<s.size()){i++;k++;}cnt+=(k*(k+1))/2;cnt%=1000000007;k=0;}returncnt;}};

复杂度分析

总结

本题是典型的“统计连续相同字符子串”问题，关键点在于：
连续段分解：将问题转化为对每一段连续 ‘1’ 分别计算子串数。
取模处理：每一步累加后立即取模，防止大数溢出。
边界考虑：当字符串尾部是 ‘1’ 时，循环结束后需统计最后一段（代码中通过 while 循环自然处理了）。
该解法易于扩展到其他“统计连续相同字符子串”的变体问题（如统计全0子串等）。