一道简单题看 y 总 C++ 代码风格优于我自己的地方

Piper蛋窝

发布于 2021-08-20 11:00:28

4430

发布于 2021-08-20 11:00:28

文章被收录于专栏：Piper蛋窝Piper蛋窝

题目

原题：AcWing 3805. 环形数组[1]

给定一个长度为

的由小写字母构成的字符串

。

请你构造一个长度为

的由小写字母构成的字符串

。

要求，字符串

需满足：

字符串

在字典序上大于字符串

。

字符串

的字母集是字符串

的字母集的子集。一个字符串的字母集是指该字符串包含的所有不同字母的集合，例如 abadaba 的字母集为

\{a,b,d\}

。

字符串

在字典序上尽可能小。

保证答案存在。

输入格式

第一行包含整数

，表示共有

组测试数据。

每组数据第一行包含两个整数

和

。

第二行包含一个长度为

的字符串表示

。

输出格式

每组数据输出一行满足所有条件的字符串

。

数据范围

前三个测试点满足

1 \le n,k \le 3

。

所有测试点满足

1 \le T \le 10

，

1 \le n,k \le 10^5

。

同一测试点内，所有

的和不超过

10^5

，所有

的和不超过

10^5

。

输入样例：


4
3 3
abc
3 2
abc
3 3
ayy
2 3
ba

输出样例：


aca
ac
yaa
baa

思路：分情况讨论

当 k 大于 n 时，前 n 位不变，我们让 n 位开始填补出现过的最小字符就行
当 k 小于等于 n 时，我们从原字符串 k - 1 位开始往前找，如果当前字符还有变小的可能，那么就让其变小，寻找停止，输出新字符串

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, k;
bool used[26];
string s, t;

string tail()
{
    int i = 0;
    for (; i < 26; ++ i)
        if (used[i]) break;
    char a = 'a' + i;
    string res(k - n, a);
    return res;
}

string get()
{
    char max_char;
    for (int i = 25; i >= 0; -- i)
    {
        if (used[i])
        {
            max_char = 'a' + i;
            break;
        }
    }
    char min_char;
    for (int i = 0; i < 26; ++ i)
    {
        if (used[i])
        {
            min_char = 'a' + i;
            break;
        }
    }
    
    int i = k - 1;
    for (; i >= 0; -- i)
    {
        if (s[i] != max_char) break;
    }
    
    string res1 = s.substr(0, i);
    string res2;
    for (int j = s[i] - 'a' + 1; j < 26; ++ j)
    {
        if (used[j])
        {
            res2 = (char) 'a' + j;
            break;
        }
    }
    string res3(k - i - 1, min_char);

    return res1 + res2 + res3;
}

int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        cin >> n >> k;
        cin >> s;
        memset(used, 0, sizeof used);
        for (int i = 0; i < s.size(); ++ i) used[s[i] - 'a'] = true;
        if (k > n)
        {
            t = s + tail();
        }
        else
        {
            t = get();
        }
        cout << t << endl;
    }
}

可以看出我的代码思路很清晰，但是写得有一点冗余。

y 总代码

看看 y 总的代码。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k;
char s1[N], s2[N];
bool st[26];

char get_min()
{
    for (int i = 0; i < 26; i ++ )
        if (st[i])
            return i + 'a';
    return -1;
}

char get_next(int t)
{
    for (int i = t + 1; i < 26; i ++ )
        if (st[i])
            return i + 'a';
    return -1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &k);
        scanf("%s", s1);
        memset(st, 0, sizeof st);
        for (int i = 0; i < n; i ++ ) st[s1[i] - 'a'] = true;
        if (k > n)
        {
            printf("%s", s1);
            char c = get_min();
            for (int i = n; i < k; i ++ ) printf("%c", c);
            puts("");
        }
        else
        {
            s2[k] = 0;
            for (int i = k - 1; i >= 0; i -- )
            {
                char c = get_next(s1[i] - 'a');
                if (c != -1)
                {
                    s2[i] = c;
                    for (int j = 0; j < i; j ++ ) s2[j] = s1[j];
                    break;
                }
                s2[i] = get_min();
            }
            puts(s2);
        }
    }

    return 0;
}

// 作者：yxc
// 链接：https://www.acwing.com/activity/content/code/content/1634481/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

很简洁。

经验：

char s[]; puts(s); 中， puts 遇到 \0 注意是 char s[k] = 0 而不是 char s[k] = '0' 字符串停止输出。

参考资料

[1]

AcWing 3805. 环形数组: https://www.acwing.com/activity/content/problem/content/5457/

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-08-16，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 Piper蛋窝微信公众号，前往查看

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

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

编程算法

登录后参与评论

0 条评论

热度