小易的字典

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/94563972

题目描述:

小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。

小易的这个字典很奇特, 字典内的每个单词都包含n个'a'和m个'z', 并且所有单词按照字典序排列。

小易现在希望你能帮他找出第k个单词是什么。

输入描述:

输入包括一行三个整数n, m, k(1 <= n, m <= 100, 1 <= k <= 109), 以空格分割。

输出描述:

输出第k个字典中的字符串,如果无解,输出-1。

输入样例:

2 2 6

输出样例:

zzaa

样例说明:

测试用例中字典里的字符串依次为aazz azaz azza zaaz zaza zzaa。

解题思路:

网易校招题。我一开始的想法就是暴力破解,先调用next_permutation来求全排列,然后将所有的字符串都存入unordered_map中,最后输出unordered_map中的第k个字符串即可,若无解则输出-1。然而我提交代码后出现了MLE 只通过30%的测试用例就出现内存超限啦。?

那没得一点办法 我只能把unordered_map去掉了,不再存储字符串,换成一个if语句,如果当前全排列的字符串是第k个就将它进行输出,如果无解就输出-1。然而这次提交代码后TLE了 通过50%的测试用例后就出现了运行超时。"100 100 1000000000"这个测试用例谁顶得住啊??

我哭了?今天运筹学考炸了,本来是想刷下题找成就感,结果这道题又是MLE又是TLE的。很显然网易不准C++玩家用next_permutation来暴力破解这道题。根据排列组合的知识可以知道,n个'a'和m个'z'只能组成

个字符串,我在这里暂且把

表示为C(n,n+m)吧。先假设第一个字符为'a',那么剩下n-1个'a'和m个'z'组成的子序列能构成字典中的前C(n-1+m,n-1)个字符串。然后比较k和C(n-1+m,n-1),这里有俩种情况:①若k小于等于C(n-1+m,n-1),就说明第k个字符串是字典里前C(n-1+m,n-1)个中的一个(显然该字符串的第一个字符必为'a'),所以该问题又可以缩减为在子序列(n-1个'a'和m个'z')找到第k个字符串。②若k大于C(n-1+m,n-1),就说明结果字符串ans是以'z'开头的字符串中的第k-C(n-1+m,n-1)个字符串,所以该问题又可以缩减为在子序列(n个'a'和m-1个'z')找到第k-count(n+m-1,m-1)个字符串。while(n&&m)循环结束后,剩余子序列中只存在"aaa...a"或"zzz...z"的情况,若k不为1则说明无解输出-1,否则在字符串ans后补'a'或'z',最后输出ans即可。提交代码终于AC了!含泪AC?。

AC代码:MLE代码:

#include <bits/stdc++.h>
using namespace std;

string init(int n,int m)    //初始化,得到字典中的第一个单词
{
    string ans = "";
    while(n--)
    {
        ans += 'a';
    }
    while(m--)
    {
        ans += 'z';
    }
    return ans;
}

int main()
{
    int n,m,k;   //字典中每个单词包含n个'a',m个'z',求第k个单词
    while(cin >> n >> m >> k)
    {
        string str = init(n,m);
        unordered_map<int,string> dictionary;   //小易的字典,key为单词,value为单词的次序
        int cnt = 0;    //计数器,记录当前字典的次序
        do{
            dictionary[++cnt] = str;   //存入字典中
        }while(next_permutation(str.begin(),str.end()));   //全排列
        cout << (k <= dictionary.size() ? dictionary[k] : "-1") << endl;   //输出字典中的第k个字符串,如果无解则输出-1
    }
    return 0;
}

AC代码:TLE代码:

#include <bits/stdc++.h>
using namespace std;

string init(int n,int m)    //初始化,得到字典中的第一个单词
{
    string ans = "";
    while(n--)
    {
        ans += 'a';
    }
    while(m--)
    {
        ans += 'z';
    }
    return ans;
}

int main()
{
    int n,m,k;   //字典中每个单词包含n个'a',m个'z',求第k个单词
    while(cin >> n >> m >> k)
    {
        bool flag = false;    //判断有无解,默认为false无解
        string str = init(n,m);
        int cnt = 0;   //计数器,用来记录当前字典中的单词个数
        do{
            if(++cnt == k)
            {
                flag = true;  //有解
                cout << str << endl;    //输出字典中第k个字符串
                break;
            }
        }while(next_permutation(str.begin(), str.end()));    //全排列
        if(!flag)   //若无解,则输出-1
        {
            cout << -1 << endl;
        }
    }
    return 0;
}

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m,k;   //字典中每个单词包含n个'a',m个'z',求第k个单词
    while(cin >> n >> m >> k)
    {
        string ans = "";
        while(n && m)
        {
            long long cnt = 1;   //一定要long long
            for(int i = 1; i < n; i++)    //求组合数
            {
                cnt *= (n+m-i);
                cnt /= i;
                if(cnt > k) break;   //防止越界,cnt>k就跳出for循环
            }
            if(k <= cnt)
            {
                ans += "a";
                n--;   //问题缩减为n-1个a和m个z中找第k个字符串
            }
            else
            {
                ans += "z";
                m--;
                k -= cnt;   //问题缩减为n-1个a和m个z中找第k-cnt个字符串
            }
        }
        if(k != 1)    //若k不为1说明无解
        {
            cout << -1 << endl;
        }
        else
        {
            //while(n&&m)循环结束后,剩余子序列中只存在"aaa...a"或"zzz...z"的情况
            while(n--)
            {
                ans += "a";
            }
            while(m--)
            {
                ans += "z";
            }
            cout << ans << endl;
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【PAT乙级】单身狗

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 字符串长度最大乘积

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【蓝桥杯】BASIC-12 十六进制转八进制

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • Bad Rabbit病毒引发的企业数据安全的思考与应对方案

    十月底,欧洲地区爆发新型勒索病毒Bad Rabbit,感染范围包含俄罗斯、乌克兰、德国等多个东欧国家。据国内网络安全企业介绍,该病毒伪装成Adobe flash...

    数据和云
  • 老司机告诉你:正规的运维工作是什么的?

    联网运维工作,以服务为中心,以稳定、安全、高效为三个基本点,确保公司的互联网业务能够 7×24 小时为用户提供高质量的服务。

    小小科
  • 运维工作到底是做什么的?

    互联网运维工作,以服务为中心,以稳定、安全、高效为三个基本点,确保公司的互联网业务能够 7×24 小时为用户提供高质量的服务。

    用户6543014
  • 史上最全互联网运维工作规划!十分钟找到职业方向!

    互联网运维工作,以服务为中心,以稳定、安全、高效为三个基本点,确保公司的互联网业务能够7×24小时为用户提供高质量的服务。 运维人员对公司互联网业务所依赖的基础...

    小小科
  • etcd v2文档(2) -- 客户端http请求管理集群成员api

    solate
  • 一个真实的DevOps演进过程是啥样的?

    前几天听老王分享,提到关于DevOps在国内外的发展问题,其中就说到早期腾讯做运维时,那个时候也没什么意识是DevOps,其实就是在变态的业务体量下面一步步做出...

    赵成
  • 实践:在运维大数据这事上,Apache Kylin比ELK更擅长?

    他居然不假思索,略带调侃的回答我, “背锅” 与 “惊醒”,随即愣了一下,改口说,“发布” 与 “排障”。

    吃草的罗汉

扫码关注云+社区

领取腾讯云代金券