788. Rotated Digits*
https://leetcode.com/problems/rotated-digits/
题目描述
X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.
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 and become invalid.
Now given a positive number N, how many numbers X from 1 to N are good?
Example:
Input: 10
Output: 4
Explanation:
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:
-
Nwill be in range[1, 10000].
解题思路
给定数字 N, 判断 1 ~ N 中有多少数字是 good 的. 一个数字是 good 的定义是: 将它翻转 180 度后是一个不等于自身的有效的数字. 比如 0 ~ 9 中, 只有 2, 5, 6, 9 等四个数字符合定义, 属于 good.
而一个数字有效的定义是, 将其翻转 180 度后仍然是一个数字, 那么就有 0, 1, 8, 2, 5, 6, 9 等七个数字满足含义. 那么当 N 为 [1, 10000] 范围内的数字时, 1 ~ N 中有多少个数字是 good 的? 比如当 N 等于 10 时, 只有 2, 5, 6, 9 四个数字是 good 的, 而 1, 8, 10 由于它们翻转 180 度后等于自身, 因此不是 good 的.
思路: 理解题意后, 要确认哪些数字是 good 的:
- 如果有某个 digit 是 3, 4, 7, 那么翻转之后都不是一个 valid 的数字, 所以不是 good 的.
- 如果某数字全部由 0, 1, 8 组成, 那么也不是 good 的(因为翻转后等于自身)
- 剩下的数字都是 good 的, 也就是说, 这些数字由除 3, 4, 7 以外的数字组成, 并且至少存在 2, 5, 6, 9 中的一个数字.
C++ 实现 1
class Solution {
private:
bool isGood(int N) {
bool isValid = false;
while (N) {
int n = N % 10;
if (n == 3 || n == 4 || n == 7)
return false;
// 使用 isValid 来记录是否存在 2, 5, 6, 9 中的某个数字.
if (n == 2 || n == 5 || n == 6 || n == 9)
isValid = true;
N = N / 10;
}
return (isValid == true);
}
public:
int rotatedDigits(int N) {
int count = 0;
for (int i = 1; i <= N; ++i)
if (isGood(i))
count ++;
return count;
}
};
C++ 实现 2
这个实现比较慢. 另外可以考虑将 isValid 实现为 NotValid: 因为无效数字只有三个数字 3, 4, 7, 数量相比 valid number 更少.
class Solution {
private:
bool isValid(int N) {
unordered_set<int> record{0, 1, 2, 5, 6, 8, 9};
if (record.count(N)) return true;
return false;
}
bool isGood(int N) {
unordered_set<int> digits;
while (N > 0) {
int n = N % 10;
if (!isValid(n)) return false;
digits.insert(n);
N /= 10;
}
for (auto &i : {0, 1, 8})
if (digits.count(i)) digits.erase(i);
// 如果 digits 中还包含其他数字, 那就说明 N 为 good number
return !digits.empty();
}
public:
int rotatedDigits(int N) {
int count = 0;
for (int i = 1; i <= N; ++ i)
if (isGood(i)) count += 1;
return count;
}
};