短距离里程表 “A”是什么样的符号 正常的里程表会依次显示自然数表示里程

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)