c*****u
发帖数: 867 | 1 就是第357题 Count Numbers with Unique Digits。题目给了提示，通项公式是：
f(k) = 9 * 9 * 8 * ... (9 - k + 2)。具体就是
f(1) = 10
f(2) = 9 * 9
f(3) = f(2) * 8
f(4) = f(3) * 7
...
但是我觉得这种算法里f(3)没有包含201这个数。原因是：求f(3)时，先看只有两位时
的值（也就是f(2)），然后在放上第3位，于是结果是f(2) * 8。但是这么算时，f(2)
里面不包含01这个数，所以求出来的f(3)不包含201、301。。。901这些数。
我知道我想错了， 暴力破解报所有数打印出来结果和leetcode一致。
请问我哪里想错了呢？ |
h****e
发帖数: 11 | 2 f(2)是指头两位,第一位是1-9有9种,第二位是0-9去除和第一位相同的,也有9种。f(3)
在这个基础上, 0-9去除和前两位相同的,只有8种。 |
l****u
发帖数: 1764 | 3 f(3) 在f（2）的基础上加一位，加到最后面就行啊，所以01不在f(2)，当然01X也不在
f(3)中；同理，f(3)中可以包含201，301因为f(2)中包含20， 30
【在 c*****u 的大作中提到】
: 就是第357题 Count Numbers with Unique Digits。题目给了提示，通项公式是：
: f(k) = 9 * 9 * 8 * ... (9 - k + 2)。具体就是
: f(1) = 10
: f(2) = 9 * 9
: f(3) = f(2) * 8
: f(4) = f(3) * 7
: ...
: 但是我觉得这种算法里f(3)没有包含201这个数。原因是：求f(3)时，先看只有两位时
: 的值（也就是f(2)），然后在放上第3位，于是结果是f(2) * 8。但是这么算时，f(2)
: 里面不包含01这个数，所以求出来的f(3)不包含201、301。。。901这些数。
|
c*****u
发帖数: 867 | 4 我的想法是f(3) 在f（2）的基础上加一位，加到最前面，而不是最后面。请问我这么
想为什么错了呢？
【在 l****u 的大作中提到】
: f(3) 在f（2）的基础上加一位，加到最后面就行啊，所以01不在f(2)，当然01X也不在
: f(3)中；同理，f(3)中可以包含201，301因为f(2)中包含20， 30
|
c*****u
发帖数: 867 | 5 想明白了，f(3) 在f（2）的基础上加一位如果加到最高位的话不能乘以8。确实应该是
往后加。
谢谢楼上的两位。
【在 c*****u 的大作中提到】
: 我的想法是f(3) 在f（2）的基础上加一位，加到最前面，而不是最后面。请问我这么
: 想为什么错了呢？
|
s**********1
发帖数: 12 | |
