标签： 递归

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

 

示例 1：

输入：digits = ["1","3","5","7"], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：

输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

示例 3:

输入：digits = ["7"], n = 8
输出：1

 

提示：

• 1 <= digits.length <= 9
• digits[i].length == 1
• digits[i] 是从 '1' 到 '9' 的数
• digits 中的所有值都 不同 
• digits 按 非递减顺序 排列
• 1 <= n <= 109

数学方法+递归，10月18日，今天的每日一题，有空偷个闲撸一把

看到题目第一反应是动态规划，然后扫了下题目给了示例，看到这么一段

输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

突然灵光一闪，可以直接用数学方法来解

拿其中的一个示例稍微改下来分解运算试试看，粗略的分解如下

输入：digits = ["1","3","5","7"], n = 1571

 1 5 7 1

 4
 16   4*4
 64   4*4*4
 45   0*4*4*4 + 1 * (2*4*4 + 1 * (3*4 + 1*( 0 + 1*(1))))

最终验证得到 4 + 16 + 64 + 45 = 129 确定正确
如果你能看懂上面最后一行 4位数的组合数量计算公式的话，那么说明你就已经GET到了

数字1571一共有4位，那么我们将结果分为两部分，不满足4位的和满足4位的结果分开计算

在不满足4位的部分

1. 如果只列举一位，那么就有String[] digits种方案，每一个数字都可以列举一次
2. 如果要列举两位数字的情况，那么每一位都可以列举String[] digits种方案，在本示例中即为4 * 4种
3. 如果要列举三位数字的话，那么同理有4 * 4 * 4中，因为位数小于目标数字n = 1571的4位，所以可以任意组合，不要考虑结果是否会大于1571

接下来第二部分，需要组合4位数字的情况

1. 我们先取出目标数字1571的第一位数字1,拿到digits数组中比较，发现小于1的没有，但是有等于1的情况
2. 如果digits中存在小于当前位数字的lessCnt个，那么后面的排列组合可以不考虑。即有lessCnt * digits.length * ...... * digits.length种组合情况
3. 如果digits中没有当前位的数字，在处理了上一位小于的情况之后，说明后面无论怎么样排序都不会有满足结果小于目标值的情况
4. 如果存在有等于当前位的数字，那么，我们需要再往后看一位，此时回到了和步骤1相同的处理逻辑部分
5. 那么第二位是5，digits数组中有[1,3]是小于5的，即可以有两种情况，后面无论如何排列都是满足的，那么得到2 * 4 * 4
6. 又digits数组中也包含了5，我们继续看下一位数字7
7. digits数组中有[1,3,5]小于7，于是有新的可能组合数量 3 * 4，且数组中有数字7，那么继续看下一位数字
8. 最后一位数字1，同样的，数组中小于1的数字不存在，那么即有0种情况，后面没有4要乘了
9. 同时数组中包含了1，所以继续看下一位
10. 最后已经没有下一位了，这里需要返回个1，根据前一步的结果返回0的话显然会造成结果不正确

代码

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        int size = getSize(n);
        int ans = 0;
        int t = digits.length;
        //低位数的直接相加
        while (--size>0){
            ans += t;
            t *= digits.length;
        }
        int[] intDigtis = getIntDigtis(digits);
        int[] nArr = getNArr(n);
        //最高位数的分区段统计数量
        ans += splitCnt(intDigtis,nArr, 0);
        return ans;
    }

    int splitCnt(int[] digits, int[] arr, int idx){
        if (idx == arr.length){
            return 1;
        }
        //比arr[idx]小的数字有个lessCnt个，相等的有equalCnt个
        int lessCnt = 0;
        int equalCnt = 0;
        for (int i = 0; i < digits.length; i++) {
            if (digits[i] > arr[idx]){
                break;
            }
            if (digits[i] < arr[idx]){
                lessCnt++;
            }
            if (digits[i] == arr[idx]){
                equalCnt++;
            }
        }
        for (int i = idx+1; i < arr.length; i++) {
            lessCnt *= digits.length;
        }
        return lessCnt + (equalCnt * splitCnt(digits,arr,idx+1));
    }

    final static int[] mod = {
            0,
            1,
            10,
            100,
            1000,
            10000,
            100000,
            1000000,
            10000000,
            100000000,
            1000000000
    };

    final static int [] sizeTable = {
            9,
            99,
            999,
            9999,
            99999,
            999999,
            9999999,
            99999999,
            999999999,
            Integer.MAX_VALUE
    };

    static int getSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }

    int[] getIntDigtis(String[] digtis) {
        int[] intDigtis = new int[digtis.length];
        for (int i = 0; i < digtis.length; i++) {
            intDigtis[i] = digtis[i].charAt(0)-'0';
        }
        return intDigtis;
    }

    int[] getNArr(int n){
        int size = getSize(n);
        int[] nArr = new int[size];
        int i = size;
        while (n > 0){
            nArr[size-i] = n/mod[i];
            n %= mod[i];
            i--;
        }
        return nArr;
    }
}

思路想明白了的话，还是不算太复杂的，主要是全位数部分计算的方法要递归起来实现的话，略微有点点显得绕

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

 

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

 

提示：

• 1 <= n <= 9
• 1 <= k <= n!

class Solution {

    boolean[] usedNums;

    public String getPermutation(int n, int k) {
        k--;
        usedNums = new boolean[n+1];
        int[] factorial = new int[n];
        factorial[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            factorial[i] = factorial[i+1] * (n-i);
        }
        char[] ans = new char[n];
        int idx = 0;
        while (++idx < n){
            int i = k / factorial[idx];
            k %= factorial[idx];
            int num = findNthNum(i+1);
            ans[idx-1] = (char)('0'+ num);
        }
        ans[idx-1] = (char)('0'+ findNthNum(1));
        return new String(ans);
    }

    int findNthNum(int nth){
        for (int i = 1; i < usedNums.length; i++) {
            if(!usedNums[i]){
                nth--;
                if (nth==0){
                    usedNums[i] = true;
                    return i;
                }
            }
        }
        return -1;
    }
}