专栏首页Michael阿明学习之路LeetCode 1363. 形成三的最大倍数(贪心,难)

LeetCode 1363. 形成三的最大倍数(贪心,难)

1. 题目

给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内,请以字符串形式返回答案。

如果无法得到答案,请返回一个空字符串。

示例 1:
输入:digits = [8,1,9]
输出:"981"

示例 2:
输入:digits = [8,6,7,1,0]
输出:"8760"

示例 3:
输入:digits = [1]
输出:""

示例 4:
输入:digits = [0,0,0,0,0,0]
输出:"0"
 
提示:
1 <= digits.length <= 10^4
0 <= digits[i] <= 9
返回的结果不应包含不必要的前导零。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/largest-multiple-of-three 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

容易错的数据:

[9,8,6,8,6]
[2,2,1,1,1]
[1,1,1,2]
[5,8]

2. 解题

  • 把所有数加起来和为sum,总的字符串降序排序,然后sum%3,看余数
  • 等于0,直接返回
  • 等于1,优先删除1个1 or 4 or 7,没有的话,删除2,5,8中最小的2个
  • 等于2,优先删除1个2 or 5 or 8,没有的话,删除1,4,7中最小的2个
class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
    	int count[10] = {0}, i, sum = 0, time;
    	string ans;	
    	for(i = 0; i < digits.size(); ++i)
    	{
    		count[digits[i]]++;//计数
    		sum += digits[i];//总和
    		ans += digits[i]+'0';//字符串
    	}
    	sort(ans.begin(), ans.end(),[](char& a, char& b){return a > b;});
		if(sum%3 == 1)
    	{
    		i = ans.size()-1;
    		if(count[1]!=0||count[4]!=0||count[7]!=0)
    		{
    			for( ; i>=0; --i)
	    		{
	    			if(ans[i]=='1'||ans[i]=='4'||ans[i]=='7')
	    			{
	    				ans.erase(ans.begin()+i);
	    				break;
	    			}
	    		}
    		}
    		else
    		{	
    			time = 2;
    			for( ; i>=0; --i)
    			{
    				if(ans[i]=='2'||ans[i]=='5'||ans[i]=='8')
	    			{
	    				ans.erase(ans.begin()+i);
	    				time--;
	    				if(time == 0)
	    					break;
	    			}
    			}
    		}
    	}
    	else if(sum%3 == 2)
    	{
    		i = ans.size()-1;
    		if(count[2]!=0||count[5]!=0||count[8]!=0)
    		{
    			for( ; i>=0; --i)
	    		{
	    			if(ans[i]=='2'||ans[i]=='5'||ans[i]=='8')
	    			{
	    				ans.erase(ans.begin()+i);
	    				break;
	    			}
	    		}
    		}
    		else
    		{	
    			time = 2;
    			for( ; i>=0; --i)
    			{
    				if(ans[i]=='1'||ans[i]=='4'||ans[i]=='7')
	    			{
	    				ans.erase(ans.begin()+i);
	    				time--;
	    				if(time == 0)
	    					break;
	    			}
    			}
    		}
		}
		if(ans != "" && ans[0]=='0')
			return "0";
		return ans;
	}
};

大佬优美解:

class Solution {
    int cnt[10], sum;
    string ans = "";
    set<int> s;
    int del(int m)
    {
        for(int i=m;i<=9;i+=3)
        	if(cnt[i])
        	{
        		cnt[i]--;
        		return 1;
       		}
        return 0;
    }
public:
    string largestMultipleOfThree(vector<int>& d) {
        for(auto x:d)
        	cnt[x]++, sum += x;
        if(sum%3==1)
        	if(!del(1))
        		del(2),del(2);
        if(sum%3==2)
        	if(!del(2))
        		del(1),del(1);
        for(int i=9; i>=0; i--)
        	while(cnt[i]--)
        		ans += i+'0', s.insert(i);
        if(s.size()==1 && s.count(0))
        	return "0";// [1,0,0] -> "0"
        return ans;
    }
};

作者:YusenZhang_chatc
链接:https://leetcode-cn.com/problems/largest-multiple-of-three/solution/c-qu-diao-zui-xiao-zhi-8ms-by-yusenzhang_chatc/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 482. 密钥格式化

    给定一个密钥字符串S,只包含字母,数字以及 ‘-’(破折号)。N 个 ‘-’ 将字符串分成了 N+1 组。给定一个数字 K,重新格式化字符串,除了第一个分组以外...

    Michael阿明
  • LeetCode 984. 不含 AAA 或 BBB 的字符串(贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/string-without-aaa-or-bbb ...

    Michael阿明
  • LeetCode 1119. 删去字符串中的元音

    给你一个字符串 S,请你删去其中的所有元音字母( ‘a’,‘e’,‘i’,‘o’,‘u’),并返回这个新字符串。

    Michael阿明
  • 【POJ 2406】Power Strings(KMP循环节)

    终于靠着理解写出KMP了,两种KMP要代码中这种才能求循环节。i-next[i]就是循环节。

    饶文津
  • Q13 Roman to Integer

    Given a roman numeral, convert it to an integer. Input is guaranteed to be withi...

    echobingo
  • 【USACO 3.2】Factorials(阶层非零尾数)

    题解:可以把5和2的个数算出来,每次把5和2都除掉,最后乘上比5多出来的2。我的解法是,每次把尾巴的0去掉,并且保留3位,算到最后取尾数就可以了。、

    饶文津
  • HDUOJ-------(1211)RSA

    RSA Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/...

    Gxjun
  • 【CodeForces 577C】Vasya and Petya’s Game

    某个数x属于[1,n],至少询问哪些数y“x是否是y的倍数”才能判断x。 找出所有质因数和质因数的幂即可。

    饶文津
  • Leetcode【392、870、881、1090】

    简单题。双指针 i 和 j 分别指向 t 和 s,对于 t 的每一个位置遍历,如果 t[i] 和 s[j] 相同,那么 j 也想后移动找下一个相同的字符。当 j...

    echobingo
  • LeetCode 274. H-Index

    题目的意思很简单啦,就是问你一个数组,有x个数字,都大于等于x,问这个x是多少, 这个x肯定是一定的。

    ShenduCC

扫码关注云+社区

领取腾讯云代金券