2021-08-27：正常的里程表会依次显示自然数表示里程，吉祥的里程表会忽略含有4的数字而跳到下一个完全不含有4的数。正常：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X。吉祥：1 2 3 5 6 7 8 9 10 11 12 13 15 16 17 ... 38 39 50 51 52 53 55。给定一个吉祥里程表的数字num(当然这个数字中不含有4)。返回这个数字代表的真实里程。
福大大 答案2021-08-27：
这道题的本质是一个9进制的数转成10进制的数。
0-3不变。5-9变成4-8。
比如39，先变成38，然后3*9 8=35。35就是需要的返回的值。
时间复杂度：O(lgN)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
ret := notContains4Nums1(39)
fmt.Println(ret)
ret = notContains4Nums2(39)
fmt.Println(ret)
ret = notContains4Nums3(39)
fmt.Println(ret)
}
// num中一定没有4这个数字
func notContains4Nums1(num int) int {
count := 0
for i := 1; i <= num; i {
if isNot4(i) {
count
}
}
return count
}
func isNot4(num int) bool {
for num != 0 {
if num == 4 {
return false
}
num /= 10
}
return true
}
// arr[1] : 比1位数还少1位，有几个数(数字里可以包含0但是不可以包含4)？0个
// arr[2] : 比2位数还少1位，有几个数(数字里可以包含0但是不可以包含4)？9个
// 1 -> 0 1 2 3 - 5 6 7 8 9 = 9
// arr[3] :比3位数还少1位，有几个数(数字里可以包含0但是不可以包含4)？81个
// 1 : 0 (0 1 2 3 - 5 6 7 8 9) = 9
// 2 :
// 1 (0 1 2 3 - 5 6 7 8 9) = 9
// 2 (0 1 2 3 - 5 6 7 8 9) = 9
// 3 (0 1 2 3 - 5 6 7 8 9) = 9
// 5 (0 1 2 3 - 5 6 7 8 9) = 9
// ...
// 9 (0 1 2 3 - 5 6 7 8 9) = 9
var arr []int = []int{0, 1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489,
3486784401, 31381059609, 282429536481, 2541865828329, 22876792454961, 205891132094649,
1853020188851841, 16677181699666569, 150094635296999121, 1350851717672992089}
// num中一定没有4这个数字
func notContains4Nums2(num int) int {
if num <= 0 {
return 0
}
// num的十进制位数，len
len2 := decimalLength(num)
// 35621
// 10000
offset := offset(len2)
// 第一位数字
first := num / offset
return arr[len2] - 1 (first-twoSelectOne(first < 4, 1, 2))*arr[len2] process(num%offset, offset/10, len2-1)
}
// num之前，有开头！
// 在算0的情况下，num是第几个数字
// num 76217
// 10000
// 6217
// 1000
// len
func process(num int, offset int, len2 int) int {
if len2 == 0 {
return 1
}
first := num / offset
return twoSelectOne(first < 4, first, (first-1))*arr[len2] process(num%offset, offset/10, len2-1)
}
// num的十进制位数
// num = 7653210
// 7
func decimalLength(num int) int {
len2 := 0
for num != 0 {
len2
num /= 10
}
return len2
}
// len = 6
// 100000
// len = 4
// 1000
// 3452168
// 1000000
// 3
func offset(len2 int) int {
offset := 1
for i := 1; i < len2; i {
offset *= 10
}
return offset
}
// 讲完之后想到了课上同学的留言
// 突然意识到，这道题的本质是一个9进制的数转成10进制的数
// 不过好在课上的解法有实际意义，就是这种求解的方式，很多题目都这么弄
// 还有课上的时间复杂度和"9进制的数转成10进制的数"的做法，时间复杂度都是O(lg N)
// 不过"9进制的数转成10进制的数"毫无疑问是最优解
func notContains4Nums3(num int) int {
if num <= 0 {
return 0
}
ans := 0
for base, cur := 1, 0; num != 0; num, base = num/10, base*9 {
cur = num % 10
ans = twoSelectOne(cur < 4, cur, cur-1) * base
}
return ans
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class24/Code03_NotContains4.java)
,
