博客

时隔好久做点算法题是真的手生，今天一波笔试效果较差，补道题吧。

题意：  将1到n所有数按字典序排序，输出序列。

思路：  将数字按字典序排列，显然，应该一位一位的分析，开始的思路是数位DP（实际上也确实是），不过错了，这里犯的一个问题就是：我的想法是先求出来n的位数m，然后从最高位向低位走过去，中间从0-9循环，就能出来0001,0002，0003，，，，，0010,0011，,0012，，，1000，1001,1002，，，类似的顺序，再dfs的dp过程中将参数sum逐步*10加该位以实现去0。由于手有点生，写了一半才开始考虑到数位dp的基本参数limit判断是否前导为0，不过还是处理掉了。但是结果运行出来并没如愿，这样考虑固然是出来了上述的序列，但结合其递归顺序仔细观察上述序列才发现这个数列并不是想要的字典序，而是我废了老大劲得到的顺序序列，一时间有点尴尬的。

继续考虑下去，正确的解法，应该是从低位起向高位走，也不是，还是从高位起走，不过是从高位起，但并不把该位当做当前参数p所代表的位；而是从高位起走，把当前位当做最低位，也就是不考虑那么多0，而是把0001,0002，，，前面的0直接不考虑，把0010,0011，，，，。即把本该在p=4时才应该考虑的个位向前移动到p=0时应考虑的万位上，本该在p=3时才应该考虑的十位也向前移动到p=0时应考虑的万位上，这样就能得到了1，10,100，1000，也就是字典序。

另外使用到 atoi()函数，百度如下。

实现简单，但省得自己循环麻烦了，以后常用吧。

C语言库函数名

原型

int atoi(const char *nptr);

代码如下：

#include <iostream>
#include <cassert>
#include <stdlib.h>
using namespace std;
const int MAX_LEN = 12;
char a[MAX_LEN];

//引用参数k，注意用处！！！！
//       n     位数     k个数    当前位
void topK(int n, int m, int &k, int p)
{
    if (k <= 0 || p >= m)
        return;
    for (int j = 0; j < 10; j++)
    {
        a[p] = j + '0';
        a[p+1] = '\0';
        //atoi (表示 ascii to integer)是把字符串转换成整型数的一个函数
        int v = atoi(a);
        // 判断该数的条件
        // 1、大于等于1    2、小于等于n    3、k个数以内
        if (v >= 1 && v <= n && k > 0)
        {
            cout << a << endl;
            k--;
            topK(n, m, k, p+1);
        }
    }
}
int main()
{
    int n;
    int k;  // k表示要输出k个数,用做计数，也可以用全局变量代替引用参数！
    cin >> n;
    k = n;
    int m = 0;  //n 的位数
    int p = n;
    while (p > 0)
    {
        m ++;
        p /= 10;
    }
    //从0位开始
    topK(n, m, k, 0);
    return 0;
}