解题思路

比较繁琐的分类讨论。
一个数字是 3 的倍数,他的十进制数位和必须是 3 的倍数。
如果数位和刚开始并不是 3 的倍数,我们看看是否能通过删除一个数位,使得数位和为 3 的倍数。
如果要删的这个数位必须是第一位,那就要考虑很多情况。

  1. 后面都是 0 ,删完之后就变成 0 了,不符合题意,所以一次都不能删。
  2. 后面有 0 ,但不完全是 0 ,需要抹掉前导零。

考虑完上面的情况,开始删 0 3 6 9 ,因为这四种数位不会影响数位和的性质。
需要注意的是,最后需要保留一个非零数位,别全部删干净了。

代码

#include <iostream>
#include <string>
using namespace std;
int b[4];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	int t,n,m,i,ans;
	cin>>t;
	while(t--)
	{
		cin>>s;
		ans=0;
		n=s.length();
		for(i=0;i<4;++i)
			b[i]=0;
		for(i=0;i<n;++i)
		{
			m=s[i]-48;
			if(m!=0&&m%3==0)
				++b[3];
			else
				++b[m%3];
		}
		m=0;
		for(i=1;i<4;++i)
			m+=i*b[i];
		if(m%3!=0)
		{
			if(b[m%3]==0)
			{
				cout<<"0\n";
				continue;
			}
			++ans;
			--b[m%3];
			if(b[m%3]==0&&(s[0]-48)%3==m%3)
			{
				if(b[0]==n-1)
				{
					cout<<"0\n";
					continue;
				}
				for(i=1;i<n&&s[i]=='0';++i)
					--b[0];
				if(b[1]==0&&b[2]==0)
					--ans;
			}
		}
		ans+=b[0]+b[3];
		ans=min(ans,n-1);
		cout<<ans<<'\n';
	}
	return 0;
}
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(),n,m,i,ans;
        while (t-->0){
            String s=sc.next();
            n=s.length();
            ans=0;
            int[] b=new int[4];
            for(i=0;i<n;++i){
                m=s.charAt(i)-48;
                if(m!=0&&m%3==0)
                    b[3]++;
                else
                    b[m%3]++;
            }
            m=0;
            for(i=1;i<4;++i)
                m+=i*b[i];
            if(m%3!=0){
                if(b[m%3]==0){
                    System.out.println(0);
                    continue;
                }
                ++ans;
                --b[m%3];
                if(b[m%3]==0&&(s.charAt(0)-48)%3==m%3){
                    if(b[0]==n-1){
                        System.out.println(0);
                        continue;
                    }
                    for(i=1;i<n&&s.charAt(i)=='0';++i)
                        --b[0];
                    if(b[1]==0&&b[2]==0)
                        --ans;
                }
            }
            ans+=b[0]+b[3];
            ans=Math.min(ans,n-1);
            System.out.println(ans);
        }
    }
}
t=int(input())
for _ in range(0,t):
    s=input()
    n=len(s)
    b=[0]*4
    ans=0
    for i in range(0,n):
        m=ord(s[i])-48
        if(m!=0 and m%3==0):
            b[3]+=1
        else:
            b[m%3]+=1
    m=0
    for i in range(1,4):
        m+=i*b[i]
    if(m%3!=0):
        if(b[m%3]==0):
            print(0)
            continue
        ans+=1
        b[m%3]-=1
        if(b[m%3]==0 and (ord(s[0])-48)%3==m%3):
            if(b[0]==n-1):
                print(0)
                continue
            for i in range(1,n):
                if(s[i]!='0'):
                    break
                b[0]-=1
            if(b[1]==0 and b[2]==0):
                ans-=1
    ans+=b[0]+b[3]
    ans=min(ans,n-1)
    print(ans)

算法及复杂度

  • 算法:枚举。
  • 时间复杂度:
  • 空间复杂度: