https://leetcode.com/problems/rotated-digits/description/
X. O(logn)
http://www.frankmadrid.com/ALudicFallacy/2018/02/28/rotated-digits-leet-code-788/
The critical intuition is: we want numbers that contain only
https://leetcode.com/problems/rotated-digits/discuss/116530/O(logN)-Solution
X. Digit DP
http://www.cnblogs.com/grandyang/p/9154892.html
其实这道题还有更好的解法呢，使用动态规划Dynamic Programming来做的，思路非常巧妙，博主深为叹服。定义了一个长度为N+1的一维布尔型DP数组，其中dp[i]表示数字i的三种状态，0表示数字i翻转后不合法，1表示数字i翻转后和原数相同，2表示数字i翻转后形成一个不同的数字。那么根据题目中的定义可知，只有当dp[i]=2的时候才是好数字。那么下面来看状态转移方程吧，我们知道如果数字只有1位的话，那么判断起来很简单，如果是0，1，和8中的一个，那么dp[i]=1，如果是2，5，6，和9中的一个，那么dp[i]=2，并且结果res自增1。如果是剩下的三个数字3，4，7中的一个不用更新，因为dp数组初始化就为0。下面来看数字i大于10的情况，非常的经典，dp[i] 的值其实可以从 dp[i/10] 和 dp[i%10] 这两个状态值转移而来，由于我们更新的顺序是从小到大，所以当要更新dp[i]的时候，dp[i/10] 和 dp[i%10] 这两个状态值已经算过了。为啥dp[i] 的值是由这两个状态值决定的呢？因为每个数字都是相互独立的翻转，比如四位数字abcd，可以拆分为三位数abc，和个位数d，如果abc翻转后仍是abc，d翻转后仍是d，说明abcd翻转后仍是abcd，所以dp[i]=1，只要其中有一个大于1了，另外一个至少是1的话，那么说明可以翻转成不同的数字，dp[i]=2，并且结果res自增1
https://leetcode.com/problems/rotated-digits/discuss/117975/Java-dp-solution-9ms
https://leetcode.com/problems/rotated-digits/discuss/116547/Easily-Understood-Java-Solution
Improved efficiency. Increments i if the leading digit of i is 3, 4 or 7.
For example, if i = 300, then we know 300, 301, 302 ... 399 are all invalid. IncrementIfNeeded(int i) returns 99 to set i to 399 and 400 after i++ from loop increment.
The same thing happens for 400.
Therefore, we only check 300 and 400, rather than 300, 301, 302, ..., 399, 400, 401, 402, ..., 499.
def rotatedDigits(self, N):
"""
:type N: int
:rtype: int
"""
dmap = {"0" : "0", "1" : "1", "8" : "8", "2" : "5", "5" : "2", "6" : "9", "9" : "6"}
res = 0
for num in range(1, N + 1):
if any(x in str(num) for x in ["3", "4", "7"]):
continue
if any(x in str(num) for x in ["2", "5", "6", "9"]):
res += 1
return res
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:
- N will be in range
[1, 10000].
http://www.frankmadrid.com/ALudicFallacy/2018/02/28/rotated-digits-leet-code-788/
The critical intuition is: we want numbers that contain only
0182569, but also at least one 2569. If you still remember how we handled this at least one situation during school, you should realize you just have to subtract the count of only-contain-0182569 by the count of only-contain-018 (which means, does not contain 2569) numbers.
The idea is very nice, but using
pow at each iteration will possibly make your time complexity O((lgN)^2) (unless you know to argue with the interviewer that java's pow is O(1) or O(lgN) depending on you). Instead, you can iterate on the pow result:class Solution {
private int[] allPossibleCount = new int[] {1, 2, 3, 3, 3, 4, 5, 5, 6, 7}; // 0,1,2,5,6,8,9
private int[] excludeNumCount = new int[] {1, 2, 2, 2, 2, 2, 2, 2, 3, 3}; // 0, 1, 8
private boolean[] isValid = new boolean[] {true, true, true, false,false,true, true, false,true,true}; // 0,1,2,5,6,8,9
private boolean[] isExclude = new boolean[] {true, true, false,false,false,false,false,false,true,false}; // 0,1,8
public int rotatedDigits(int N) {
char[] cs = Integer.toString(N).toCharArray();
int len = cs.length, count = 0;
boolean exclude = true;
int base7 = (int) Math.pow (7, len - 1), base3 = (int) Math.pow (3, len - 1);
for (int i = 0; i < len; i++, base7 /= 7, base3 /= 3) {
if (cs[i] == '0' && i != len - 1) continue;
int index = i == len - 1 ? cs[i] - '0' : cs[i] - '0' - 1;
double c = allPossibleCount[index] * base7;
double e = exclude ? excludeNumCount[index] * base3 : 0; // # of numbers which only contain 0,1,8
count += c - e;
if (!isValid[cs[i] - '0']) break;
exclude = exclude & isExclude[cs[i] - '0'];
}
return count;
}https://leetcode.com/problems/rotated-digits/discuss/116530/O(logN)-Solution
+= 7 **means you could pick digits from this set[0, 1, 8, 2, 5, 6, 9], there are 7 different kinds of digits in this set, right?-= 3 **is similar to the above, except that this time the set is[0, 1, 8]
Here is solution in O(logN) complexity.
def rotatedDigits(self, N):
s1 = set([0, 1, 8])
s2 = set([0, 1, 8, 2, 5, 6, 9])
s = set()
res = 0
N = map(int, str(N))
for i, v in enumerate(N):
for j in range(v):
if s.issubset(s2) and j in s2:
res += 7**(len(N) - i - 1)
if s.issubset(s1) and j in s1:
res -= 3**(len(N) - i - 1)
if v not in s2:
return res
s.add(v)
return res + (s.issubset(s2) and not s.issubset(s1))X. Digit DP
http://www.cnblogs.com/grandyang/p/9154892.html
其实这道题还有更好的解法呢，使用动态规划Dynamic Programming来做的，思路非常巧妙，博主深为叹服。定义了一个长度为N+1的一维布尔型DP数组，其中dp[i]表示数字i的三种状态，0表示数字i翻转后不合法，1表示数字i翻转后和原数相同，2表示数字i翻转后形成一个不同的数字。那么根据题目中的定义可知，只有当dp[i]=2的时候才是好数字。那么下面来看状态转移方程吧，我们知道如果数字只有1位的话，那么判断起来很简单，如果是0，1，和8中的一个，那么dp[i]=1，如果是2，5，6，和9中的一个，那么dp[i]=2，并且结果res自增1。如果是剩下的三个数字3，4，7中的一个不用更新，因为dp数组初始化就为0。下面来看数字i大于10的情况，非常的经典，dp[i] 的值其实可以从 dp[i/10] 和 dp[i%10] 这两个状态值转移而来，由于我们更新的顺序是从小到大，所以当要更新dp[i]的时候，dp[i/10] 和 dp[i%10] 这两个状态值已经算过了。为啥dp[i] 的值是由这两个状态值决定的呢？因为每个数字都是相互独立的翻转，比如四位数字abcd，可以拆分为三位数abc，和个位数d，如果abc翻转后仍是abc，d翻转后仍是d，说明abcd翻转后仍是abcd，所以dp[i]=1，只要其中有一个大于1了，另外一个至少是1的话，那么说明可以翻转成不同的数字，dp[i]=2，并且结果res自增1
https://leetcode.com/problems/rotated-digits/discuss/117975/Java-dp-solution-9ms
Using a int[] for dp.
dp[i] = 0, invalid number
dp[i] = 1, valid and same number
dp[i] = 2, valid and different number
dp[i] = 0, invalid number
dp[i] = 1, valid and same number
dp[i] = 2, valid and different number
public int rotatedDigits(int N) {
int[] dp = new int[N + 1];
int count = 0;
for(int i = 0; i <= N; i++){
if(i < 10){
if(i == 0 || i == 1 || i == 8) dp[i] = 1;
else if(i == 2 || i == 5 || i == 6 || i == 9){
dp[i] = 2;
count++;
}
} else {
int a = dp[i / 10], b = dp[i % 10];
if(a == 1 && b == 1) dp[i] = 1;
else if(a >= 1 && b >= 1){
dp[i] = 2;
count++;
}
}
}
return count;
}https://leetcode.com/problems/rotated-digits/discuss/116547/Easily-Understood-Java-Solution
public int rotatedDigits(int N) {
int count = 0;
for (int i = 1; i <= N; i ++) {
if (isValid(i)) count ++;
}
return count;
}
public boolean isValid(int N) {
/*
Valid if N contains ATLEAST ONE 2, 5, 6, 9
AND NO 3, 4 or 7s
*/
boolean validFound = false;
while (N > 0) {
if (N % 10 == 2) validFound = true;
if (N % 10 == 5) validFound = true;
if (N % 10 == 6) validFound = true;
if (N % 10 == 9) validFound = true;
if (N % 10 == 3) return false;
if (N % 10 == 4) return false;
if (N % 10 == 7) return false;
N = N / 10;
}
return validFound;
}Improved efficiency. Increments i if the leading digit of i is 3, 4 or 7.
For example, if i = 300, then we know 300, 301, 302 ... 399 are all invalid. IncrementIfNeeded(int i) returns 99 to set i to 399 and 400 after i++ from loop increment.
The same thing happens for 400.
Therefore, we only check 300 and 400, rather than 300, 301, 302, ..., 399, 400, 401, 402, ..., 499.
public int rotatedDigits(int N) {
int count = 0;
for (int i = 1; i <= N; i ++) {
if (isValid(i)) count ++;
i += incrementIfNeeded(i);
}
return count;
}
public int incrementIfNeeded(int i) {
int inc = 1;
while (i >= 10) {
inc *= 10;
i /= 10;
}
if (i == 3 || i == 4 || i == 7) return inc - 1;
else return 0;
}
public boolean isValid(int N) {
/*
Valid if N contains ATLEAST ONE 2, 5, 6, 9
AND NO 3, 4 or 7s
*/
boolean validFound = false;
while (N > 0) {
if (N % 10 == 2) validFound = true;
if (N % 10 == 5) validFound = true;
if (N % 10 == 6) validFound = true;
if (N % 10 == 9) validFound = true;
if (N % 10 == 3) return false;
if (N % 10 == 4) return false;
if (N % 10 == 7) return false;
N = N / 10;
}
return validFound;
}def rotatedDigits(self, N):
"""
:type N: int
:rtype: int
"""
dmap = {"0" : "0", "1" : "1", "8" : "8", "2" : "5", "5" : "2", "6" : "9", "9" : "6"}
res = 0
for num in range(1, N + 1):
if any(x in str(num) for x in ["3", "4", "7"]):
continue
if any(x in str(num) for x in ["2", "5", "6", "9"]):
res += 1
return res
