LeetCode 1363. 形成三的最大倍数（贪心，难）

示例 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
返回的结果不应包含不必要的前导零。

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

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/