题目描述
思路解析动画文字版
记住这对指针:l 从左、r 从右,一对对往中间收。逐对相等 → 继续;有一对不等 → 立刻判否。下面把 12 位数走完。
把 123456654321 拆成 12 位排开。左指针 l 站在最左边的下标 0,右指针 r 站在最右边的下标 11,准备一对对地比。
这一对里,左指针 l 落在下标 0,它的值是 1(高亮的这位)。
右指针 r 落在下标 11,它的值是 1。现在把这一对的两位 1 和 1 拿来比。
1 和 1 相等,这一对通过。左指针往右挪一格、右指针往左挪一格,去比更靠中间的下一对。
这一对里,左指针 l 落在下标 1,它的值是 2(高亮的这位)。
右指针 r 落在下标 10,它的值是 2。现在把这一对的两位 2 和 2 拿来比。
2 和 2 相等,这一对通过。左指针往右挪一格、右指针往左挪一格,去比更靠中间的下一对。
这一对里,左指针 l 落在下标 2,它的值是 3(高亮的这位)。
右指针 r 落在下标 9,它的值是 3。现在把这一对的两位 3 和 3 拿来比。
3 和 3 相等,这一对通过。左指针往右挪一格、右指针往左挪一格,去比更靠中间的下一对。
这一对里,左指针 l 落在下标 3,它的值是 4(高亮的这位)。
右指针 r 落在下标 8,它的值是 4。现在把这一对的两位 4 和 4 拿来比。
4 和 4 相等,这一对通过。左指针往右挪一格、右指针往左挪一格,去比更靠中间的下一对。
这一对里,左指针 l 落在下标 4,它的值是 5(高亮的这位)。
右指针 r 落在下标 7,它的值是 5。现在把这一对的两位 5 和 5 拿来比。
5 和 5 相等,这一对通过。左指针往右挪一格、右指针往左挪一格,去比更靠中间的下一对。
这一对里,左指针 l 落在下标 5,它的值是 6(高亮的这位)。
右指针 r 落在下标 6,它的值是 6。现在把这一对的两位 6 和 6 拿来比。
6 和 6 相等,这一对通过。左指针往右挪一格、右指针往左挪一格,去比更靠中间的下一对。
所有对都比过、且对对相等,两个指针在中间会合。123456654321 正着倒着读完全一样,是回文数,返回 true。
三个高频追问:负数为何 false、能否不转字符串、个位数边界。
参考代码
class Solution: def isPalindrome(self, x): if x < 0: # 负数一定不是回文(有负号) return False s = str(x) # 拆成每一位 l, r = 0, len(s) - 1 while l < r: # 从两端向中间逐对比 if s[l] != s[r]: return False l += 1; r -= 1 return True复杂度
- 时间:O(n),n 是数字的位数,两个指针合起来最多扫一遍所有位
- 空间:O(1),只用 l、r 两个指针;按位取数还能不转字符串、做到真正 O(1)