Medium

题目描述

给你一个非负整数 num，如果 num 可以表示为任何非负整数及其反转的和，则返回 true，否则返回 false。

示例 1：

输入：num = 443
输出：true
解释：172 + 271 = 443，所以我们返回 true。

示例 2：

输入：num = 63
输出：false
解释：63 不能表示为任何非负整数及其反转的和，所以我们返回 false。

示例 3：

输入：num = 181
输出：true
解释：140 + 041 = 181，所以我们返回 true。注意，当一个数字被反转时，可能会有前导零。

约束条件：

  • 0 <= num <= 10^5

提示：

  • 约束条件足够小，我们可以检查每个数字。
  • 要反转一个数字，首先将其转换为字符串。然后，创建一个新字符串，它是第一个字符串的反转。最后，将新字符串转换回数字。

解题思路

这是一道枚举题，关键思路是遍历所有可能的数字，检查该数字与其反转数字的和是否等于目标值。

解题思路：

  1. 暴力枚举法：由于约束条件较小（num <= 10^5），我们可以遍历从 0 到 num 的所有数字 i，检查 i + reverse(i) 是否等于 num。

  2. 数字反转：实现一个反转数字的函数。可以通过字符串反转或数学方法实现。字符串方法更直观，数学方法更高效。

  3. 优化范围：理论上只需要遍历到 num，因为如果 i > num，那么 i + reverse(i) 必然大于 num。

  4. 特殊情况：当 num = 0 时，0 + reverse(0) = 0，所以返回 true。

算法步骤：

  • 遍历 i 从 0 到 num
  • 计算 i 的反转数字 reversed_i
  • 如果 i + reversed_i == num，返回 true
  • 遍历结束后返回 false

推荐使用字符串反转方法，代码更清晰易懂。

代码实现

class Solution {
public:
    bool sumOfNumberAndReverse(int num) {
        for (int i = 0; i <= num; i++) {
            if (i + reverse(i) == num) {
                return true;
            }
        }
        return false;
    }
    
private:
    int reverse(int n) {
        string s = to_string(n);
        std::reverse(s.begin(), s.end());
        return stoi(s);
    }
};

class Solution:
    def sumOfNumberAndReverse(self, num: int) -> bool:
        def reverse(n):
            return int(str(n)[::-1])
        
        for i in range(num + 1):
            if i + reverse(i) == num:
                return True
        return False

public class Solution {
    public bool SumOfNumberAndReverse(int num) {
        for (int i = 0; i <= num; i++) {
            if (i + Reverse(i) == num) {
                return true;
            }
        }
        return false;
    }
    
    private int Reverse(int n) {
        string s = n.ToString();
        char[] chars = s.ToCharArray();
        Array.Reverse(chars);
        return int.Parse(new string(chars));
    }
}

var sumOfNumberAndReverse = function(num) {
    const reverse = (n) => {
        return parseInt(n.toString().split('').reverse().join(''));
    };
    
    for (let i = 0; i <= num; i++) {
        if (i + reverse(i) === num) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log n)需要遍历 0 到 n 的所有数字，每次反转数字需要 O(log n) 时间
空间复杂度O(log n)字符串反转需要额外空间存储数字的字符串表示

相关题目