LC: 1088. Confusing Number II
https://leetcode.com/problems/confusing-number-ii/
1088. Confusing Number II
A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.
We can rotate digits of a number by 180 degrees to form new digits.
When
0,1,6,8, and9are rotated180degrees, they become0,1,9,8, and6respectively.When
2,3,4,5, and7are rotated180degrees, they become invalid.
Note that after rotating a number, we can ignore leading zeros.
For example, after rotating
8000, we have0008which is considered as just8.
Given an integer n, return the number of confusing numbers in the inclusive range [1, n].
Example 1:
Input: n = 20
Output: 6
Explanation: The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.Example 2:
Constraints:
1 <= n <= 109
The Essence:
Alle Zahlen, die nach einer Drehung um 180 Grad gleich bleiben, sind keine confusing Zahl, sondern eine strobogrammatische Zahl. Man kann also die Anzahl solcher Zahlen finden und von n subtrahieren.
Details:
Man kann die Anzahl der strobogrammatischen Zahlen durch Backtracking-Technik finden. Die Im Alle Zahlen, die nach einer Drehung um 180 Grad gleich bleiben, sind keine confusing Zahl, sondern eine strobogrammatische Zahl. Man kann also die Anzahl solcher Zahlen finden und von n subtrahieren.Alle Zahlen, die nach einer Drehung um 180 Grad gleich bleiben, sind keine confusing Zahl, sondern eine strobogrammatische Zahl. Man kann also die Anzahl solcher Zahlen finden und von n subtrahieren.dfeef plementierung ist hier: https://github.com/spiralgo/algorithms/pull/323
Default Code:
Last updated