idea 常用快捷键 drupal7 seo mui vue前端开发 后台模板 linux内存管理 进销存源码 linux源码在线阅读 华为路由器ipv6配置 ps字体旋转角度 java 数据分析 mysql增删改查语句 less比较级 python相对路径怎么写 excel带格式复制粘贴 docker启动命令 python运算符优先级 python分析 java编程基础 java数据库连接 java数组追加 java新建文件 javac linuxgrep 海妖花粉哪里多 stretchcolumns 手机模拟器下载 2k14生涯模式修改器 骰子表情 什么软件买电影票便宜 红巨人插件 cubase下载 安卓adb 3dmax2014下载 appdata是什么文件夹 fireworks序列号 死从天降成就 qq空间自动点赞 极速pdf转word
当前位置: 首页 > 学习教程  > 编程语言

c++ Gym - 101020I-Playing With String SDUT

2020/8/11 20:09:45 文章标签:

在这里插入图片描述
在这里插入图片描述
题目大意:给出一个字符串,判断其是否是回文串,如果不是是否能经过交换字母的位置变成回文串,如果不能输出“impossible”,如果能输出该字符串的回文串,如果有多个回文串输出字典序小的串,如abcba和bacab都满足条件但是a的字典序小所以a应该在前输出abcba

思路:有一个数组储存字符串中每一个字符出现的次数,如果其中有字符出现次数为奇数但只有一个字符出现次数为奇数,或所有字符出现次数都为偶数,则可以形成回文串,否则不能形成回文串,输出时按照从前到后的顺序输出一般字符,然后再从后向前输出另一半字符,就是符合条件的字典序小的回文串

#include <iostream>
#include <string.h>

using namespace std;

int main()
{
    int t;
    char str[1005];
    int vis[29];//储存每个字符出现的次数
    cin >> t;
    while (t--)
    {
        memset(vis, 0, sizeof(vis));
        cin >> str;
        for (int i = 0; str[i]; i++)
        //统计每个字符出现的次数
        {
            vis[str[i] - 'a']++;
        }
        int flag = -1, cnt = 0;//储存出现次数为奇数的字符是哪个,标记是否有出现次数为奇数的字符
        for (int i = 0; i < 26; i++)
        //判断出现次数为奇数的字符有多少个
        {
            if (vis[i] % 2 != 0)
            {
                flag = i;
                cnt++;
            }
        }
        
        if (cnt > 1)
        //如果有多余一个的字符出现次数为奇数
        {
            cout << "impossible\n";
        }
        else
        {
            for (int i = 0; i < 26; i++)
            //先输出一般字符
            {
                for (int j = 0; j < vis[i] / 2; j++)
                {
                    printf("%c", i + 'a');
                }
                vis[i] /= 2;//没输出一个字符将其个数除以2
            }
            if (cnt == 1)//如果有出现次数为奇数的字符
            {
                printf("%c", flag + 'a');
            }
            for (int i = 25; i >= 0; i--)
            //逆序输出另一半字符
            {
                for (int j = 0; j < vis[i]; j++)
                {
                    printf("%c", i + 'a');
                }
            }
            printf("\n");
        }
    }
}


本文链接: http://www.dtmao.cc/news_show_100293.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?