3052. 最小不重复数

yuanfang

参考大神的博客http://www.cnblogs.com/pmer/p/3351466.html#!comments

#include <string>
#include <cstdio>
#include <iostream>
using namespace std;
string addOne(string a) {
    string ans;
    int sum, carry = 1;
    for (int i = a.size() - 1; i >= 0; --i) {
        sum = a[i] - '0' + carry;
        carry = sum / 10;
        ans.insert(0, 1, sum % 10 + '0');
    }
    if (carry != 0) {
        ans.insert(0, 1, carry + '0');
    }
    return ans;
}
bool lesser(string a, string b) {
    if (a.size() == b.size()) {
        return a < b;
    } else {
        return a.size() < b.size();
    }
}
string solve(string str) {
    if (str.size() == 1) {
        return str;
    }
    string sub = str.substr(0, str.size() - 1);
    string temp = solve(sub);
    if (lesser(sub, temp)) {
        str = temp.append(1, '0');
    }
    if (str[str.size() - 1] == str[str.size() - 2]) {
        temp = addOne(str);
        return solve(temp);
    }
    return str;
}
int main() {
    int t;
    cin >> t;
    string str;
    for (int cas = 0; cas < t; ++cas) {
        cin >> str;
        str = addOne(str);
        str = solve(str);
        printf("case #%d:\n%s\n", cas, str.c_str());
    }
    return 0;
}
10175102262 LarsPendragon

我确实写错了,大佬说得对,应该+1而不是加到相等。
附新的C代码:

#include <stdio.h>
#include <string.h>
int noReputationTwice;//判断是否连续两次都是非重复数
void solve(char *num)
{
    int l=strlen(num), check=0, i;
    if(l==1 && num[0]<'9') printf("%c\n",num[0]+1);//处理一位数
    else if(l==1 && num[0]=='9') printf("10\n");//处理9
    else
    {
        for(i=0; i<l-1; i++) if(num[i]==num[i+1]) break;
        if(i==l-1)//没有重复数的情况
        {
            if(noReputationTwice)
            {
                for(i=0; i<l; i++) printf("%c",num[i]); printf("\n");
                return;
            }
            if(num[l-1]=='9') {num[l-2]++; num[l-1]='0';}
            else num[l-1]++;
            noReputationTwice=1;
            solve(num);
            return;
        }
        else if(num[i]!='9')//处理一般情况
        {
            num[i+1]++;
            for(i+=2; i<l; i++)
            {
                if(check==0) {num[i]='0'; check=1;}
                else {num[i]='1'; check=0;}
            }
        }
        else if(i==0)//处理首位是9的情况
        {
            printf("1");
            for(i=0; i<l; i++)
            {
                if(check==0) {num[i]='0'; check=1;}
                else {num[i]='1'; check=0;}
            }
        }
        else//处理重复数是9的情况
        {
            num[i-1]++;
            for(; i<l; i++)
            {
                if(check==0) {num[i]='0'; check=1;}
                else {num[i]='1'; check=0;}
            }
        }
        noReputationTwice=0;
        for(i=0; i<l-1; i++) if(num[i]==num[i+1]) break;//再次判断是否有重复数
        if(i==l-1) //没有重复数直接输出
        {
            for(i=0; i<l; i++) printf("%c",num[i]); printf("\n");
            return;
        }
        else solve(num);//有重复数循环处理
    }
}
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        noReputationTwice=0;
        char num[120];
        int i;
        scanf("%s",num);
        printf("case #%d:\n",I);
        solve(num);
    }
    return 0;
}
Li Dao

一种我能想到但是相对笨拙的方法
首先,直接把数一直加一,直到相邻不重复可能太慢了

程序如下:

include

using namespace std;
int T;
string strs;
vector V;

