LeetCode每日一题--验证回文串

前言

今天题目是误打误撞遇到的。原本想刷一下五大常用算法之一的— 贪心算法 ，用标签搜了一下贪心算法，点进去之后发现并不是。但是遇到就是缘分，并且这题的解题思路很像快速排序，因此今天顺便复习一下快速排序，也同时可以复习一下五大常用算法的另一种— 分治算法 。明天应该会整理一下贪心算法的解题思路。

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

1 2	输入: "A man, a plan, a canal: Panama" 输出: true

示例 2:

1 2	输入: "race a car" 输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

对于本题，难免会涉及前后两个元素比对。我们可以定义两个 游标 一个从字符串的起始位，一个从字符串的末位，依次遍历。遇到无效字符游标移动到下一个字符，当 left 和 right 相遇之后。说明在此之前所有的元素全部相同。如果在相遇之前已经遇到不匹配的字符，说明匹配失败。

未命名文件.png

根据这样的思路可以写出一段伪代码：

BEGIN:
    while: left!= right then
    do:
        if(left字符无效) then
                left++;
                CONTINUE;
        END if;
        if(right字符无效) then
                right++;
                CONTINUE;
        END if;
        if(left字符！=right字符)
                BREAK;
    END while;
    return left== right;
END

但是这样其实还是有一点问题的， left 真的能每次都遇到 right 吗？如果输入的字符串中有效字符个数是奇数，可以遇到。但是如果有效字符个数是偶数，如 aa , left 和 right 匹配成功。这时， left 和 right 分别移动一个位置，他们便完美的擦肩而过。他们擦肩而过，也能代表在擦肩之前所有的字符串都是匹配上的，因此真实的临界条件应该是 left < right 。整理一下最终的代码为：

class Solution {
    public boolean isPalindrome(String s) {
        String inStr = s.toLowerCase();
        int left = 0, right = inStr.length() - 1;

        while (left < right) {
            if (!Character.isLetterOrDigit(inStr.charAt(left))) {
                ++left;
                continue;
            }
            if (!Character.isLetterOrDigit(inStr.charAt(right))) {
                --right;
                continue;
            }
            if (inStr.charAt(left) != inStr.charAt(right))
                break;
            ++left;
            --right;
        }
        return left >= right;
    }
}

这种游标操作，很容易联想到快速排序。排序算法的思想是在待排序的数列中，首先找一个数字作为基准数。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时候左边的元素肯定全部小于基准数小于右边元素。接着再分别对左右两个分区重复这个操作，直至完全有序。

这里以 47、29、71、99、78、19、24、47 为例。首先选取第一个元素作为基准值。定义两个 游标 i 和 j ，将 i 游标依次向前移动，找到比基准数小的就交换。接着移动游标 j 从左边开始往右边找，找到第 1 个比基准数大的值，让它与基准值交换；然后继续寻找，直到 i 与 j 相遇时结束，最后基准值所在的位置即 k 的位置，也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比 k 上的值大。

所以对于上面的数列 47、29、71、99、78、19、24、47，进行第 1 趟第 1 个交换的排序情况如下，第 1 次的操作情况图所示。

交换之后，j 移动到了下标为 6 的位置，对 i 继续扫描，如图所示。

此时交换后的数列变为 24、29、47、99、78、19、71、47。接下来我们继续对 i、j 进行操作，如图 3 所示，继续进行 i— 及 j++ 的比较操作。

进行了这两次 i、j 的移动、比较、交换之后，我们最终得到的数列是 24、29、19、47、78、99、71、47。接下来我们继续进行 i— 的操作，发现在 i 为 4 时比 47 大不用交换，在 i 为 3 时与 j 相遇，这时就不需要继续移动、比较了，已经找到 k 了，并且 k 的值为 3。我们可以确认一下当前的数列是不是 k 左边的值都比 47 小，而 k 右边的值都比 47 大（由于要保持相对位置不变，所以 47 同样在基准值 47 的右边）。

47 这个值已经落到了它该在的位置，第 1 趟排序完成了。接下来就是以 k 为基准，分为两部分，然后在左右两部分分别执行上述排序操作，最后数据会分为 4 部分；接着对每部分进行操作，直到每部分都只有一个值为止。

样例来源：《数据结构与算法教程》</br>
链接：http://data.biancheng.net/view/117.html

快排代码

public class QuickSort {
    private int[] array;
    public QuickSort(int[] array) {
        this.array = array;
    }
    public void sort() {
        quickSort(array, 0, array.length - 1);
    }
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
   
    /**
     * 递归排序
     * @param src
     * @param begin
     * @param end
     */
    private void quickSort(int[] src, int begin, int end) {
        if (begin < end) {
            int key = src[begin];
            int i = begin;
            int j = end;
            while (i < j) {
                while (i < j && src[j] > key) {
                    j--;
                }
                if (i < j) {
                    src[i] = src[j];
                    i++;
                }
                while (i < j && src[i] < key) {
                    i++;
                }
                if (i < j) {
                    src[j] = src[i];
                    j--;
                }
            }
            src[i] = key;
            quickSort(src, begin, i - 1);
            quickSort(src, i + 1, end);
        }
    }
}

总结

排序算法的核心思想本质其实是分治思想，把问题分为一个个的小部分来分别解决，再把结果组合起来。这题通过一个小的游标操作强行把快排拉了过来。虽然题目简单，但是能复习一下 分治算法 ，也巩固了一下快速排序，也算今天有所收获吧。

本文正在参与「掘金 2021 4 月刷题打卡」, 点击查看活动详情。

...

00:00

LeetCode每日一题--验证回文串

leetCode算法系列--分治算法

前言

题目描述

解题思路

快排代码

总结

...

标签

其他常用