LeetCode 687. 最长同值路径

Category Difficulty Total Accepted: Total Submissions:
algorithms Hard (33.09%) 5.7K 17.3K

Tags
greedy

Companies

无

题目:

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。

示例:

输入：L = "4", R = "1000"
输出：4
解释：
4，9，121，以及 484 是超级回文数。
注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数。

提示:

  • 1 <= len( L ) <= 18
  • 1 <= len( R ) <= 18
  • L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
  • int( L ) <= int( R )

思路

greedy

贪心算法,将数倒置然后进行==运算,最后判断是否在[L,R]区间内. 注意i为右值的平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// @lc code=start
class Solution {
public:
    int superpalindromesInRange(string left, string right) {
        long long leftNum = stoll(left);
        long long rightNum = stoll(right);
        int count = 0;
        for (long long i = sqrt(leftNum); i <= sqrt(rightNum); i++) {
            if (dfsNumber(i) && dfsNumber(i * i)) {
                count++;
            }
        }
        return count;
    }
private:
    bool dfsNumber(long long number) {
        if (number < 0) return false;
        long long x = number, y = 0;
        while (number > 0) {
            y = y * 10 + number % 10;number /= 10;//反转
        }
        return x == y;
    }
};

// @lc code=end

测试用例

悲

leetcode评论区

难绷

  1. 来自评论区ffreturn佬的解答

解题思路
思路其实很直观

按照范围去找基础数字i，然后构建回文数字m， 然后判断p=r^2是否在范围内和p是回文，是的话则计数器+1
i的查找范围： 题目告诉我们范围是10^18，那么R就是10^9,而i保守可以设置到10^5,范围是[1,100000]
回文存在两种情况： 偶数和奇数，为了处理简单，也分开来遍历
注意事项： 考虑到数值范围，计算得用long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
>class Solution {
>public:
   int superpalindromesInRange(string left, string right) {
       int res = 0;
       long l = stol(left);
       long r = stol(right);

       // 先判断偶数的情况 ABCCBA
       for (int i = 1; i < 100000; ++i)
       {
           string s = to_string(i);
           string s2 = s;
           reverse(s2.begin(), s2.end());
           long m= stol(s + s2);
           m *= m;
           // 超过范围提前结束遍历
           if (m > r)
           {
               break;
           }
           else if (m >= l && IsPalindrom(m))
           {
               ++res;
           }
       }

       // 再判断奇数的情况 ABCBA
       for (int i = 1; i < 100000; ++i)
       {
           string s = to_string(i);
           string s2 = s;
           reverse(s2.begin(), s2.end());
           long m= stol(s.append(s2.begin()+1, s2.end()));
           m *= m;
           // 超过范围提前结束遍历
           if (m > r)
           {
               break;
           }
           else if (m >= l && IsPalindrom(m))
           {
               ++res;
           }
       }

       return res;
   }

   bool IsPalindrom(long num)
   {
       long n = num;
       // 倒序的数字
       long revNum = 0;
       while (n > 0)
       {
           revNum = revNum * 10 + n % 10;
           n /= 10;
       }
       // 直接比较是否相等即可
       return revNum == num;
   }
>};