第357题---Count Numbers with Unique Digits

• 题意描述
  • 给定一个整数n，求1-10的n次方之间的位上不重复的唯一数
    
    
• 思路一：动态规划+数学
  • f(1) = 10, f(2)=99, f(3)=99*8
  • 1-0,1, 2, 3,4, …., 9
  • 2- 1对应9个数，…9对应9个数

• 代码

  class Solution {
  public:
      int countNumbersWithUniqueDigits(int n) {
          if(n == 0)
              return 1;
              
          int res = 10;
          int unique = 9;
          int available = 9;
          
          while(n -- > 1 && available > 0) {
              unique = unique * available;
              res += unique;
              available--;
          }
          return res;
      }
  };

• 思路二：回溯法

  • 记录三个状态，对应数字的标记，当前数，以及前一个数

    class Solution {
    public:
        int countNumbersWithUniqueDigits(int n) {
            if (n > 10)
                countNumbersWithUniqueDigits(10);
                
            int count = 1;
            long max = pow(10, n);
            
            vector<bool> vec(10, false);
            
            for(int i = 1; i < 10; i ++) {
                vec[i] = true;
                count += search(i, max, vec);
                vec[i] = false;
            }
            return count;
        }
        
        int search(long prev, long max, vector<bool> vec) {
            int count = 0;
            if(prev < max) {
                count += 1;
            } else {
                return count;
            }
            
            for(int i = 1; i < 10; i++) {
                if(!vec[i]) {
                    vec[i] = true;
                    long cur = 10 * prev + i;
                    count += search(cur, max, vec);
                    vec[i] = false;
                }
            }
            return count;
        }
    };