首页 > 试题广场 > 多多的电子字典
[编程题]多多的电子字典
  • 热度指数:1960 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
多多鸡打算造一本自己的电子字典,里面的所有单词都只由a和b组成。
每个单词的组成里a的数量不能超过N个且b的数量不能超过M个。
多多鸡的幸运数字是K,它打算把所有满足条件的单词里的字典序第K小的单词找出来,作为字典的封面。

输入描述:
共一行,三个整数N, M, K。(0 < N, M < 50, 0 < K < 1,000,000,000,000,000)


输出描述:
共一行,为字典序第K小的单词。
示例1

输入

2 1 4

输出

ab

说明

满足条件的单词里,按照字典序从小到大排列的结果是
a
aa
aab
ab
aba
b
ba
baa

备注:
对于40%的数据:0 < K < 100,000

对于100%的数据:0 < K < 1,000,000,000,000,000

题目保证第K小的单词一定存在

由不同的前缀ab构成了两个子树,找第k个元素实际上就是先序遍历的过程,通过求子树中的唯一字符串个数可以快速地跳过一些无关的子树。

直接先序遍历往往会有过大的时间复杂度,可以通过带备忘录的递归算法求解出f(n,m)的值,从而避免大量的重复运算。

Base case:只有m或n不为零,则直接返回对应的值。

# 计算包含N个a和M个b的子字典树包含的unique字符串的个数,从而和K进行
# 比较,以便选择跳过该子树或者进入该子树
count_dict = {}
def calc_subtree_str_num(N,M):
    if (N,M) in count_dict.keys():
        return count_dict[(N,M)]
    elif N == 0:
        count_dict[(N,M)] = M
    elif M == 0:
        count_dict[(N,M)] = N
    else:
        #分别以a和b得到的两个子树的个数统计加上a和b这两个节点
        count_dict[(N,M)] = calc_subtree_str_num(N-1,M) + calc_subtree_str_num(N,M-1) + 2
    return count_dict[(N,M)]

def main():
    N,M,K = list(map(int,input().split()))

    res = ""
    #当K=0时就找到了对应的字符串
    while K > 0:
        # 一般情况 N 和 M 都存在
        if N > 0 and M > 0:
            #获取当前情况下左子树的字符串个数,如果大于K说明结果在右子树
            left_str_cnt = calc_subtree_str_num(N-1, M)+1
            if K <= left_str_cnt:
                # 说明第k个在a子树下,添加字符'a',并继续循环向下判断
                res += 'a'
                K -= 1 
                N -= 1
            else:
                # 在右子树下,K可以跳过left_str_cnt+1个值,1为左子树根节点'a',配合上前缀也是一个unique的str
                res += 'b'
                K -= (left_str_cnt + 1)
                M -= 1
        #其他情况,N=0或者M=0时只需要一直添加字符即可,因为题上的说明不用考虑不存在
        elif N == 0 and M > 0:
            res += 'b'
            K -= 1
            M -= 1
        elif M == 0 and N > 0:
            res += 'a'
            K -= 1
            N -= 1
    return res

print(main())
发表于 2020-07-09 21:44:46 回复(7)
 
回溯不可以的话,相当N特别大,所以考虑用字典序在O(N)复杂度下解决该问题。 
字典序又叫trie树,该算法思想在实际生活中大量应用。 
默认大家有trie树的基础知识,下面这种方式就是根据构建的字典序进行适当的剪枝,因为我们并不需要遍历每一颗树。 只需要通过数学公式推导出我们想要的结果在哪个子树即可。
本题相当于有两个树,以a开头和以b开头的两颗二叉树。 每一次的cal_step函数是返回以当前节点"a"或者"b"开头的前序遍历需要经过的步数,这个不是由动态规划得到一个dp二维数组,然后直接返回即可。 
这里说一下动态规划的递推公式: dp[i][j] = dp[i-1][j] + 1 + dp[i][j-1] + 1 什么意思呢? 我看评论里也有人说了,就是返回以"a"开头的和以"b"开头的个数。 可能有人还是不理解,这个时候拿出笔来写一写就明白了。
比如a[2][1] = dp[1][1] + dp[2][0] + 2 dp[1][1] + 1是以"a"开头的个数,即我们可以固定一个"a"在开头
这样就少了一个a可以用,那么只剩下了[a,b]可以组合 即:a,ab,ba,b; 然后再和固定的a开头的字母"a"组合,即aa,aab,aba,ab,这个时候组合就相当于是dp[1][1] 
以a开头的组合显然少了一个"a"这个特殊的组合,显然dp[1][1] + 1才是以"a"开头的组合个数。
题解如下: 



