题目描述
思路解析动画文字版
记住这对指针: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、能否不转字符串、个位数边界。
参考代码
def isPalindrome(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)
易错点
面试追问把动画讲成自己的话
追问为什么负数一定不是回文?
追问不转成字符串能做吗?
追问个位数(如 7)是回文吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题