C++回文唯一解，给出错误

Question

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) {
            return false;
        }
        if(x < 10){
          return true;
        }
        int s = 0;
        int en = floor(log10(x));
        while(s < en){
          if(x % 10 != ((x / int(pow(10, en))))) {
              return false;
          }
          x = (x % int(pow(10, en))) / 10;
          s++;
          en--;
        }
        return true;
    }
};

此代码通过了许多测试用例，但在 9999,11211,112211 等测试用例中失败并返回 false

代码解释 在此代码中，我使用两个变量 s 代表开始，en 代表结束 通过这两个变量，我正在运行一个 while 循环，同时从左到右遍历整数并检查它们是否相等

[https://leetcode.com/problems/palindrome-number/] 我在这里做的

我试图在 O(n/2) 时间内打印数字是否为回文

Answer 1

先转换成十进制字符串才真正符合你的利益！

这避免了整个世界的灾难。 一旦你这样做了，它就非常简单了。

你从哪里得到目标为 O(n/2) 的想法？在这样的表达式中只有 n 的幂重要。你是说 n^(1/2) 吗？

并且避免说像

this code has no error but is giving false on test cases

这样的话，因为它会让读者发笑。

Answer 2

您在链接中展示了 Leetcode 中的原始问题：

请看这里。。它允许在第一步中通过将数字转换为字符串来提供解决方案。这将产生一段非常简单的代码，因为您可以使用带有反向迭代器的

std::string

s 范围构造函数简单地构造第二个反向字符串。真的很简单。

然后 Leetcode 要求在不进行字符串转换的情况下执行此操作。在这里，我们可以使用标准方法将数字拆分为具有模数和整数除法的数字。我们提取的数字将乘以十次方并反转，

请看下面的简单例子，展示了这两种方法。

#include <iostream>
#include <string>

class Solution {
public:
    bool isPalindrome1(int x) {
        std::string s{ std::to_string(x) };
        return (x >= 0) and (s == std::string{ s.rbegin(), s.rend() });
    }
    bool isPalindrome2(int x) {
        if (x < 0) return false;
        long long reversedNumber{}, y{ x }; // because of potential overflow
        while (y > 0) {
            reversedNumber = reversedNumber * 10 + y % 10;
            y /= 10;
        }
        return x == reversedNumber;
    }
};
int main() {
    Solution s{};
    std::cout << s.isPalindrome1(123454321) << '\n';
    std::cout << s.isPalindrome2(123454321) << '\n';
}

Answer 3

那样不是更简单吗？

bool isPalindrome(int x){
    auto str = std::to_string(x);
    int l = 0;
    int r = str.size()-1;
    while(l < r){
       if(str[l] != str[r]) return false;
       l++;
       r--;
    }
    return true;
}

Answer 4

我不完全确定存在哪些要求，以及您到底想做什么以及为什么。

我相信，如果我曾经遇到过这个特定问题，我会将 (base10) 数字转换为一个字符数组，然后将 char left 与 char right 进行比较。

据我所知，不存在将 base10 值转换为 base2 或 base16 的良好、可靠和高效的方法，因此将其转换为 char 似乎是最直接的方法。如果它在 base2 或 base16 中，你可以只使用 bitshift 和 bitmasks 来进行比较，但由于没有好的方法来“隔离和转移”base10 数字，所以它感觉不是解决问题的好方法，为什么您应该将每个 base10 数字转换为一个字符。

有关如何转换为字符数组的信息，请参见：https://en.cppreference.com/w/cpp/utility/to_chars

这是它的样子：

bool isPalindrome(int input)
{
    std::array<char, 32> arr;
    auto begin = arr.data();
    auto result = std::to_chars(begin, begin + sizeof(arr), input);
    auto end = result.ptr;
    auto numIterations = (end - begin) / 2;

    // todo: insert algorithm here 
    // foreach ...
    // char left = arr[...]
    // char right = arr[...]
    // compare left vs right
}