line = list(map(int,sys.stdin.readline().strip().split())) n = line[0] m = line[1] k = line[2] class Solution:     map = dict()     def findKthNumber(self, n: int, m: int, k: int) -> int:         # dp[i][j] 表示i个a,j个b所能构成的字母组合         dp = [[0] * (m + 1) for _ in range(n + 1)]         for i in range(n + 1):             dp[i][0] = i         for i in range(m + 1):             dp[0][i] = i         for i in range(1, n + 1):             for j in range(1, m + 1):                 # i个a和j个b组成的个数为以a开头的和以b开头的加上特殊的a和b                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 2         def cal_step(n, m):                 return dp[n][m] + 1         cur = "a"         # 第一次,应该是以'a'开头的         n -= 1         k -= 1         while k > 0 and (n or m):             step = cal_step(n, m)             if step <= k:  # k在下一个子树中                 k -= step                 # 此时的n,m是为了计算dp[m][n]                 # 一轮过后,需要计算以b开头的,所以m-=1,n+=1                 n += 1                 m -= 1                 cur = cur[:-1] + "b"             else:  # 在子树中                 k -= 1                 if n:                     cur += "a"                     n -= 1                 else:                     cur += "b"                     m -= 1         return cur print(Solution().findKthNumber(n, m, k))

编辑于 2020-07-02 20:57:33 回复(0)
java
dp[n][m]表示n个a,m个b的单词数量
dp[n][m] = 1 + dp[n-1][m] + 1 + dp[n][m-1]
根据K倒推,是前半部分,还是后半部分,来确定第一个字母是 a,还是b
注意dp[n][m] 可能超过long类型的范围,所以,用BigInteger来存dp
import java.util.*;
import java.math.*;
public class Main{
    public static void main(String[] args){
        BigInteger[][] dp = new BigInteger[50][50];
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        long K = sc.nextLong();
        for(int i=0;i<=N;i++){
            dp[i][0] = new BigInteger(Integer.toString(i));
        }
        for(int i=0;i<=M;i++){
            dp[0][i] = new BigInteger(Integer.toString(i));
        }
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                //dp[i][j] = 1+dp[i-1][j] + 1+ dp[i][j-1];
                dp[i][j] = dp[i-1][j].add(dp[i][j-1]).add(new BigInteger("2"));
            }
        }
        StringBuilder sb = new StringBuilder();
        int n = N, m = M;
        long k = K;
        while(k>0){
            if(n>0 && m>0){
                if(dp[n-1][m].compareTo(new BigInteger(Long.toString(k-1)))>=0){//k<=dp[n-1][m]+1
                    k--;
                    sb.append('a');
                    n--;
                }else{ //k>dp[n-1][m]+1
                    k -= dp[n-1][m].longValue()+2;
                    sb.append('b');
                    m--;
                }
            }else if(n>0 && m==0){
                k--;
                sb.append('a');
                n--;
            }else if(n==0 && m>0){
                k--;
                sb.append('b');
                m--;
            }else{
                k=0;
            }
        }
        System.out.println(sb.toString());
    }
}


发表于 2020-05-27 19:12:38 回复(4)
#include <iostream>
#include <string>
#include <map>
using namespace std;
map<pair<int,int>,unsigned long long> ma;

unsigned long long f(int m,int n)
{
    if(ma.count({m,n}))return ma[{m,n}];
    if(!m)ma[{m,n}]=n;
    else if(!n)ma[{m,n}]=m;
    else ma[{m,n}]=f(m-1,n)+f(m,n-1)+2;
    return ma[{m,n}];
}

int main()
{
    long long k;
    int n,m;
    cin>>n>>m>>k;
    string cur="a";
    n--;
    k--;
    while(k>0&&(m||n))
    {
        unsigned long long step=f(n,m)+1;//子树的个数
        if(step>k)//k在子树中
        {
            k--;
            if(n)
            {
                cur+="a";
                n--;
            }else{
                cur+="b";
                m--;
            }
        }else{//k不在子树中,在下一个子树里
             k-=step;
             n++;
             m--;
             cur.back()++;
        }
    }
    cout<<cur<<endl;
    return 0;
}
参考leetcode 440写的,对比那个题目特殊的地方在于用map记录a个数小于n且b个数小于m的所有排列个数,从而防止重复计算。基本的思路在于构建一个字典树,然后对这个字典树进行先序遍历,必要时进行剪枝,
编辑于 2020-05-20 19:49:26 回复(6)
我来解释一下为什么其他回答的递归为dp[m][n] = dp[m][n - 1] + dp[m-1][n] + 2吧。
假设m个a,n个b:
那么第一个字母为a的个数为dp[m - 1][n] + 1 (额外加1是为了包括总长度为1的情况, 即'a')
那么第一个字母为b的个数为dp[m][n - 1] + 1 (额外的1是为了包括总长度为1的情况,即'b')
所以,dp[m][n] = dp[m][n - 1] + dp[m-1][n] + 2。
发表于 2020-06-01 22:15:42 回复(0)
贡献一份C++代码,我裂开了,用递归居然超时了,你们把递归改成非递归应该不会超时。
#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution{
  public:
    vector<string> res;
    vector<string> Magic_box(int n,int m,string tmp)
    {
            if(n!=0)
            {
                tmp.push_back('a');
                res.push_back(tmp);
                Magic_box(n-1,m,tmp);
                tmp.pop_back();
            }
            if(m!=0)
            {
                tmp.push_back('b');
                res.push_back(tmp);
                 Magic_box(n,m-1,tmp);
                 tmp.pop_back();
            }
            return res;
           
    }
};


