leetcode1088

ゝ一世哀愁。 2021-12-19 04:07 720阅读 0赞

参考了CSDN上一位博主提供的C++的代码:

  1. class Solution {
  2. public:
  3. int confusingNumberII(int N) {
  4. n = N;
  5. ans = 0;
  6. search(0);
  7. return ans;
  8. }
  9. private:
  10. int n, ans;
  11. void search(long long num) {
  12. if (num > n) return;
  13. if (num) {
  14. if (rotate(num) != num) ++ ans;
  15. }
  16. if (num) search(num * 10);
  17. search(num * 10 + 1);
  18. search(num * 10 + 6);
  19. search(num * 10 + 8);
  20. search(num * 10 + 9);
  21. }
  22. long long rotate(long long x) {
  23. long long y = 0;
  24. for (; x; x /= 10) {
  25. int k = x % 10;
  26. switch (k) {
  27. case 6: k = 9; break;
  28. case 9: k = 6; break;
  29. }
  30. y = y * 10 + k;
  31. }
  32. return y;
  33. }
  34. };

我尝试转换成python,但是却超时了:

  1. 1 class Solution:
  2. 2 def __init__(self):
  3. 3 self.n = 0
  4. 4 self.ans = 0
  5. 5
  6. 6 def confusingNumberII(self, N: int) -> int:
  7. 7 self.n = N
  8. 8 self.searchNumber(0)
  9. 9 return self.ans
  10. 10
  11. 11 def searchNumber(self,num):
  12. 12 if num > self.n:
  13. 13 return
  14. 14 #if self.confusingNumber(num):
  15. 15 if num != 0 and self.rotate(num) != num:
  16. 16 self.ans += 1
  17. 17 #print(str(self.ans) +":"+ str(num))
  18. 18 if num != 0:
  19. 19 self.searchNumber(num * 10)
  20. 20 self.searchNumber(num * 10 + 1)
  21. 21 self.searchNumber(num * 10 + 6)
  22. 22 self.searchNumber(num * 10 + 8)
  23. 23 self.searchNumber(num * 10 + 9)
  24. 24
  25. 25 def rotate(self,x):
  26. 26 y = 0
  27. 27 while x != 0:
  28. 28 k = x % 10
  29. 29 if k == 6:
  30. 30 k = 9
  31. 31 elif k == 9:
  32. 32 k = 6
  33. 33 y = y * 10 + k
  34. 34 x = x // 10
  35. 35 return y

超时的测试用例:1000000000,答案:1950627,python在我本机执行时间:11.3s。

目前没想到解决办法。

转载于:https://www.cnblogs.com/asenyang/p/11032348.html

发表评论

表情:
评论列表 (有 0 条评论,720人围观)

还没有评论,来说两句吧...

相关阅读

    相关 1088滑雪

    1088:滑雪 总时间限制: 1000ms 内存限制: 65536kB 描述 Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域

    相关 POJ 1088 sking

    给你个二维数组让你找到这个二维数组的最长下降路径的长度,可以向上下左右四个方向移动。 原来刚看题目是以为是深搜,后来仔细一看发现深搜明显会TLE;就加了记忆化搜索。

    相关 P1088 火星人

    [原题链接][Link 1] 题目描述 人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这