今天是2020年02月02日，被誉为“千年一遇的对称日”。20200202的优劣是一样的，反正都是“爱你爱你”的意思。很多新人选择今天作为领证的日子，但是因为肺炎的原因，有些地方已经取消了今天的预约。不过今天我们先不谈这个日子的意义，我们来聊聊技术相关的话题。20200202这种前后相同的字符串在算法上叫做“回文”，因为结构的不同，又分为回文数、回文串、回文链表等。这里分别扩展了几道Leetcode算法题。今天我们就在别人领证的这一天，复习“回文”相关的算法题。1.验证回文串今天的日期，用字符串表示为“20200202”，这是一个回文串。所以如果要写一个方法来验证是否是回文字符串，最简单的思路就是翻转字符串比较。booleanisPalindrome(Strings){returnnewStringBuilder(s).reverse().equals(s)}但是在大多数情况下，我们是不允许直接使用Api的。另外，比较常用的方法是用2个指针，从字符串的前后两个方向，向内夹。booleanisPalindrome(Strings){inti=0;intj=s.length()-1;while(irevertedNumber){revertedNumber=revertedNumber*10+x%10;x/=10;}returnx==revertedNumber||x==revertedNumber/10;}简要说明：1、先做一些简单的验证。如果一个大于0的非零数的个位为0，那么它就注定不是回文数。因为对应的回文位置是数的最高位，而最高位不会为0。2.通过循环，在每次循环中，逐位生成翻转后的数，原数的最低位为被踢出。3、如果跳出循环，说明后半部分已经被翻转了，那么考虑两种情况，数字长度是奇数还是偶数。然后判断原数x和倒数reversedNumber是否相同。另外，这道题是Leetcode上的“9.回文数”题。3.验证回文列表。回文串和回文数都提到了。接下来，让我们看一下回文列表。对于单向链表的特殊结构，确定一个长度需要O(n)的复杂度，而且没有前驱指针，所以双指针来回裁剪的方法是没有用的。当然，我们可以将其转化为我们熟悉的回文数或者回文串进行计算，但这也没有利用到链表的特性。在验证回文链表的场景中，我们可以通过快慢指针找到链表的中间节点，然后将原链表倒转一半，然后开始比较。为了提高效率，这两个步骤可以合并为1个循环。publicbooleanisPalindrome(ListNodehead){if(head==null||head.next==null){returntrue;}ListNodeslow=head,fast=head;ListNodepre=head,prepre=null;while(fast!=null&&fast.next!=null){pre=slow;slow=slow.next;fast=fast.next.next;pre.next=prepre;prepre=pre;}//如果fast不为null，表示为奇数，并且还需要多一位if(fast!=null){slow=slow.next;}//此时pre为将原链表前半部分反转的子链表//slow为中间原链表节点while(pre!=null&&slow!=null){if(pre.val!=slow.val){returnfalse;}pre=pre.next;slow=slow.next;}returntrue;}后第一个循环，慢节点指向链表的中间，而pre是翻转原链表前半部分的子链表。然后通过一个while循环，将它们一一比较，得到我们想要的结果。另外，这道题是Leetcode上的“234.回文链表”题。4.总结时刻今天就到这里。20200202这一天，我们复习了回文相关的算法题。可以总结出什么规律？欢迎在留言区讨论。受疫情影响，明天开始很多朋友都会转为在家远程办公。祝你一切顺利。
