java实现快速排序&最长子字符串

快速排序

简述

快速排序是一种排序执行效率很高的排序算法，它利用分治法来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序，下面我们简单进行阐述。

先用例子理解快排的实现思路

比如对 4,1,8,5,3,2,9,10,6,7 这10个数字进行排序，

1.对第一个数字4排序，这里先想一下，当我们把4排好序后它左边的数字应该都比它小，而且它右边的数字应该都比它大，做到这样后4这个数字的位置就排好了。那怎么达到这样的效果呢？

第一步：我们先从数组的右边开始循环，跟4比较大小，如果比4小，那就和4交换位置，循环过程如下：

7>4，不交换

6>4，不交换

10>4，不交换

9>4，不交换

2<4，交换，4和2交换后数组变 2,1,8,5,3,4,9,10,6,7，此次循环到了数组下标为5的位置

第二步：从数组的左边开始循环，跟4比较大小，如果比4大，那就和4交换位置，循环过程如下：

2<4，不交换

1<4，不交换

8>4，交换，8和4交换后数组变为 2,1,4,5,3,8,9,10,6,7，此次循环到了数组下标为2的位置

第三步：这里注意，要左右两边同时循环和4比较大小，直到两边循环相遇。第一步从右向左循环到了下标为5（当前对应数字8）的位置，继续循环过程如下：

3<4，交换，3和4交换后数组变为 2,1,3,5,4,8,9,10,6,7，此次循环到了数组下标为4的位置

第四步：第二步从左向右循环到了下标为2（当前对应数字3）的位置，继续循环过程如下：

5>4，交换，5和4交换后数组变为2,1,3,4,5,8,9,10,6,7，此次循环到了数组下标为3的位置，上一步从右向左也循环到了下标为4的位置，已经相遇了。到此4也已经放到正确的位置了，次轮循环结束。

但是4左边的2,1,3和右边的5,8,9,10,6,7还是乱序的，所以继续对两边的数字重复上面的步骤。

2.对数组的前3个元素2,1,3排序，首先对第一个数字2排序，过程如下：

第一步：从右向左循环和2比较大小

3>2，不交换

1<2，交换，1和2交换后变为1,2,3，此次循环到了数组下标为1的位置，排序已经完成。

3.对数组的后6个元素5,8,9,10,6,7排序，首先对第一个数字5排序，5已经在正确位置上，再继续对后面的5个元素重复上面的步骤循环排序。

用Java实现快排

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 1, 8, 5, 3, 2, 9, 10, 6, 7};
        quickSort(arr, 0, 9);
        // 打印
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }

    /**
     * 递归循环实现快排
     *
     * @param arr        数组
     * @param startIndex 快排的开始下标
     * @param endIndex   快排的结束下标
     */
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (arr == null || arr.length == 0) {
            return;
        }

        int start = startIndex, end = endIndex;
        //target是本次循环要排序的元素，每次循环都是确定一个元素的排序位置，这个元素都是开始下标对应的元素
        int target = arr[startIndex];
        //开始循环，从两头往中间循环，相遇后循环结束
        while (start < end) {
            //从右向左循环比较，如果比target小，就和target交换位置，让所有比target小的元素到target的左边去
            while (start < end) {
                if (arr[end] < target) {
                    swap(arr, start, end);
                    break;
                }
                end--;
            }

            //从左向右循环比较，如果比target大，就和target交换位置，让所有比target大的元素到target的右边去
            while (start < end) {
                if (arr[start] > target) {
                    swap(arr, start, end);
                    break;
                }
                start++;
            }
        }
        //确定target的排序后，如果target左边还有元素，继续递归排序
        if ((start - 1) > startIndex) {
            quickSort(arr, startIndex, start - 1);
        }
        //确定target的排序后，如果target右边还有元素，继续递归排序
        if ((end + 1) < endIndex) {
            quickSort(arr, end + 1, endIndex);
        }
    }

    /**
     * 根据下标交换数组的两个元素
     *
     * @param arr    数组
     * @param index1 下标1
     * @param index2 下标2
     */
    public static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

运行结果：

1,2,3,4,5,6,7,8,9,10,

无重复字符的最长子串

参考：https://www.cnblogs.com/ariel-dreamland/p/8668286.html
题目描述：
给定一个字符串，找出不含有重复字符的 最长子串 的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

方法一：暴力法

直觉
逐个检查所有的字符串，看它是否不含有重复的字符。

算法
假设我们有一个函数boolean allUnique(String substring) ，如果子字符串中的字符都是唯一的，它会返回true，否则会返回false。 我们可以遍历给定字符串s的所有可能的子字符串并调用函数allUnique。 如果事实证明返回值为true，那么我们将会更新无重复字符子串的最大长度的答案。

现在让我们填补缺少的部分：
为了枚举给定字符串的所有子字符串，我们需要枚举它们开始和结束的索引。假设开始和结束的索引分别为 i 和 j。那么我们有 0≤i<j≤n （这里的结束索引 j 是按惯例排除的）。因此，使用 i从0到 n - n−1 以及 j 从 i+1到 n这两个嵌套的循环，我们可以枚举出s的所有子字符串。

要检查一个字符串是否有重复字符，我们可以使用集合。我们遍历字符串中的所有字符，并将它们逐个放入set中。在放置一个字符之前，我们检查该集合是否已经包含它。如果包含，我们会返回false。循环结束后，我们返回true。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

方法二：滑动窗口

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)向右滑动 1 个元素，则它将变为 [i+1,j+1)（左闭，右开）。

回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i,j)（最初 j=i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 jj。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。

public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
}