解题思路
比较繁琐的分类讨论。
一个数字是 3 的倍数,他的十进制数位和必须是 3 的倍数。
如果数位和刚开始并不是 3 的倍数,我们看看是否能通过删除一个数位,使得数位和为 3 的倍数。
如果要删的这个数位必须是第一位,那就要考虑很多情况。
- 后面都是 0 ,删完之后就变成 0 了,不符合题意,所以一次都不能删。
- 后面有 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)
算法及复杂度
- 算法:枚举。
- 时间复杂度:。
- 空间复杂度:。