leetcode1088
参考了CSDN上一位博主提供的C++的代码:
class Solution {
public:
int confusingNumberII(int N) {
n = N;
ans = 0;
search(0);
return ans;
}
private:
int n, ans;
void search(long long num) {
if (num > n) return;
if (num) {
if (rotate(num) != num) ++ ans;
}
if (num) search(num * 10);
search(num * 10 + 1);
search(num * 10 + 6);
search(num * 10 + 8);
search(num * 10 + 9);
}
long long rotate(long long x) {
long long y = 0;
for (; x; x /= 10) {
int k = x % 10;
switch (k) {
case 6: k = 9; break;
case 9: k = 6; break;
}
y = y * 10 + k;
}
return y;
}
};
我尝试转换成python,但是却超时了:
1 class Solution:
2 def __init__(self):
3 self.n = 0
4 self.ans = 0
5
6 def confusingNumberII(self, N: int) -> int:
7 self.n = N
8 self.searchNumber(0)
9 return self.ans
10
11 def searchNumber(self,num):
12 if num > self.n:
13 return
14 #if self.confusingNumber(num):
15 if num != 0 and self.rotate(num) != num:
16 self.ans += 1
17 #print(str(self.ans) +":"+ str(num))
18 if num != 0:
19 self.searchNumber(num * 10)
20 self.searchNumber(num * 10 + 1)
21 self.searchNumber(num * 10 + 6)
22 self.searchNumber(num * 10 + 8)
23 self.searchNumber(num * 10 + 9)
24
25 def rotate(self,x):
26 y = 0
27 while x != 0:
28 k = x % 10
29 if k == 6:
30 k = 9
31 elif k == 9:
32 k = 6
33 y = y * 10 + k
34 x = x // 10
35 return y
超时的测试用例:1000000000,答案:1950627,python在我本机执行时间:11.3s。
目前没想到解决办法。
转载于//www.cnblogs.com/asenyang/p/11032348.html
还没有评论,来说两句吧...