comments | difficulty | edit_url | tags | ||
---|---|---|---|---|---|
true |
中等 |
|
我们称一个数 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]
。
一种直观且有效的思路是,直接枚举
那么题目的重点转化为如何判断一个数字
我们先用一个长度为
然后遍历数字
时间复杂度
相似题目:
class Solution:
def rotatedDigits(self, n: int) -> int:
def check(x):
y, t = 0, x
k = 1
while t:
v = t % 10
if d[v] == -1:
return False
y = d[v] * k + y
k *= 10
t //= 10
return x != y
d = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6]
return sum(check(i) for i in range(1, n + 1))
class Solution {
private int[] d = new int[] {0, 1, 5, -1, -1, 2, 9, -1, 8, 6};
public int rotatedDigits(int n) {
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (check(i)) {
++ans;
}
}
return ans;
}
private boolean check(int x) {
int y = 0, t = x;
int k = 1;
while (t > 0) {
int v = t % 10;
if (d[v] == -1) {
return false;
}
y = d[v] * k + y;
k *= 10;
t /= 10;
}
return x != y;
}
}
class Solution {
public:
int rotatedDigits(int n) {
int d[10] = {0, 1, 5, -1, -1, 2, 9, -1, 8, 6};
auto check = [&](int x) -> bool {
int y = 0, t = x;
int k = 1;
while (t) {
int v = t % 10;
if (d[v] == -1) {
return false;
}
y = d[v] * k + y;
k *= 10;
t /= 10;
}
return x != y;
};
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans += check(i);
}
return ans;
}
};
func rotatedDigits(n int) int {
d := []int{0, 1, 5, -1, -1, 2, 9, -1, 8, 6}
check := func(x int) bool {
y, t := 0, x
k := 1
for ; t > 0; t /= 10 {
v := t % 10
if d[v] == -1 {
return false
}
y = d[v]*k + y
k *= 10
}
return x != y
}
ans := 0
for i := 1; i <= n; i++ {
if check(i) {
ans++
}
}
return ans
}
function rotatedDigits(n: number): number {
const d: number[] = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6];
const check = (x: number): boolean => {
let y = 0;
let t = x;
let k = 1;
while (t > 0) {
const v = t % 10;
if (d[v] === -1) {
return false;
}
y = d[v] * k + y;
k *= 10;
t = Math.floor(t / 10);
}
return x !== y;
};
return Array.from({ length: n }, (_, i) => i + 1).filter(check).length;
}
方法一的做法足以通过本题,但时间复杂度较高。如果题目的数据范围达到
这道题实际上是求在给定区间
对于区间
不过对于本题而言,我们只需要求出区间
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索,到最底层得到方案数,一层层向上返回答案并累加,最后从搜索起点得到最终的答案。
基本步骤如下:
我们将数字
函数的执行逻辑如下:
如果
否则,我们获取当前位的数字
接下来,我们遍历
时间复杂度
相似题目:
- 233. 数字 1 的个数
- 357. 统计各位数字都不同的数字个数
- 600. 不含连续 1 的非负整数
- 902. 最大为 N 的数字组合
- 1012. 至少有 1 位重复的数字
- 2376. 统计特殊整数
class Solution:
def rotatedDigits(self, n: int) -> int:
@cache
def dfs(i: int, ok: int, limit: bool) -> int:
if i >= len(s):
return ok
up = int(s[i]) if limit else 9
ans = 0
for j in range(up + 1):
if j in (0, 1, 8):
ans += dfs(i + 1, ok, limit and j == up)
elif j in (2, 5, 6, 9):
ans += dfs(i + 1, 1, limit and j == up)
return ans
s = str(n)
return dfs(0, 0, True)
class Solution {
private char[] s;
private Integer[][] f;
public int rotatedDigits(int n) {
s = String.valueOf(n).toCharArray();
f = new Integer[s.length][2];
return dfs(0, 0, true);
}
private int dfs(int i, int ok, boolean limit) {
if (i >= s.length) {
return ok;
}
if (!limit && f[i][ok] != null) {
return f[i][ok];
}
int up = limit ? s[i] - '0' : 9;
int ans = 0;
for (int j = 0; j <= up; ++j) {
if (j == 0 || j == 1 || j == 8) {
ans += dfs(i + 1, ok, limit && j == up);
} else if (j == 2 || j == 5 || j == 6 || j == 9) {
ans += dfs(i + 1, 1, limit && j == up);
}
}
if (!limit) {
f[i][ok] = ans;
}
return ans;
}
}
class Solution {
public:
int rotatedDigits(int n) {
string s = to_string(n);
int m = s.size();
int f[m][2];
memset(f, -1, sizeof(f));
auto dfs = [&](this auto&& dfs, int i, int ok, bool limit) -> int {
if (i >= m) {
return ok;
}
if (!limit && f[i][ok] != -1) {
return f[i][ok];
}
int up = limit ? s[i] - '0' : 9;
int ans = 0;
for (int j = 0; j <= up; ++j) {
if (j == 0 || j == 1 || j == 8) {
ans += dfs(i + 1, ok, limit && j == up);
} else if (j == 2 || j == 5 || j == 6 || j == 9) {
ans += dfs(i + 1, 1, limit && j == up);
}
}
if (!limit) {
f[i][ok] = ans;
}
return ans;
};
return dfs(0, 0, true);
}
};
func rotatedDigits(n int) int {
s := strconv.Itoa(n)
m := len(s)
f := make([][2]int, m)
for i := range f {
f[i] = [2]int{-1, -1}
}
var dfs func(i, ok int, limit bool) int
dfs = func(i, ok int, limit bool) int {
if i >= m {
return ok
}
if !limit && f[i][ok] != -1 {
return f[i][ok]
}
up := 9
if limit {
up = int(s[i] - '0')
}
ans := 0
for j := 0; j <= up; j++ {
if j == 0 || j == 1 || j == 8 {
ans += dfs(i+1, ok, limit && j == up)
} else if j == 2 || j == 5 || j == 6 || j == 9 {
ans += dfs(i+1, 1, limit && j == up)
}
}
if !limit {
f[i][ok] = ans
}
return ans
}
return dfs(0, 0, true)
}
function rotatedDigits(n: number): number {
const s = n.toString();
const m = s.length;
const f: number[][] = Array.from({ length: m }, () => Array(2).fill(-1));
const dfs = (i: number, ok: number, limit: boolean): number => {
if (i >= m) {
return ok;
}
if (!limit && f[i][ok] !== -1) {
return f[i][ok];
}
const up = limit ? +s[i] : 9;
let ans = 0;
for (let j = 0; j <= up; ++j) {
if ([0, 1, 8].includes(j)) {
ans += dfs(i + 1, ok, limit && j === up);
} else if ([2, 5, 6, 9].includes(j)) {
ans += dfs(i + 1, 1, limit && j === up);
}
}
if (!limit) {
f[i][ok] = ans;
}
return ans;
};
return dfs(0, 0, true);
}