05 August 2008
如果将每个数字单独旋转 180 度后，我们得到一个与 x 不同的有效数字，则整数 x 是一个很好的选择。每个数字都必须轮换——我们不能选择不理会它。
如果每个数字在旋转后仍然是一个数字，则该数字是有效的。例如：
0、1、8自转，
2 和 5 相互旋转（在这种情况下，它们以不同的方向旋转，换句话说，2 或 5 被镜像），
6 和 9 相互旋转，并且
其余数字不会轮换到任何其他数字并变为无效。
给定一个整数 n，返回 [1, n] 范围内的好整数个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
static int[] map = {0, 1, 5, -1, -1, 2, 9, -1, 8, 6};
public int rotatedDigits(int N) {
int result = 0;
for (int i = 2; i <= N; i++) {
if (isGoodNumber(i)) result++;
}
return result;
}
private boolean isGoodNumber(int n) {
int t = n, m = 0, base = 1;
while (t > 0) {
if (map[t % 10] == -1) return false;
m = m + map[t % 10] * base;
t /= 10;
base *= 10;
}
return n != m;
}
}
String
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int rotatedDigits(int N) {
int ans = 0;
outer: for(int i = 1; i <= N; i++) {
int d = 0;
for(char ch : Integer.toString(i).toCharArray()) {
if (ch == '3' || ch == '4' || ch == '7')
continue outer;
if (ch == '2' || ch == '5' || ch == '6' || ch == '9')
d = 1;
}
ans += d;
}
return ans;
}
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int rotatedDigits(int N) {
int[] dp = new int[N + 1];
int res = 0;
Set<Integer> s1 = Set.of(0, 1, 8), s2 = Set.of(2, 5, 6, 9);
for (int i = 0; i < Math.min(10, N + 1); i++) {
if (s1.contains(i)) dp[i] = 1;
else if (s2.contains(i)) {
dp[i] = 2;
res++;
}
}
for (int i = 10; i <= N; i++) {
int a = dp[i / 10], b = dp[i % 10];
if (a == 1 && b == 1) dp[i] = 1;
else if (a >= 1 && b >= 1) {
dp[i] = 2;
res++;
}
}
return res;
}
}
String
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
static Pattern pattern=Pattern.compile("[018]+");
private boolean isGood(int n){
String s=""+n;
if(s.indexOf('3')>=0||s.indexOf('4')>=0||s.indexOf('7')>=0)
return false;
Matcher matcher=pattern.matcher(s);
return !matcher.matches();
}//~
public int rotatedDigits(int N) {
return IntStream.rangeClosed(0,N).filter(i->isGood(i)).map(i->1).sum();
}
}