【2022-09-25每日一题】788. 旋转数字[Medium]
2022-09-25
4分钟阅读时长
2022-09-25每日一题：788. 旋转数字
难度：Medium
标签：数学 、 动态规划
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
示例：
输入: 10 输出: 4 解释: 在[1, 10]中有四个好数： 2, 5, 6, 9。 注意 1 和 10 不是好数, 因为他们在旋转之后不变。
提示：
- N 的取值范围是
[1, 10000]。
方法一：枚举
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
官方check数组法
// 写法一：
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
var check = []int{0, 0, 1,-1,-1, 1, 1,-1, 0, 1} // 反转后0代码原样, 1有对应数字，-1 无效
func rotatedDigits(n int) (ans int) {
for i := 1; i <= n; i++ {
s := strconv.Itoa(i)
vliad, diff := true, false // vliad 默认有效, diff 翻转后得到不同的数字
for _, c := range s {
if check[c-'0'] == -1 {
vliad = false
break
} else if check[c-'0'] == 1 {
diff = true
}
}
if vliad && diff {
ans++
}
}
return ans
}
// 写法二：
// 不把数字转字符串，直接数学运算
func rotatedDigits(n int) (ans int) {
for i := 1; i <= n; i++ {
vliad, diff := true, false // vliad 默认有效, diff 翻转后得到不同的数字
for num := i; num > 0; num = num/10 {
mod := num%10
if check[mod] == -1 {
vliad = false
break
} else if check[mod] == 1 {
diff = true
}
}
if vliad && diff {
ans++
}
}
return ans
}
复杂度分析
- 写法一：时间复杂度：O(nlogn) 空间复杂度：O(logn)
- 写法二：时间复杂度：O(nlogn) 空间复杂度：O(1)
不使用check数组
func rotatedDigits(n int) (ans int) {
for i := 1; i <= n; i++ {
ok := false
for num := i; num > 0; num = num/10 {
mod := num%10
if mod == 2 || mod == 5 || mod == 6 || mod == 9 {
ok = true
} else if mod != 0 && mod != 1 && mod != 8 {
ok = false
break
}
}
if ok {
ans++
}
}
return ans
}
复杂度分析
时间复杂度：共有 n 个数需要枚举，检查一个数需要遍历其每个数字，复杂度为 O(logn)。整体复杂度为O(nlogn)
空间复杂度：O(1)
方法二：数位动态规划
官方题解
var check = [10]int{0, 0, 1, -1, -1, 1, 1, -1, 0, 1}
func rotatedDigits(n int) int {
digits := strconv.Itoa(n)
memo := [5][2][2]int{}
for i := 0; i < 5; i++ {
memo[i] = [2][2]int{{-1, -1}, {-1, -1}}
}
var dfs func(int, bool, bool) int
dfs = func(pos int, bound, diff bool) (res int) {
if pos == len(digits) {
return bool2int(diff)
}
ptr := &memo[pos][bool2int(bound)][bool2int(diff)]
if *ptr != -1 {
return *ptr
}
lim := 9
if bound {
lim = int(digits[pos] - '0')
}
for i := 0; i <= lim; i++ {
if check[i] != -1 {
res += dfs(pos+1, bound && i == int(digits[pos]-'0'), diff || check[i] == 1)
}
}
*ptr = res
return
}
return dfs(0, true, false)
}
func bool2int(b bool) int {
if b {
return 1
}
return 0
}
灵茶山艾府题解
var diffs = [10]int{0, 0, 1, -1, -1, 1, 1, -1, 0, 1}
func rotatedDigits(n int) int {
s := strconv.Itoa(n)
m := len(s)
dp := make([][2]int, m)
for i := range dp {
dp[i] = [2]int{-1, -1}
}
var f func(int, int, bool) int
f = func(i, isDiff int, isLimit bool) (res int) {
if i == m {
return isDiff // 只有包含 2/5/6/9 才算一个好数
}
if !isLimit {
dv := &dp[i][isDiff]
if *dv >= 0 {
return *dv
}
defer func() { *dv = res }()
}
up := 9
if isLimit {
up = int(s[i] - '0')
}
for d := 0; d <= up; d++ { // 枚举要填入的数字 d
if diffs[d] != -1 { // d 不是 3/4/7
res += f(i+1, isDiff|diffs[d], isLimit && d == up)
}
}
return
}
return f(0, 0, true)
}
ylb 题解
func rotatedDigits(n int) int {
a := make([]int, 6)
dp := make([][2]int, 6)
for i := range a {
dp[i] = [2]int{-1, -1}
}
l := 0
for n > 0 {
l++
a[l] = n % 10
n /= 10
}
var dfs func(int, int, bool) int
dfs = func(pos, ok int, limit bool) int {
if pos <= 0 {
return ok
}
if !limit && dp[pos][ok] != -1 {
return dp[pos][ok]
}
up := 9
if limit {
up = a[pos]
}
ans := 0
for i := 0; i <= up; i++ {
if i == 0 || i == 1 || i == 8 {
ans += dfs(pos-1, ok, limit && i == up)
}
if i == 2 || i == 5 || i == 6 || i == 9 {
ans += dfs(pos-1, 1, limit && i == up)
}
}
if !limit {
dp[pos][ok] = ans
}
return ans
}
return dfs(l, 0, true)
}
复杂度分析
- 时间复杂度：O(logn)。
- 空间复杂度：O(logn)。