这道题思路并不复杂，主要是实现比较麻烦，需要考虑各种各样的情况。那么首先可以明确的一点是，对于一个数，我们要寻找大于它的最小回文prev和小于它的最大回文next。这里面差值最小的那个就是答案。这里面有几种情况：
- 直接用前半部分镜像生成，比如1234->1221(prev)，35212->35253(next)
- 用前半部分+1镜像生成，比如1234->1331(next), 345->353(next)
- 用前半部分-1镜像生成，比如1200->1111(prev), 341->333(prev)
所以我们需要生成这三个数，然后取差值最小的。需要注意的是，这里面有几种情况我们需要特殊处理：
- 当用前半部分+1的时候位数变多了并且当前数长度为偶数，比如99，我们取前半部分9，9+1 = 10，这时候我们就需要生成奇数长度101而不是1001
- 当用前半部分+1的时候位数变多了并且当前数长度为奇数，比如999，我们取前半部分99，99+1 = 100，我们需要抹去最后一位变为10，并且生成偶数长度1001
- 当用前半部分-1的时候位数变少了并且当前数长度为偶数，比如1000，我们取前半部分10，10 - 1= 9，这时候我们要额外在末尾补9，并且生成奇数长度999
- 用前半部分-1的时候位数变少了并且当前数长度为奇数，比如100，我们取前半部分10，10 - 1= 9，这时候我们要生成偶数长度99
假设输入string长度为L，O(L)时间就可以做到并且不需要额外空间，代码如下：
No comments:
Post a Comment