首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >置换的玩笑

置换的玩笑

作者头像
Max超
发布2019-01-21 15:25:56
4450
发布2019-01-21 15:25:56
举报

题目

小蒜头又调皮了。这一次,姐姐的实验报告惨遭毒手。

姐姐的实验报告上原本记录着从 1 到 n 的序列,任意两个数字间用空格间隔。但是“坑姐”的蒜头居然把数字间的空格都给删掉了,整个数字序列变成一个长度为 1 到 100 的且首部没有空格的数字串。

现在姐姐已经怒了,蒜头找你写个程序快点把试验数据复原。

输入

输入文件有一行,为一个字符串——被蒜头搞乱的实验数据。

字符串的长度在 1 到 100 之间。

输出

输出共一行,为姐姐的原始测试数据—— 1 到 n 的输出。

任意两个数据之间有一个空格。

如果有多组符合要求的正确解,输出其中任意一组即可。

样例输入

4111109876532
样例输出

4 1 11 10 9 8 7 6 5 3 2

我这里用数组对输入的数字进行保存,然后用一个数组保存当前下标 计算所对应的数值。 先是用dfs做的,做完之后感觉可以用dp。

第一种dfs

#include<iostream>

int num[300];
int cur_index[300] = {0};//保存下标地址 
int result[300];//保存数值 
int index = 1;

using namespace std;
//将数组里的下标 a 到 b换成int型数字 
int atoin(int a,int b)
{
    int sum = 0;
    for(int i = a; i <= b; i++)
    {
        sum = sum*10+num[i];
    }
    return sum;
}
int check(int k)
{
    int j = 1;
    for(int i = 0; i < k; i++)
    {
        result[j] = atoin(cur_index[i]+1,cur_index[i+1]);
        j++;
    }
    j--;
    for(int i = 1; i < j; i++)
    {
        if(result[j]==result[i])
        {
            return 0;
        }
    }
    return 1;

}
//深度搜索 
void dfs()
{
    int k = 1;
    while(k>0)
    {
        if(cur_index[k]<=cur_index[k-1])
        {
            cur_index[k] = cur_index[k-1]+1;
        }
        else
        {
            cur_index[k]++;
        }
        int flag = check(k);
        while(cur_index[k]<=cur_index[k-1]+2&&!flag)
        {
            cur_index[k]++;
            flag = check(k);
        }
        if(cur_index[k]<=cur_index[k-1]+2&&cur_index[k]<index)
        {
            if(cur_index[k]==index-1)
            {
                for(int i = 1;result[i]!=0;i++)
                {
                    cout << result[i] << ends;
                }
                cout << endl;
                //return ;
            }
            else if(k<200)
            {
                k++;
            }
            else
            {
                cur_index[k] = 0;
                result[k] = 0;
                k--;
            }
        }
        else
        {
            cur_index[k] = 0;
            result[k] = 0;
            k--;
        }
    }
}

int main()
{
    do
    {
        char c;
        c = getchar();
        if(c=='\n')
        {
            break;
        }
        num[index] = c-'0';
        index++;
    }while(1);
    dfs();
    return 0;
}

第二种dp(目前不可以全部表示出来)

#include<iostream>

int num[300];
int cur_index[300] = {0};//保存下标地址 
int result[300];//保存数值 
int index = 1;

using namespace std;
//将数组里的下标 a 到 b换成int型数字 
int atoin(int a,int b)
{
    int sum = 0;
    for(int i = a; i <= b; i++)
    {
        sum = sum*10+num[i];
    }
    return sum;
}
int check(int k)
{
    int j = 1;
    for(int i = 0; i < k; i++)
    {
        result[j] = atoin(cur_index[i]+1,cur_index[i+1]);
        j++;
    }
    j--;
    for(int i = 1; i < j; i++)
    {
        if(result[j]==result[i])
        {
            return 0;
        }
    }
    return 1;

}
//利用动态规划的思想 
/*发觉这种动态规划试用于连续的*/
void dp()
{
    //cur_index[i]表示我只要选一个数值的状态
    for(int i = 1;cur_index[i-1]!=index-1; i++)
    {
        for(int j = cur_index[i-1]+1; j < index; j++)
        {
            cur_index[i] = j;
            if(check(i))
            {
                break;
            }
        }
    }
    for(int i = 1;result[i]!=0;i++)
    {
        cout << result[i] << ends;
    }
    cout << endl;
}
int main()
{
    do
    {
        char c;
        c = getchar();
        if(c=='\n')
        {
            break;
        }
        num[index] = c-'0';
        index++;
    }while(1);
    dp();
    return 0;
}

其实两种方法判断的条件都是相同的,不同是想题目的方式

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年03月25日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档