int main()
{
    Solution s;
    string tmp="";
    int n,m,k;
    cin>>n;
    cin>>m;
    cin>>k;
    auto str=s.Magic_box(n,m,tmp);
    for(int i=0;i<str[k-1].size();i++)
    {
        cout<<str[k-1][i];
    }
    return 0;
}


发表于 2020-06-25 11:04:05 回复(0)

添加个golang的解析,思路与其他人差不多

package main

import "fmt"

func main() {
    n, m, k := 0, 0, 0
    fmt.Scanf("%d %d %d", &n, &m, &k)
    dp := make([][]uint64, n+1)
    //构造动态规划二维数组dp[n][m]
    //dp[i][j]代表i个a,j个b所能拼接出的所有可能字符串的数量
    for i := 0; i <= n; i++ {
        dp[i] = make([]uint64, m+1)
        dp[i][0] = uint64(i)
    }
    for j := 0; j <= m; j++ {
        dp[0][j] = uint64(j)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            dp[i][j] = 1 + dp[i-1][j] + 1 + dp[i][j-1]
        }
    }
    res := ""
    tmp := uint64(k)
    ac, bc := n, m
    for tmp != 0 {
        //如果b的数量没了,则剩下的要填补a
        if bc == 0 {
            var i uint64
            for i  = 0; i < tmp; i++ {
                res += "a"
            }
            break
        }
        //如果a的数量没了,则剩下的要填补b
        if ac == 0 {
            var i uint64
            for i = 0; i < tmp; i++ {
                res += "b"
            }
            break
        }
        // 如果当前的字符是a 则tmp的上限是 1+dp[ac-1][bc](dp[ac-1][bc]为ac-1个a,bc个b 所能拼接出的所有可能字符串的数量);
        // 否则 当前字符应该是b
        if tmp <= 1+dp[ac-1][bc] {
            res += "a"
            tmp -= 1
            ac--
        } else {
            res += "b"
            tmp -= 1 + dp[ac-1][bc] + 1
            bc--
        }
    }
    fmt.Printf("%s",res)
}
发表于 2020-06-09 21:24:03 回复(0)
def getcount(map,m,n):
    if not m:
        map[(m,n)]=n
    if not n:
        map[(m,n)]=m
    elif (m,n) in map:
        return map[(m,n)]
    else:
        #+'a'就是getcount(map,m-1,n)+1,加'b'同理
        map[(m,n)]=getcount(map,m-1,n)+getcount(map,m,n-1)+2
    return map[(m,n)]


def mink(n,m,k):
    cur=""
    map= {}
    while k>0 :
        if n>0 and m==0:#只有'a'存在
            k-=1
            cur+="a"
            n-=1
        elif m>0 and n==0: #只有'b'存在
            cur+='b'
            k-=1
            m-=1
        elif n>0 and m>0 :#都存在时
            #计算a下所有子节点的和
            cnt=getcount(map,n-1,m) +1
            if cnt>=k:#在a子树下
                cur+='a'
                k-=1 #k相当于横向遍历,每次向右遍历一个节点
                n-=1
            else:#在b子树下
                cur+='b'
                m-=1
                k-=(cnt+1) #k要减去a子树的所有节点个数
    return cur


from collections import defaultdict

ss=list(map(int,input().split()))
n=ss[0]
m=ss[1]
k=ss[2]
p=mink(n,m,k) 
print(p)

