算法@LeetCode:CountNumbersWithUniq

Log

• 【170427】完成 01 版（Python）提交
• 【170501】研究参考答案，并补充笔记

题目

Count Numbers with Unique Digits

【题目类型备注】

动态规划, 回溯法, 数学

提交

01

【语言】

Python

【时间】

170427

【思路】

搞清楚思路以后这就是一个简单的排列组合题……然而我还走了各种弯路，不忍直视……

不要反扣那些不符合要求的数字，否则思考量/计算量很大；也不用根据非首位是否含有 0 来分情况计算，这也复杂化了问题。

本题的思路如下：（当 n 为 0 或 1 时很容易手算，不考虑；当 n >= 2 时，）

1. 当数字为 2 位数、3 位数、……、n 位数时，在每种情况下（k 位数）分别计算：P(9, k-1)。于是，所有满足条件（没有重复数字）的 k 位数总共就有 9 * P(9, k-1) 个

• 这里，定义 P(n, r) 为：从 n 个元素中取出 r 个进行排列的所有不同排列数
• 解释 9 * P(9, k-1)：
  • 首位非 0，因此是首位可用数字是 9 选 1；
  • 剩下的 k-1 位所选数字，则是从剩下的 9 个数字（0~9， 除去首位已用的）中选出 k-1 个进行排列；由于是排列，所以一定不会重复，也考虑了使用同样数字但顺序不同导致结果不同的情况

2. 求和：9 * P(9, 2) + ... + 9 * P(9, n) ，即为答案

还没看参考答案，但我认为这应该不会和参考答案相差到哪里去，毕竟思路和代码都很难再精简了。这里的状态方程应该就是排列的计算方法，以及最终答案的计算方法（求和）

感觉有一点别扭，但似乎也像是状态方程……

【代码】

class Solution(object):
    def countNumbersWithUniqueDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        P9 = [1, 9]
        ct = 10
        if n == 0:
          return 1
        if n == 1:
          return 10
        for i in range(2, n+1):
          ct += 9 * P9[i-1]
          P9.append(P9[i-1] * (9 - (i-1)))
        # Return the result
        return ct

【结果】

运行时：38 ms

报告链接：https://leetcode.com/submissions/detail/101337148/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 83.50 % of python submissions.

00

参考解法：

（有 2 个解法我没看，一个是所谓的回溯法，代码长不说，居然还用了递归……不同的方法要么复杂度更优、要么代码更短，两者都做不到，那么我是不看的；另一个不看的则是一个使用了依赖于编译的写法，即把自增运算符放到了 while 的判断句中，这也是非常糟糕的代码，没有兴趣看）

这次贴出来的代码和我的思路是一样的，也就是说我的实现也算是最优解了

• Python
• Java
• C++

自己实现一遍最优解：

• Python
• 。。。