1012. Numbers With Repeated Digits

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Example 1:

Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2:

Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Example 3:

Input: 1000
Output: 262

Note:

  1. 1 <= N <= 10^9

这道题给了一个正整数N,让返回所有不大于N且至少有一个重复数字的正整数的个数,题目中给的例子也可以很好的帮助我们理解。要求的是正整数的位数上至少要有一个重复数字,当然最简单暴力的方法就是从1遍历到N,然后对于每个数字判断是否有重复数字,看了一眼题目难度 Hard,想都不用想,肯定是超时的。这道题需要更高效的解法,首先来想,若是直接求至少有一个重复数字的正整数,由于并不知道有多少个重复数字,可能1个,2个,甚至全是重复数字,这样很难找到规律。有时候直接求一个问题不好求,可以考虑求其相反的情况,至少有一个重复数字反过来就是一个重复数字都没有,所以这里可以求不大于N且一个重复数字都没有的正整数的个数,然后用N减去这个数字即为所求。好,接下来看怎么求,对于任意一个N,比如 7918,是个四位数,而所有的三位数,两位数,一位数,都一定比其小,所以可以直接求出没有重复数字的三位数,两位数,和一位数。比如三位数,由于百位上不能有0,则只有9种情况,十位上可以有0,则有9种情况,个位上则有8种情况,所以就是 9*9*8。可以归纳出没有重复数字的n位数的个数,最高位去除0还有9种,剩余的 n-1 位则依次是 9,8,7… 则后面的 n-1 位其实是个全排列,从9个数中取出 n-1 个数字的全排列,初中就学过的。这里写一个全排列的子函数,求从m个数字中取n个数字的全排列,方便后面计算。算完这些后,还要来算符合题意的四位数,由于第一位是7,若千位上是小于7的数字(共有6种,千位上不能是0),则后面的百位,十位,个位又都可以全排列了,从9个数字中取3个数字的全排列,再乘以千位上小于7的6种情况。若当千位固定为7,则百位上可以放小于9的数字(共有8种,百位不能放7,但可以放0),则后面的十位和个位都可以全排列了,从8个数字种取出2个数字的全排列,再乘以百位上小于9的8种情况。需要注意的是,遍历给定数字的各个位时,有可能出现重复数字,一旦出现了之后,则该 prefix 就不能再用了,因为已经不合题意了。所以要用一个 HashSet 来记录访问过的数字,一旦遇到重复数字后就直接 break 掉。最后还有一个小 trick 需要注意,由于N本身也需要计算进去,所以再计算的时候,使用 N+1 进行计算的话,就可以把N这种情况算进去了,参见代码如下:

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        vector<int> digits;
        unordered_set<int> visited;
        for (int x = N + 1; x > 0; x /= 10) {
            digits.insert(digits.begin(), x % 10);
        }
        int res = 0, len = digits.size();
        for (int i = 1; i < len; ++i) {
            res += 9 * A(9, i - 1);
        }
        for (int i = 0; i < len; ++i) {
            for (int j = i > 0 ? 0 : 1; j < digits[i]; ++j) {
                if (visited.count(j)) continue;
                res += A(9 - i, len - i - 1);
            }
            if (visited.count(digits[i])) break;
            visited.insert(digits[i]);
        }
        return N - res;
    }
    int A(int m, int n) {
        return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1012

类似题目:

Numbers At Most N Given Digit Set

Rotated Digits

参考资料:

https://leetcode.com/problems/numbers-with-repeated-digits/

https://leetcode.com/problems/numbers-with-repeated-digits/discuss/256725/JavaPython-Count-the-Number-Without-Repeated-Digit

https://leetcode.com/problems/numbers-with-repeated-digits/discuss/258212/Share-my-O(logN)-C%2B%2B-DP-solution-with-proof-and-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation