原题链接在这里：https://leetcode.com/problems/confusing-number-ii/
题目：
We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.
A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.(Note that the rotated number can be greater than the original number.)
Given a positive integer N, return the number of confusing numbers between 1 and N inclusive.
Example 1:
Input: 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:
Input: 100
Output: 19
Explanation:
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].
Note:
1 <= N <= 10^9
题解：
Create num and its rotation on the run with 0, 1, 6, 8, 9. If the number != rotation, count++.
num = num * 10 + d.
rotation = hm.get(d) *base + ratation.
base *= 10.
Time Complexity: exponential.
Space: O(N). stack space.
AC Java:
1 class Solution { 2 int limit; 3 int [] nums = new int[]{0, 1, 6, 8, 9}; 4 int count = 0; 5 6 public int confusingNumberII(int N) { 7 limit = N; 8 9 HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); 10 hm.put(0, 0); 11 hm.put(1, 1); 12 hm.put(6, 9); 13 hm.put(8, 8); 14 hm.put(9, 6); 15 16 dfs(0, 0, 1, hm); 17 return count; 18 } 19 20 private void dfs(long num, long reNum, long base, HashMap<Integer, Integer> hm){ 21 if(num > limit){ 22 return; 23 } 24 25 if(num != reNum){ 26 count++; 27 } 28 29 for(int d : nums){ 30 if(num == 0 && d == 0){ 31 continue; 32 } 33 34 dfs(num * 10 + d, hm.get(d) * base + reNum, base * 10, hm); 35 } 36 } 37 }