LWC 73: 788. Rotated Digits
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434548
LWC 73: 788. Rotated Digits
Problem:
X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number. Now given a positive number N, how many numbers X from 1 to N are good?
Example:
Input: 10 Output: 4 Explanation:undefined There are four good numbers in the range 1, 10 : 2, 5, 6, 9. Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.
Note:
N will be in range 1, 10000.
思路：
观察N最大不超过10000，可以暴力解决。遍历1到N，核实每个num，如果num符合Rotated Digits则计数。
Java版本:
public int rotatedDigits(int N) {
int cnt = 0;
for (int i = 1; i <= N; ++i) {
int rotate = valid(i);
if (rotate != -1 && rotate != i) cnt += 1;
}
return cnt;
}
public int valid(int n) {
int[] map = {0, 1, 5, -1, -1, 2, 9, -1, 8, 6};
int num = 0; int p = 1;
for(;n != 0; n /= 10) {
int digit = map[n % 10];
if (digit == -1) return -1;
num = num + p * digit;
p *= 10;
}
return num;
}Python版本：
class Solution(object):
def rotatedDigits(self, N):
s1 = set([1, 8, 0])
s2 = set([1, 2, 5, 8, 6, 9, 0])
def isGood(n):
s = set([int(i) for i in str(n)])
return s.issubset(s2) and not s.issubset(s1)
return sum(isGood(i) for i in range(N + 1))腾讯云开发者
