RotatedDigits [source code]
public class RotatedDigits {
static
/******************************************************************************/
class Solution {
public int rotatedDigits(int N) {
if (N == 0)
return 0;
return (isGood (N) ? 1 : 0) + rotatedDigits (N - 1);
}
boolean isGood (int N) {
if (N == 0)
return false;
boolean can_change = false;
while (N > 0) {
int digit = N % 10;
N /= 10;
if (digit == 3 || digit == 4 || digit == 7)
return false;
if (digit == 2 || digit == 5 || digit == 6 || digit == 9)
can_change = true;
}
return can_change;
}
}
/******************************************************************************/
public static void main(String[] args) {
RotatedDigits.Solution tester = new RotatedDigits.Solution();
int[] inputs = {
10, 4,
857, 247,
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int N = inputs[2 * i], ans = inputs[2 * i + 1];
int output = tester.rotatedDigits (N);
System.out.printf ("%s -> %s, expected: %d\n",
N, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
这题其实还是挺不应该的, 当时想了好半天; 刚开始用的这个思路:
class Solution {
public int rotatedDigits(int N) {
int res = 1;
while (N > 0) {
int digit = N % 10;
N /= 10;
res *= helper (digit);
}
return res;
}
int helper (int digit) {
if (digit >= 9)
return 4;
if (digit >= 6)
return 3;
if (digit >= 5)
return 2;
if (digit >= 2)
return 1;
return 0;
}
}
然后这个思路其实错的挺离谱的;
最后就是很直接的暴力做法了;
虽然看起来好像是一个recursion什么的, 其实就是暴力做法;
速度是7ms (NA);
editorial
Approach #1: Brute Force [Accepted]
Intuition
For each X from 1 to N, let's analyze whether X is good.
If X has a digit that does not have a valid rotation (3, 4, or 7), then it can't be good.
If X doesn't have a digit that rotates to a different digit (2, 5, 6, or 9), it can't be good because X will be the same after rotation.
Otherwise, X will successfully rotate to a valid different number.
Algorithm
To handle checking the digits of X, we showcase two implementations. The most obvious way is to parse the string; another way is to recursively check the last digit of X.
See the comments in each implementation for more details.
class Solution {
public int rotatedDigits(int N) {
// Count how many n in [1, N] are good.
int ans = 0;
for (int n = 1; n <= N; ++n)
if (good(n, false)) ans++;
return ans;
}
// Return true if n is good.
// The flag is true iff we have an occurrence of 2, 5, 6, 9.
public boolean good(int n, boolean flag) {
if (n == 0) return flag;
int d = n % 10;
if (d == 3 || d == 4 || d == 7) return false;
if (d == 0 || d == 1 || d == 8) return good(n / 10, flag);
return good(n / 10, true);
}
}
他这里good里面的这个recursion用的还是挺有意思的;
复杂度NlgN;
Approach #2: Dynamic Programming On Digits [Accepted]
Intuition
Say we are writing a good number digit by digit. The necessary and sufficient conditions are: we need to write using only digits from 0125689, write a number less than or equal to N, and write at least one digit from 2569.
We can use dynamic programming to solve this efficiently. Our state will be how many digits i we have written, whether we have previously written a jth digit lower than the jth digit of N, and whether we have previously written a digit from 2569. We will represent this state by three variables: i, equality_flag, involution_flag.
dp(i, equality_flag, involution_flag) will represent the number of ways to write the suffix of N corresponding to these above conditions. The answer we want is dp(0, True, False).
Algorithm
If equality_flag is true, the ith digit (0 indexed) will be at most the ith digit of N. For each digit d, we determine if we can write d based on the flags that are currently set.
In the below implementations, we showcase both top-down and bottom-up approaches. The four lines in the top-down approach (Python) from for d in xrange(... to before memo[...] = ans clearly illustrates the recursive relationship between states in our dynamic programming.
class Solution {
public int rotatedDigits(int N) {
char[] A = String.valueOf(N).toCharArray();
int K = A.length;
int[][][] memo = new int[K+1][2][2];
memo[K][0][1] = memo[K][1][1] = 1;
for (int i = K - 1; i >= 0; --i) {
for (int eqf = 0; eqf <= 1; ++eqf)
for (int invf = 0; invf <= 1; ++invf) {
// We will compute ans = memo[i][eqf][invf],
// the number of good numbers with respect to N = A[i:].
// If eqf is true, we must stay below N, otherwise
// we can use any digits.
// Invf becomes true when we write a 2569, and it
// must be true by the end of our writing as all
// good numbers have a digit in 2569.
int ans = 0;
for (char d = '0'; d <= (eqf == 1 ? A[i] : '9'); ++d) {
if (d == '3' || d == '4' || d == '7') continue;
boolean invo = (d == '2' || d == '5' || d == '6' || d == '9');
ans += memo[i+1][d == A[i] ? eqf : 0][invo ? 1 : invf];
}
memo[i][eqf][invf] = ans;
}
}
return memo[0][1][0];
}
}
他这里对于第三个维度的定义, 我不是很认同, 这个是我的发言:
Dear awice, I am really impressed by the second solution. The code is very solid, though I do not quite agree with your verbal definition of the 3rd dimension:
I think the third dimension should be defined as:
0: we must have at least one 2569 in[i:].1: we may have one 2569 in[i:].
as we can see from the code:
- if
invois 0, which means we are not adding a 2569 at digiti- If
invfis 0, the code shows we look at[i+1][..][0]. That means, we are trying to count good numbers in[i:]that must have at least one 2569, that's why we need to look back at[i+1][..][0], because we don't have one inv digit ati, we have to count on[i+1:]to provide one. - If
invfis 1, then code shows we look at[i+1][..][1]. That means, we are trying to count good numbers in[i:]with maybe one 2569. We did not provide one atibecauseinvo = 0, but it doesn't matter, because we are not mandated by anything. Look at how many good numbers are in[i+1:]that may have 2569.
- If
- if
invois 1, which means we are providing an inv digit of 2569 ati. Then we surely should be looking back at[i+1][..][1]because we provided one 2569 ati, and now it doesn't matter whatinvfis (meaning whether we require there must or may be 2569 in[i:]) because we got one.
And to better explain the initialization of [K][..][1] = 1 and [K][..][0] = 0, I modify the definition of the second dimension as well:
- The second dimension corresponds to whether, the counted numbers included in this
memocell, must be less or equal to the corresponding[K:]of the given numberN.
This is an intuitive interpretation, because, at termination, we only care about [0][1][0] with the second dimension being 1: meaning we only count those numbers that are less or equal to N.
Coming back to the initialization, why is it that the init is only determined by invf? Because talking about [K:], it's empty. Any number we build from digits [K:] of N will be satisfying the less or equal condition. That's why eqf does not matter at all during initialization. Since the definition of invf = 1 indicates a may contain 2569, and we sure have to set those cells to 1 because does not contain belongs to may contain.
Here is a helpful illustration of the first iteration. Be aware of the inversed eqf dimension: I apologize for that:
上面这个我认为对于第三维已经解释的比较到位了; 这个定义其实是稍微有点反常规的, 不是一个简单的binary的定义, 而是一个子集类型的定义, 但是这种DP dimension的定义以前其实是见过的;
后来意识到上面的解释的一个弱点是没有很好的解释这里的init过程; 虽然可以说[k][..][1]等于1, 对应了may有2569的话, 结果就应该是1, 但是如果是[k][..][0], must的话, 那么就应该是0因为现在一个数字还没有; 但是这样的一个解释并没有很好的解释为什么第二维是[1]的初始值不是init到0? 而且严格来说, 如果真的是intuitive的角度来理解, 只要第一维是K, 意思就是[K:]的suffix, 这个根本就肯定是Empty的, 那么你任何的初始值都应该是0.
DP问题的两个实现方面的重点以前也讲过了(当然是你表格设计出来之后, 这个属于设计), 一个是初始化, 一个是填表顺序. 这里感觉这个初始化其实就是一个为了让填表更正常的小的hack; 毕竟这种dot结构本身
这个算法的复杂度是lgN, 很厉害;
这里可以找到关于eqf这个维度的定义; 他这里的处理还是比较巧妙的; 重点关注一下d <= (eqf == 1 ? A[i] : '9')这里和[d == A[i] ? eqf : 0]. 具体的对应原因图上都能找到;
还有一个最关键的, 这题还是用我们NLP的时候见过的dot方法来处理这个digit, 毕竟digit本身就跟string的letter是差不多的; awice轻松写出这样一个思路的算法, 可见这个家伙的科班背景还是很扎实的;
真正面试的时候讲实话还是没把握写出来这样的算法的; 三个维度的DP, 调试起来要调死人; 虽然这个是一个easy的题目, 但是如果像这个算法这样要求logN的复杂度, 我感觉这个DP的思路可以算作是hard了; 自己尝试了一下脑子里调试, 一个小的技巧就是, 脑子里其实只要存放一个二维的表格就行了: 第一维这个长度可以不管, 因为逻辑很trivial, 自然就是向后看; 这个算法回头看看, 无论是设计(从题目意思里面提炼出来这三个维度)还是最后的实现(填表的方法和初始化)要求都相当的高;
又重新修改了上面的评论, 感觉现在应该是解释的比较清楚的了;
https://leetcode.com/problems/rotated-digits/discuss/116547/Easily-Understood-Java-Solution
trivial的解法, 代码不贴了;
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.
还好了, 就是一个小优化;
https://leetcode.com/problems/rotated-digits/discuss/116527/O(len(N))-method
Clearly we can do better than O(N) by reuse results from shorter numbers.
Here is my O(len(N)) method. Took me some time in the contest…
class Solution(object):
def rotatedDigits(self, N):
"""
:type N: int
:rtype: int
"""
# 0 1 2 3 4 5 6 7 8 9
same = [1, 2, 2, 2, 2, 2, 2, 2, 3, 3]
diff = [0, 0, 1, 1, 1, 2, 3, 3, 3, 4]
def calc(num):
if len(num)==1:
return same[int(num)], diff[int(num)]
lead = int(num[0])
if lead == 0:
return calc(num[1:])
else:
n_s, n_d = calc('9'*(len(num)-1))
nxt_same, nxt_diff = calc(num[1:])
s = same[lead-1] * n_s
if lead in [1, 8]:
s += nxt_same
d = (same[lead-1]+diff[lead-1]) * n_d + diff[lead-1] * n_s
if lead in [1, 8]:
d += nxt_diff
if lead in [2, 5, 6, 9]:
d += nxt_diff + nxt_same
return s, d
return calc(str(N))[1]
一点解释都没有, 看了半天看懂了, 意思是差不多的, 这个是我的解释:
Very clean solution. I add some explanations and comments to make it easier to understand. I do hope every OP as brilliant as this one could leave comments at least regarding what your variable and function return values are.
Terminology explanation:
same: count of valid but not good numbers: can rotate but rotate to the same numberdiff: count of good numbers: rotate to a different number
class Solution(object):
def rotatedDigits(self, N):
"""
:type N: int
:rtype: int
"""
# 0 1 2 3 4 5 6 7 8 9
same = [1, 2, 2, 2, 2, 2, 2, 2, 3, 3] # verify the definition with 1-digit number first for yourself
diff = [0, 0, 1, 1, 1, 2, 3, 3, 3, 4]
def calc(num):
if len(num)==1:
return same[int(num)], diff[int(num)]
lead = int(num[0])
if lead == 0:
return calc(num[1:])
else:
n_s, n_d = calc('9'*(len(num)-1))
nxt_same, nxt_diff = calc(num[1:])
"""
How many valid-but-not-good numbers? First, assign digits smaller than LEAD to the leftmost digitIn this case, we can choose any valid-but-not-good numbers for [1:] without making the result number larger than actual N. This is why N_S is calculated from 99..99= same[lead-1] * n_s.
If LEAD is 1 or 8, then we can choose them at [0], but we have to make sure that the trailing digits does not make the resulting number larger than N (this could happen because we are making the highest digit the same as N's), this is why we use NXT_SAME which is calculated from the original N[1:]: we make sure we don't return thingslarger than the input in each iteration, thus we can count on the recused up result from a call to [1:] to include only numbers less or equal to N[1:].
"""
if lead in [1, 8]:
s += nxt_same
"""
Again, does not allow [0] to be LEAD for now: only pick smaller digits. If we have [1:] being DIFF meaning good, then we can assign any digit (that is at least valid) to [0] here, corresponding to the first term.
The second term: if [1:] is valid but no good (SAME), then we have to make sure that digit[0] is DIFF: note we are calculating D which is the DIFF return value for this iteration. Note again we are using N_S/D values calculated from 99..99 rather than NXT_S/D here: more candidates because we ensure the MSB is smaller than N'sthus the combined numbers won't exceed N.
"""
d = (same[lead-1]+diff[lead-1]) * n_d + diff[lead-1] * n_s
"""
Now, what about LEAD itself? If it's SAME, then we have to make sure we have DIFF digits in [1:] so that D has at least one DIFF digit, that's why we add NXT_DIFF.
"""
if lead in [1, 8]:
d += nxt_diff
# IF LEAD is DIFF, then anything returned from N[1:] would do. Of course, we have to use NXT values rather than N_S/D values.
if lead in [2, 5, 6, 9]:
d += nxt_diff + nxt_same
return s, d
return calc(str(N))[1]
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;
for (int i = 0, mul = len; i < len; i++, mul--) {
if (cs[i] == '0' && i != len - 1) continue;
int index = i == len - 1 ? cs[i] - '0' : cs[i] - '0' - 1;
double c = allPossibleCount[index] * Math.pow(7, mul - 1);
double e = exclude ? excludeNumCount[index] * Math.pow(3, mul - 1) : 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;
}
}
他这里反复的要进行一个pow的操作, 我改成这样:
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;
}
}
注意, 这个改动是很必要的, 如果按照他之前那个, 复杂度是O((lgN)^2)吗? 查了一下, 好像一般认为java的这个pow可以说是O(1);
看了半天还是看懂了, 这个算法还是挺有意思的, 这个是我的解释:
And following are some explanation:
If the picture is not enough:
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.
From left to right. At the first digit, we first exclude N[0], then we count the number of only-0182569 numbers in c, then the only-018 numbers, which is stored in e.
The only thing left is what is that exclude for? It's actually for you to deal with N[0] which we have not handled yet. As you can see the picture above, when we now move on, with i++, we actually are handling numbers that start with N[0] rather than 0 itself. 0 led numbers are actually handled in the previous iteration of i==0 because both c and e contains 0.
At i==1, we implicitly have N[0] at the first digit of our to-be-assembled number. Now, we sure should include it in our new c at this iteration, only to choose the trailing parts properly. What about e? For example, if N[0] is 6, then we should not include anything in the new e, because anything like 6+[only_contain_018] does not belong to the only-contain-018 category anymore.
没有submission;
Problem Description
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?
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].
Difficulty:Easy
Total Accepted:1.2K
Total Submissions:2.6K
Contributor: