题目大意：
给一个字符串，独立旋转每个数字180°，判断得到的新字符串是否合法。
- 出现数字3,4,7一定不合法
- 新字符串 == 原来字符串不合法
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?
|
1 2 3 4 5 6 |
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:
- N will be in range
[1, 10000].
Solution 1: Brute Force
Time complexity: O(nlogn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua // Running time: 21 ms class Solution { public: int isValid(int n) { string s = to_string(n); string t(s); for (int i = 0; i < s.length(); ++i) { if (s[i] == '3' || s[i] == '4' || s[i] == '7') return 0; else if (s[i] == '2') t[i] = '5'; else if (s[i] == '5') t[i] = '2'; else if (s[i] == '6') t[i] = '9'; else if (s[i] == '9') t[i] = '6'; } return t != s; } int rotatedDigits(int N) { int ans = 0; for (int i = 1; i <= N; ++i) ans += isValid(i); return ans; } }; |
Bit Operation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Running time: 4 ms class Solution { public: int isValid(int n) { constexpr int kInValidMask = (1 << 3) | (1 << 4) | (1 << 7); constexpr int kValidMask = (1 << 2) | (1 << 5) | (1 << 6) | (1 << 9); int valid = 0; while (n > 0) { int r = 1 << (n % 10); if (r & kInValidMask) return 0; else if (r & kValidMask) valid = 1; n /= 10; } return valid; } int rotatedDigits(int N) { int ans = 0; for (int i = 1; i <= N; ++i) ans += isValid(i); return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment