Leetcode 回文数总结

布满荆棘的人生 2024-04-18 10:52 31阅读 0赞

### 文章目录 ###

*  1. 验证回文串
 *  2. 回文数

# 1. 验证回文串 #

[Leetcode 125. 验证回文串][Leetcode 125.]

**双指针**：定义左、右双指针，向中间判断；跳过非数字字母的字符；将字母全部转化为小写再判断。

class Solution { 
        public boolean isPalindrome(String s) { 
            if (s == null || s.length() == 0) { 
                return true;
            }
    
            char[] chs = s.toCharArray();
            int l = 0;
            int r = s.length() - 1;
            while (l <= r) { 
                if (!isValid(chs[l])) { 
                    l++;
                    continue;
                }
                if (!isValid(chs[r])) { 
                    r--;
                    continue;
                }
                if (Character.toLowerCase(chs[l]) != Character.toLowerCase(chs[r])) { 
                    return false;
                }
                l++;
                r--;
            }
            return true;
        }
    
        private boolean isValid(char ch) { 
            if ('0' <= ch && ch <= '9' || 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z') { 
                return true;
            } else { 
                return false;
            }
        }
    }

# 2. 回文数 #

[Leetcode 9. 回文数][Leetcode 9.]

**转化为字符串**：

class Solution { 
        public boolean isPalindrome(int x) { 
            if (x < 0) { 
                return false;
            }
    
            StringBuilder sb = new StringBuilder();
            while (x != 0) { 
                sb.append(x % 10);
                x = x / 10;
            }
            for (int i = 0; i < (sb.length() + 1) / 2; i++) { 
                if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) { 
                    return false;
                }
            }
            return true;
        }
    }

**除余运算**：

class Solution {
        public boolean isPalindrome(int x) {
            if (x < 0) {
                return false;
            }
    
            int div = 1;
            while (x / div >= 10) {
                div *= 10;
            }
            while (x != 0) {
                if (x / div != x % 10) {
                    return false;
                }
                x = x % div / 10;
                div /= 100;
            }
            return true;
        }
    }

**翻转后半部分**：

循环终止条件：前半部分小于等于后半部分时，翻转刚好一半或者过半。

判断相等：数字总长度为偶数时，直接判断前后是否相等；数字长度为奇数时，中间数字位于后半部分的最低位上，除十再比较。

class Solution {
        public boolean isPalindrome(int x) {
            if (x < 0 || x % 10 == 0 && x != 0) {
                return false;
            }
    
            int y = 0;
            while (x > y) {
                y = y * 10 + x % 10;
                x = x / 10;
            }
    
            return x == y || x == y / 10;
        }
    }

[Leetcode 125.]: https://leetcode-cn.com/problems/valid-palindrome/
[Leetcode 9.]: https://leetcode-cn.com/problems/palindrome-number/