leetcode1088

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

参考了CSDN上一位博主提供的[C++的代码][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。

目前没想到解决办法。

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

[C]: https://blog.csdn.net/Csdn_jey/article/details/92252222