package code3;

import java.util.Scanner;

/**
 * 快速排序
 *
 * @author WYF
 * @date 2020/02/06
 */
public class Main4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] a = new int[100];
        int length = 0;
        while (length < 100) {
            int temp = scanner.nextInt();
            if (temp == 0) {
                break;
            }
            a[length] = temp;
            length++;
        }
        sort(a, 0, length - 1);
        for (int i = 0; i < length; i++) {
            System.out.print(a[i] + " ");
        }

    }

    private static void sort(int[] a, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        temp = a[low];
        i = low;
        j = high;
        while (i < j) {
            while (a[j] >= temp && i < j) {
                //先比较后移动
                j--;
            }
            while (a[i] <= temp && i < j) {
                //这里好像多了一步和自己比较，但是没关系，反正也是i++ 会通过的
                i++;
            }
            if (i < j) {
                t = a[j];
                a[j] = a[i];
                a[i] = t;
            }
        }
        //核心1：上面这两个循环， 不是找一次就OK，一直找一直交换，找到i<j为止
        //核心2：循环结束了，到了考虑临界的情况，上面的i<j挺精髓的，每一步都设置了i不能大于j
        //那么 一种只有一种情况就是i==j
        if (i == j) {
            t = a[low];
            a[low] = a[i];
            a[i] = t;
        }
        //核心3 递归嘛 我干一点然后交给别人去干就行了
        sort(a, low, i - 1);
        sort(a, j + 1, high);
    }
}

//注意：
// 1.
// <=、>=和<、>的区别，可以说整个是整个算法的灵魂，如果换成<和 >
// 就是另一种快速排序了，一直拿第一个数字比较的那种，不去掉就是浪费时间效率
//2.
// int temp1 = a[low];
//        a[low] = a[j];
//        a[j] = temp1;
//是a[low] 与a[j]交换不是a[j]与temp交换
//3.
//右边的兵必须先移动，才能保证左边的是小的

2、堆排序

package code3.com.sort;

import java.util.Arrays;

/**
 * @Author: WYF
 * @Description: 构造小根堆（注意：小根堆就要先初始化大根堆，这样沉底出来才是小根堆）
 * @Create: 2020/4/2 21:02
 * @Version: 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr =  {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    private static void sort(int[] arr) {
        /** 1.构造大根堆
         *  为什么是arr.len/2-1?废话，只有arr.len/2-1才能保证他是非叶子节点
         *  注意：索引从0开始
         */
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        System.out.println(Arrays.toString(arr));
        /**
         * 2.大根堆的堆顶沉底，重新调整结构
         * i不断减小，确定的元素不断增多
         */
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            /**
             * 此处为何是0，次大的数字一定在堆顶的俩边
             */
            adjustHeap(arr, 0, i);
        }
    }


    public static void swap(int[] arr, int i, int i1) {
        int temp = arr[i];
        arr[i] = arr[i1];
        arr[i1] = temp;
    }

    /**
     * @Description: 对该节点调整，以保证该节点：根>左>右
     * 最优：取根节点为保存在temp，左右找一个大的来和temp比较，比较成功就交换，否则不变
     * @Param: [arr, i, length]
     * @Return: void
     * @Author: WYF
     * @Date: 2020/4/2 21:32
     */
    private static void adjustHeap(int[] arr, int i, int length) {
        /**这里我发现数组存放的二叉树的节点可以从0开始，也可以从1
         * 这两种对应的子节点不一样的，有个是i/2+1和i/2+2（从0开始），有个是i/2和i/2+1（从一开始）
         * 先取出当前元素i
         */
        int temp = arr[i];
        /**
         * 从i结点的左子结点开始，也就是2i+1处开始
         * 这个循环很有意义，是标志着重新调整结构，因为有可能被这么一整，顺序乱了
         */
        //多此比较 直到把temp找到一合适的位置，即调整堆结构，让它还是一个堆，不会因为头尾交换改变结构
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            /**
             * 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
             */
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        /**
         * 放回去
         */
        arr[i] = temp;
    }

}

/**
* @Author: WYF
* @Description: 归并排序
 * https://www.cnblogs.com/chengxiao/p/6194356.html
* @Create: 2020/4/29 13:37
* @Version: 1.0
*/
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }

    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left<right) {
            int mid = left+(right-left)/2;
            sort(arr,left,mid,temp);
            sort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }

}

难度中等5026

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb" 输出: 3  解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。  请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = "" 输出: 0

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
        
    }
}

看题解

1. 无重复字符的最长子串

2. k个一组翻转链表

3. 反转链表

4. top k（这个题目重点，https://leetcode-cn.com/problems/top-k-frequent-elements/，https://leetcode-cn.com/problems/smallest-k-lcci/）

5. 三数之和

6. 股票问题（有好多题目）

7. LRU

8. 两数之和

9. 相交链表

10. 背包问题（01背包、完全背包、多重背包）

JVM

jvm注意几个之点：

1、jvm5个部分是什么样的，每个部分的作用；

2、jmm模型，三个特性；

3、垃圾收集算法（比如年轻代用复制算法、老年待用什么算法）

4、双亲委派机制是什么样的？

5、 垃圾收集器有哪写？

juc等其他

1.HashMap 1.7使用数组加链表，节点是内部类Entry节点，使用的是头插法 扩容resize方法调用transfer方法，造成Entry的rehash，可能形成循环链表。 下次get得到死循环。另外，没有加锁容易造成线程不安全

1.8链表、数组加红黑树，Entry节点—》Note节点,在put的时候就行优化

1.7成链的机制， 假设两个线程执行put方法拆入节点，当一个线程要进行扩容，调用resize，resize调用transfer方法， 两个另一个线程插入了节点，造成了重新 rehash 之后链表的顺序被反转 这时候，transfer方法重新获得线程，这时候，就造成了插入的两个结点形成一个环

2.他的扩容机制？ 初始化 HaspMap，若无设置capacity，默认的容量是16， 负载因子0.75 计算一个出来一个扩容的阈值， put的时候判断，当前的size是不是大于这个阈值，大于的时候就扩容成原来两杯。

原来的Entry就行resize

3.java1.7是头插法、1.8是尾插法，1.8就安全？ 不是，只是尾插法没有改变原来的顺序，不会出现链表循环的过程

4.线程不安全 Hashtable private Hashtable<String,Object> hashtable = new Hashtable<>(); 对于Hashtable，源码里面对他的get/put方法都做了Synchronized修饰， 方法级别的阻塞，同一个时刻，只有一个线程进行get/put，效率低。

synchronizedMap private Map<String, Object> map = Collections.synchronized(new HashMap<String,Object>); 用工具类将HashMap封装，SynchronizedMap的实现方式是加了个！对象锁！，每次对HashMap的操作都要先获取这个mutex的对象锁才能进入，所以性能也不会比HashTable好到哪里去，也不建议使用。

coucurrentHashMap 推荐使用， 在jdk8之前是使用分段加锁的一个方式，分成16个桶，每次只加锁其中一个桶，而在jdk8又加入了红黑树和CAS算法来实现。 每次只会锁目前一个segment，用synchronized+CAS，效率更高了，并发度更高。

5.锁升级： 无锁 偏向，获取这个锁的线程，优先再去获取这个锁 获取不到-> 轻量级、乐观锁CAS 获取不到， 进行自旋，到底一定程度 synchronized

6.事务隔离级别：未提交读、读已提交，可重复读、串行化

7.AOP实现方式： 动态代理 JDK的proxy 接口类，没有接口就不太合适 cglib 生成目标类的子类，然后去实现代理 性能：cglib在创建的时候慢，运行的时候快