2443-反转之后的数字和

给你一个 非负 整数 num 。如果存在某个 非负 整数 k 满足 k + reverse(k) = num ，则返回
true ；否则，返回 __false 。

reverse(k) 表示 k 反转每个数位后得到的数字。

示例 1：

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

示例 2：

**输入：** num = 63
**输出：** false
**解释：** 63 不能表示为非负整数及其反转后数字之和，返回 false 。

示例 3：

**输入：** num = 181
**输出：** true
**解释：** 140 + 041 = 181 ，所以返回 true 。注意，反转后的数字可能包含前导零。

提示：

• 0 <= num <= 105

问题定义

定义 f(i, j, pre, suf) 为在满足下列条件的情况下，数字 N 中的子数字序列 N[i..j] （下标从 0 开始）是否可以由两个互为逆序的数字 K，reverse(K) 相加而来，其中：

• 如果 pre = 1，表示相加的结果需要向左侧进一位，进位完成之后剩下的结果和 N[i…j] 相同；

• 如果 suf = 1，表示在两数相加之前，已经有从低位传来的进位，相加结果需要把这个进位考虑进去。

举例说明：对于数字 12345，f(1,3,1,1) 表示，是否能找到三位数 k ，使得 k + erverse(k) + 进位的 1 = 1234（去掉向高位进位的 1，剩下的结果和 num[1…3] = 234 相同）。（注意下标从 0 开始）

求解代码

先上代码，解释附后。

class Solution {
public:
    bool sumOfNumberAndReverse(int num) {
        string s = to_string(num);
        function<bool(int,int,int,int)> f = [&](int i, int j, int pre, int suf) {
            if(i < j) {
                for(int m = 0, sum = pre * 10 + (s[i] - '0') - m; m <= 1; ++m, --sum)
                    if(sum >= int(i == 0) && sum <= 18 && (sum + suf) % 10 == s[j] - '0')
                        return f(i + 1, j - 1, m, (sum + suf) / 10);
                return false;
            }
            return (i == j && (s[i] & 1) == suf) || (i > j && pre == suf);
        };
        return f(0, s.size()-1, 0, 0) || (s[0]=='1' && f(1, s.size()-1, 1, 0));
    }
};

求解过程解释

我们把目标数字序列 N[i…j] 记作 N_iN_{i+1}…N_{j，把 K 记作 K_iK_{i+1}…K_{j。

下面用分类讨论的方式求解 f(i, j, pre, suf)。

当 i < j 时：

首先，将 K + reverse(K) 的结果分成三部分：首位数字 + 中间部分 + 末位数字。需要注意的是，首位数字 包含进位，举例说明，888 + 888 的结果是 1776，那么其首位数字按 17 计算，末位数字按 6 计算。

然后，枚举 m = K + reverse(K) 的结果中，从 中间部分 而来的进位。显然 m 只能取到 0,1。

对于每一个 m，为了让 K + reverse(K) 在考虑左侧进位 pre 和右侧进位 suf 的情况下，和目标数字 N 相等，需要满足下列条件（下图可帮助理解）：

• 条件一（取值范围）：0 \le K_i + K_j \le 18。特别地，当 i = 0 时，K_i + K_j \ne 0，否则会导致 K 和 reverse(K) 的首、末位均为 0，不合题意。
• 条件二（首位相同）：K_i + K_j + m = 10\times pre + N_i。
• 条件三（末位相同）：(K_i + K_j + suf) \mod 10 = N_j。
• 条件四（中间部分相同）：\displaystyle{f(i+1, j-1, m, \left \lfloor K_i + K_j + suf}{10} \right \rfloor ) = \texttt{True}。

求解时，首先根据条件二求出 sum = K_i + K_j = 10\times pre + N_i - m，然后带入条件一和条件三，如果满足，再求解条件四（转换为子问题）。注意，条件一、二、三最多只能满足 m = 0 或者 m = 1 的其中一个，因此转换为子问题的路径 最多只有一条。因此时间复杂度是和数字的位数 \log(N) 成线性关系的。

当 i = j 时：

• 由于一位数字取反后仍然加到自身，故每次只能 +2，无法改变奇偶性，因此目标数字的对应位的奇偶性需要和 suf，也就是从低位进位的奇偶性相同。

当 i > j 时：

• 为空字符串，需要 pre 和 suf 相同（进位需求和进位供给平衡）。

特殊情况

• 如果数字的 N 的首位是 1，那么它还可能由 n-1 位数字与逆序数相加、进位而来，此时可以调用 f(1,n-1,1,0) 再判一次。

时间复杂度

O(log(N))。