算法@LeetCode:CountNumbersWithUniq
2017-04-27 本文已影响21人
苏尚君
Log
- 【170427】完成 01 版（Python）提交
- 【170501】研究参考答案，并补充笔记
题目
Count Numbers with Unique Digits
【题目类型备注】
动态规划, 回溯法, 数学
提交
01
【语言】
Python
【时间】
170427
【思路】
搞清楚思路以后这就是一个简单的排列组合题……然而我还走了各种弯路，不忍直视……
不要反扣那些不符合要求的数字，否则思考量/计算量很大；也不用根据非首位是否含有 0 来分情况计算，这也复杂化了问题。
本题的思路如下：（当 n 为 0 或 1 时很容易手算，不考虑；当 n >= 2 时，）
- 当数字为 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个进行排列；由于是排列，所以一定不会重复，也考虑了使用同样数字但顺序不同导致结果不同的情况
- 求和：
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
- 。。。