发表于 2020-07-02 15:46:55 回复(0)
#include<iostream> #include<vector> #include<string> using namespace std; class Solution{ public: vector<string> res; vector<string> Magic_box(int n,int m,string tmp) { if(n!=0) { tmp.push_back('a'); res.push_back(tmp); Magic_box(n-1,m,tmp); tmp.pop_back(); } if(m!=0) { tmp.push_back('b'); res.push_back(tmp); Magic_box(n,m-1,tmp); tmp.pop_back(); } return res; } }; int main() { Solution s; string tmp=""; int n,m,k; cin>>n; cin>>m; cin>>k; auto str=s.Magic_box(n,m,tmp); for(int i=0;i<str[k-1].size();i++) { cout<<str[k-1][i]; } return 0; }
发表于 2020-09-05 15:07:12 回复(0)
global rec
rec = {}
def count(N, M):
    global rec
    if not N:
        return M 
    if not M:
        return N 
    if (N, M) in rec:
        return rec[(N, M)]
    rec[(N, M)] = count(N-1, M) + 1 + count(N, M-1) + 1
    return rec[(N, M)]

def helper(N, M, K):
    global rec, ans
    count(N, M)
    ans = ''
    def dfs(N, M, K, res):
        global ans
        if K<=0:
            ans = res
            return
        elif not N:
            ans = res + 'b' * K
            return 
        elif not M:
            ans = res + 'a' * K 
            return 
        #print(N, M, K, count(N-1, M))
        if count(N-1, M)+1 >= K:
            dfs(N-1, M, K-1, res+'a')
        else:
            dfs(N, M-1, K-count(N-1, M)-2, res+'b')
    dfs(N, M, K, '')
    print(ans)

发表于 2020-08-02 17:06:23 回复(0)
字典序问题,我的思路是一个字母一个字母判断接下来的字母是是什么。
比如例子中的aab三个字母, 首先第一个字母如果是b,则index应该是大于等于 1 +(第一个字母是a的情况下,剩下的字母有几种情况) + 1 =6
如果所给的K>6则第一个字母是b,否则则是a,
接下来依次判定下一个字母,记得加上前一个字母的index。直到我们的index==K,或者其中一个字母用完。
其中比较关键要解决的是 N个a,M个b可以有多少种排列
n个元素被分成K类,每类的个数分别是n1,n2,…,nk这n个元素的全排列数为n!/(n1!xn2!x…xnk!)
当字母个数x小于等于min(N,M),排列有2^x ,当大于min(N,M)时,就要考虑取几个a,或b。这时候就用列举用上面的公式解决。
import java.math.BigDecimal;
import java.util.Scanner;
 
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //N个a
        int N = sc.nextInt();
        //M个b
        int M = sc.nextInt();
        //第K个单词
        long K = sc.nextLong();
 
        System.out.println(dic(N,M,K));

 
    }
    //N个a,M个b
    public static String dic(int N, int M, long K){
        BigDecimal index = BigDecimal.valueOf(0);
        StringBuilder s = new StringBuilder();
        int num_a = N;
        int num_b = M;
        while (BigDecimal.valueOf(K).compareTo(index) > 0 && num_a!=0 && num_b!=0){
            if (BigDecimal.valueOf(K).compareTo(index.add(cal(num_a - 1, num_b)).add(BigDecimal.valueOf(2))) > 0){
                s.append("b");
                index = index.add(cal(num_a - 1, num_b)).add(BigDecimal.valueOf(2));
                num_b--;
            }
            else if (BigDecimal.valueOf(K).compareTo(index.add(cal(num_a - 1, num_b)).add(BigDecimal.valueOf(2))) == 0){
                s.append("b");
                return s.toString();
            }
            else {
                s.append("a");
                index = index.add(BigDecimal.valueOf(1));
                num_a--;
            }
        }
        if (num_a==0){
            for (long i =0;i<K-index.longValue(); i++){
                s.append("b");
            }
        }
        if (num_b==0){
            for (long i =0;i<K-index.longValue(); i++){
                s.append("a");
            }
        }
 
        return s.toString();
 
    }
 
    //解决 x个a和y个b有多少种排列方式
    public static BigDecimal cal(int x, int y){
        BigDecimal res = BigDecimal.valueOf(0);
        int min = Math.min(x,y);
        int max = Math.max(x,y);
        for (int i=1; i<=min; i++){
            res = res.add(new BigDecimal(2).pow(i));
        }
        for (int i = min+1; i<=x+y; i++){
            BigDecimal e = BigDecimal.valueOf(0);
            for (int j = min ;j>=i-max;j--){
                e = e.add(doFactorial(i).divide((doFactorial(j).multiply(doFactorial(i - j))), 2));
            }
            res  = res.add(e);
        }
        return res;
    }
 
    public static BigDecimal doFactorial(int n){
        if(n<0){
            return BigDecimal.valueOf(-1);//传入的数据不合法
        }
        if(n==0){
            return BigDecimal.valueOf(1);
        }else if(n==1){//递归结束的条件
            return BigDecimal.valueOf(1);
        }else{
            return BigDecimal.valueOf(n).multiply(doFactorial(n-1));
        }
    }
 
}


发表于 2020-05-20 10:09:48 回复(0)