【必备算法】字符串（回文问题）：LeetCode题 9. 回文数，234. 回文链表

古城微笑少年丶 2022-12-16 05:54 109阅读 0赞

文章开头先放个传送门，是回文字符串相关的LeetCode题 字符串（回文问题）：LeetCode题 125. 验证回文串，680. 验证回文字符串 Ⅱ，647. 回文子串，5. 最长回文子串，两篇可以对比着看。

9. 回文数¹

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

  1. 输入: 121
  2. 输出: true

示例 2:

  1. 输入: -121
  2. 输出: false
  3. 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

  1. 输入: 10
  2. 输出: false
  3. 解释: 从右向左读, 为 01 。因此它不是一个回文数。

解法一：转成回文串

  • 思路：转换为字符串，然后问题变为字符串是否回文问题

  • 复杂度

    • Time：O（n）
    • Space：O（n），需要额外一个字符串的空间

    public boolean isPalindrome(int x) {

    1.     // 数字转字符串直接 +“”
    2.     String s = x + "";
    3.     int i = 0, j = s.length() - 1;
    4.     // 判断回文串模板
    5.     while (i < j) {
    7.         if (s.charAt(i) != s.charAt(j)) return false;
    8.         i++; j--;
    9.     }
    10.     return true;
    11. }

解法二：倒序比较

  • 思路：那有没有一种不转为字符串的求法？有，求出当前数字逆序后的数值，然后比较（如123，逆序数为321），如果相等则回文。

  • 复杂度

    • Time：O（n）
    • Space：O（1），数值操作，没有额外空间

    public boolean isPalindrome(int x) {

    1.     if (x < 0) return false;
    2.     // 因为 x 后面还要比较，所以这里再拿一个变量保存
    3.     int tmp = x;
    4.     // 因为逆序后可能超出int范围如19999999999999
    5.     long y = 0;
    6.     while (tmp != 0) {
    8.         // 1.求末位
    9.         int num = tmp % 10;
    10.         // 2.进位相加
    11.         y = y * 10 + num;
    12.         // 3.除10右移
    13.         tmp = tmp / 10;
    14.     }
    15.     // 比较是否相同
    16.     return x == y;
    17. }

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

  1. 输入: 1->2
  2. 输出: false

示例 2:

  1. 输入: 1->2->2->1
  2. 输出: true

解法一：栈

  • 思路：遍历链表，将所有节点压入栈，再遍历一遍进行对比。这里切记，栈里应该存的是val，而不是ListNode，因为比较的时候顺序是相反的

  • 复杂度

    • Time：O（n）
    • Space：O（n），用了个Stack

    public boolean isPalindrome(ListNode head) {

    1.     // 注：栈里存的是具体value
    2.     Stack<Integer> stack = new Stack<>();
    3.     // 注：链表用for遍历更简洁
    4.     for (ListNode p = head; p != null; p = p.next) 
    5.         stack.push(p.val);
    6.     for (ListNode p = head; p != null; p = p.next)
    7.         if (p.val != stack.pop())
    8.             return false;
    9.     return true;
    10. }

解法二：折半对比

  • 思路：将链表前一半逆序，同时进行遍历比较。这里注意，若长度是奇数情况，则要将后面的指针（cur）后移一位

  • 复杂度：

    • Time：O(n)
    • Space：O(1)

    public boolean isPalindrome(ListNode head) {

    1.     // 1.计算链表长度
    2.     int len = 0;
    3.     for (ListNode p = head; p != null; p = p.next) len++;
    5.     // 2.将链表前一半倒序
    6.     ListNode cur = head, pre = null;
    7.     for (int i = 0; i < len / 2; i++) {
    9.         // 以下四步跟交换一样，都是模板套路
    10.         ListNode tmp = cur.next;
    11.         cur.next = pre;
    12.         pre = cur;
    13.         cur = tmp;
    14.     }
    16.     // 注：若长度是奇数，则要将cur后移一位再比较
    17.     if (len % 2 == 1) cur = cur.next;
    18.     // 3.同时遍历前一半与后一半，比较val
    19.     for (; pre != null && cur != null; pre = pre.next, cur = cur.next) 
    20.         if (pre.val != cur.val)
    21.             return false;
    23.     return true;
    24. }

发表评论

表情：
评论列表 （有 0 条评论，109人围观）

还没有评论，来说两句吧...

相关阅读