void inc(int pos=0)
{
V[pos]++;
for(int i=0;i=10)
{
int top=V.size()-1;
V.push_back(V[top]/10);
V[top]%=10;
}
return;
}
void print()
{
for(int i=V.size()-1;i>=0;i–) cout<<V[i];
cout<>strs;
V.clear();
int ll=strs.length();
for(int i=ll-1;i>=0;i–) V.push_back(strs[i]-‘0’);

inc();
while(havesame()) inc();
print();
return;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

测试样例都超时。比如100000000000000000这样一个数要加一到满足要求要太多次了,最多有10^100

最后用了构造法

从左到右扫描,第一次遇到重复的,比如这样XXXXXXXXXX66XXXXXXXX
就改为XXXXXXXXXX670101010101010101

比较麻烦的是遇到99
XXXXXXXX99XXXXXXXXXX
就加上
XXXXXXXX01XXXXXXXXXXXX
直到找不到99

还有一种,如果本来就没重复的,先加一,再正常做

代码如下

include

using namespace std;
int T;
string strs;
vector V;

void inc(int pos=0)
{
V[pos]++;
for(int i=0;i=10)
{
int top=V.size()-1;
V.push_back(V[top]/10);
V[top]%=10;
}
return;
}
void print()
{
for(int i=V.size()-1;i>=0;i–) cout<<V[i];
cout<=0;i--) { V[i]=now; now=1-now; } return; } int havesame() { for(int i=0;i\>strs;
V.clear();
int ll=strs.length();
for(int i=ll-1;i>=0;i–) V.push_back(strs[i]-‘0’);

int increased=0;

if(!havesame()) inc();
while(have99()) increased=1;
if(increased)
{
if(!havesame())
{
print();
return;
}
}

for(int i=ll-1;i>=1;i–)
if(V[i]==V[i-1])
{
V[i-1]++;
make01(i-2);
break;
}
print();
return;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

POCARI

include

using namespace std;

//获取重复的第一个位置
int repeatPos(string num)
{
int pos=0;
for(; pos<num.length()-1; pos++)
{
if(num[pos]==num[pos+1])
return pos+1;
}
return -1; //-1表示没有重复的
}

void setZero(string &num,int pos)
{
for(int i=pos+1,j=1; i<num.length(); i++)
{
if(j==1)
{
num[i]=‘0’;
}
else
{
num[i]=‘1’;
}
j*=-1;
}

}

//按位自加1
int selfAdd(string &num,int pos)
{
int addition=1;
for(; pos>=0&&addition>0; pos–)
{
int yu=(num[pos]+addition-‘0’)%10;
addition=(num[pos]+addition-‘0’)/10;
num[pos]=(char)(yu+‘0’);
}
if(addition>0)
num=”1”+num;
return pos+1; //表示从下一个开始变0和1的
}

//获取最终的结果
string getResult(string aim)
{
//重复的位置
if(repeatPos(aim)==-1)
{
selfAdd(aim,aim.length()-1);
if(repeatPos(aim)==-1)
return aim;
}

while(repeatPos(aim)!=-1)
{
    int pos=selfAdd(aim,repeatPos(aim));
    setZero(aim,pos);             //将剩余位设置成最简0和1
}
return aim;

}

int main()
{
vector aims;
string num=”“;
int volume;
cin>>volume;
//循环输入
for(int i=0; i>mid;
aims.push_back(mid);
}

int j=0;
for(string aim:aims)
{
    int number;
    //特判
    if(aim.length()<2)
    {
        sscanf(aim.c_str(),"%d",&number);
        printf("case #%d:\n%d\n",j,number+1);
    }else
    printf("case #%d:\n%s\n",j,getResult(aim).c_str());
    j++;
}
return 0;

}

POCARI

总的来说,数按位加1,进位的时候,将进位的位之后的位数全部赋值成0和1间隔。

10175102262 LarsPendragon
[已删除]
三七茧茧

这个代码把所有测试数据都跑过了。而测试数据都是‘9’,‘0’这种类型的。
但是,代码在跑类似于679893这种,出来的结果仍然是680101;而正解应该是679894;
有点迷……

Money4

加一用的楼上的方法= -

#include <bits/stdc++.h>
using namespace std;
string addOne(string a) {
    string ans;
    int sum, carry = 1;
    for (int i = a.size() - 1; i >= 0; --i) {
        sum = a[i] - '0' + carry;
        carry = sum / 10;
        ans.insert(0, 1, sum % 10 + '0');
    }
    if (carry != 0) {
        ans.insert(0, 1, carry + '0');
    }
    return ans;
}
string duplicate(string num){
    for(int i = 1 ; i < num.size(); i++){
        if(num[i] == num[i-1]) {
            string left = addOne(num.substr(0,i+1));
            for(int j = i + 1 ; j < num.size(); j++){
                left += '0';           //某位加一后 后面的位全都置0才最小
            }
            return duplicate(left);
        }
    }
    return num;
}
int main(){
    int T;
    cin>>T;
    for(int t = 0 ; t < T ; t++){
        string num;
        cin>>num;
        if(num.size()==1) {
            printf("case #%d:\n",t);
            printf("%s\n",addOne(num).c_str());
        }
        else{
            num = addOne(num);
            num = duplicate(num);
            printf("case #%d:\n",t);
            printf("%s\n",num.c_str());
        }
    }
}
你当前正在回复 博客/题目
存在问题!