902. 最大为 N 的数字组合

小鱼儿 2024-04-03 14:19 101阅读 0赞

问题描述：

> 给定一个按 非递减顺序 排列的数字数组 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

思路：多看几遍问题，其实就是**用升序数组中的1个或多个数字，能拼成多少比n更小的数。**

可以用数学的思路来解决本问题：  
比如 digits = \[“1”,“3”,“7”,“9”\], n = 800

1. 比n小的数字，n是三位数，则二位数和一位数怎么拼凑都是肯定小于n的，二位数的拼凑可能有 4x2 = 8， 一位数是 4x1 = 4，共12个
    2. 只需要考虑三位数，n的第一位是8， 则只有 1 3 7为首位的三位数小于n，9开头的首位必大于n，所以三位数有 3x4x4=48 
    (首位从数组中可以取三个数 1 3 7，第二位可以取四个数，个位也可以取四个数)
    4. 所以总共是 12+48 = 60

上述推理后大致就明白了思路，那如果数组中有数字和首位相同呢？  
比如 digits = \[“1”,“3”,“8”,“9”\], n = 800

1. 和上面相同，二位数和一位数都是12个
    2. 三位数中，当首位为1 3时，比较第一位“8”，后面两位任取肯定小于n，3. 所以有2x4x4=32个
    4. 当首位为8时，开始比较第二位 “0”，发现第二位全部大于0，这种情况肯定无需比较第三位了，所以8为首位且小于n的数字并没有。
    5. 同理，如果第二位全部小于n的第二位，则任选即可，这种情况也无需比较第三位，因为第三位选择哪个数都小于。
    6. 所以重点还是数组中有和第二位相同元素时，需要特殊考虑，去比较下一位。后面仍然如此类推。

综上，我决定用删减去处理三位数的选择，就是先默认数组中所有元素皆可选择，4x4x4=64.  
然后再开始遍历数组与n的各位数字进行比较，若大于，则直接减去 4x4x1=16，如果遍历到了相同元素，就中断遍历，开始比较第二位，同样操作，一直把所有大于n的可能数字剔除掉。

public int atMostNGivenDigitSet(String[] digits, int n) {
        
    
            int count = 0;
    
            char[] nc = String.valueOf(n).toCharArray();
    
            // 小于n的位数数字任取
            for (int i = 1; i < nc.length; i++) {
        
                count += Math.pow(digits.length,i);
            }
    
    
            /**
             * 集中处理n位的数字
             * 从n位后面一位开始，逐个进行比较
             * i 数字n的第几位数字
             * j 每次都从数组最大的数开始和n的对应位数比较
             */
    
            // 先默认所有的都可以，再开始删减
            count += Math.pow(digits.length,nc.length);
            boolean flag = true;
            outA: for (int i = 0; i < nc.length; i++) {
        
                outB: for (int j = digits.length-1; j >= 0; j--) {
        
                    // 每次比较时都默认true，如果某次遍历全部都比数组元素大，则结束
                    flag = true;
    
                    // 数字的每一位数data
                    int data = (int) nc[i] - (int)'0';
                    // 如果小于，直接把后面的count加上去
                    if(Integer.parseInt(digits[j]) < data){
        
                        // 如果小于，直接结束
                        break outA;
                    }else if(Integer.parseInt(digits[j]) == data){
        
                        // 如果是等于，则继续比较后面的数字，开始下一位数的比较
                        flag = false;
                        break outB;
    
                    }else{
        
                        // 如果大于，直接开始删减
                        count -= (Math.pow(digits.length,nc.length-i-1));
                    }
                }
    
                // 如果所有的数字都大于当前数组数字，那就不用再比较了
                if(flag){
        
                    break;
                }
            }
    
            return count;
    
        }

![在这里插入图片描述][d362a096cecc4e749851a701c7356837.png]

[d362a096cecc4e749851a701c7356837.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/05bbb49821874780b5542ea31c7c6cd5.png