JAVA 算法 （中）

part 3

多数元素

	public int majorityElement(int [] nums){
        //对接消耗的数字
        int currentNum = nums[0];
        //对接消耗的数字个数
        int count =1;
        for (int i = 0; i < nums.length; i++) {
            if (count==0) {
                //对接消耗的数字设置为当前元素
                currentNum=nums[i];
                count=1;
            }else {
                if (nums[i]==currentNum){
                    //对接消耗的数字个数增加
                    count++;
                }else {
                    //数字不等，兑子，对拼消耗的数字个数减一
                    count--;
                }
            }
        }
        return currentNum;
    }

盛最多水的容器

不属于热点面试题

	public int maxArea(int [] height){
        int i =0;
        int j = height.length-1;
        int maxWater = 0;
        while (i<j){
            //height[i] 和 height[j],谁小就移动谁
            maxWater = height[i]<height[j]?
            Math.max(maxWater,(j-i)*height[i++]):
            Math.max(maxWater,(j-i)*height[j--]);
        }
        return maxWater;
    }

三数之和

 	/*暴力求解：排序+三重循环*/
    public List<List<Integer>> threeSum3Loop(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        if(nums.length < 3) return results; //长度小于3,就不存在三数之和了
        //排序
        Arrays.sort(nums);
        //如果第一个数就大于0，那就没必要再查找下去了
        if(nums[0] > 0) return results;
        for(int i = 0; i < nums.length - 2; i++){
            int x = nums[i];
            if(x > 0) break;
            //去重，假如给的用例是[0, 0, 0, 0],当i第一次遇到0时，为首次遇见没有关系，可如果这次i的循环结束了
            //i+1进入第二次循环，那么这时候还是遇到0，为连续的第二次遇见，这就造成了前后重复，必须要跳过
            if(i > 0 && nums[i - 1] == nums[i]) continue;
            for(int j = i + 1; j < nums.length - 1; j++){
                int y = nums[j];
                //去重原理同i
                if(j > i + 1 && nums[j - 1] == nums[j]) continue;
                for(int k = j + 1; k < nums.length; k++){
                    int z = nums[k];
                    if(k > j + 1 && nums[k - 1] == nums[k]) continue;  //去重原理同j
                    if(x + y + z == 0){
                        List<Integer> list = new LinkedList<Integer>();
                        list.add(x);
                        list.add(y);
                        list.add(z);
                        results.add(list);
                    }
                }
            }
        }
        return results;
    }

    /*排序 + 两重循环 + HashMap*/
    public List<List<Integer>> threeSumWithMap(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        if(nums.length < 3) return results; //长度小于3,就不存在三数之和了
        //排序
        Arrays.sort(nums);
        //如果第一个数就大于0，那就没必要再查找下去了
        if(nums[0] > 0) return results;
        //用一个HashMap将所有的元素加进去，这里的keys是nums[i]，value是i
        //如果出现重复的key,那么新出现的value将会覆盖前面的一个value，
        // 用这个map来替代第三重循环
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        for(int i = 0; i < nums.length - 2; i++){
            int x = nums[i];
            //如果第一个数就大于0，那就没必要再查找下去了
            if(x > 0) break;
            //去重
            if(i > 0 && nums[i - 1] == nums[i]) continue;
            for(int j = i + 1; j < nums.length - 1; j++){
                int y = nums[j];
                if(x + y > 0) break;
                //去重
                if(j > i + 1 && nums[j - 1] == nums[j]) continue;
                //z为组合需要的那个值
                int z = 0 - x - y;
                //如果map集合里面有这个值，最重要的是要判断它的value（序号）是不是在i和j的后面
                //因为之前的第三重for循环的k是从j + 1开始的，所以它一定会大于j
                if(map.containsKey(z) && map.get(z) > j){
                    List<Integer> list = new LinkedList<Integer>();
                    list.add(x);
                    list.add(y);
                    list.add(z);
                    results.add(list);
                }
            }
        }
        return results;
    }

    /*排序 + 双指针解法*/
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        if(nums.length < 3) return results; //长度小于3,就不存在三数之和了
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            //如果第一个数就大于0，那就没必要再查找下去了
            if (nums[i] > 0) break;
            int head = i + 1, tail = n - 1;
            //head指针和tail指针相对而行，但必须保证head在tail的左边
            while (head < tail) {
                //三数之和有三种情况：大于0，小于0，等于0
                int sum = nums[i] + nums[head] + nums[tail];
                if (sum < 0) head++; //三数之和小于0，左边head的那个数太小了，要把它向右移
                else if (sum > 0) tail--;//三数之和大于0，tail坐标的那个数太大了，要把它向左移
                else {
                    //三数之和等于0，添加到返回列表里面，并且同时将左指针右移，右指针左移，探索下一组适合的数据
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[i]);
                    list.add(nums[head]);
                    list.add(nums[tail]);
                    results.add(list);
                    //去重
                    while (head+1 <= tail && nums[head] == nums[head+1]) head++;
                    while (head+1 <= tail && nums[tail] == nums[tail-1]) tail--;
                    head++;
                    tail--;
                }
            }
            //去重
            while (i+1 < n && nums[i+1] == nums[i]) i++;
        }
        return results;
    }

下一个排列

/**
 * @description ：(LeetCode-31) 下一个排列
 * 实现获取 下一个排列 的函数，
 * 算法需要将给定数字序列重新排列成字典序中下一个更大的排列
 * （即，组合出下一个更大的整数）。
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * 必须 原地 修改，只允许使用额外常数空间。
 */
public class NextPermutation_31 {

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        /*找到数组中的“小数”，退出循环就说明nums[i] < nums[i + 1]*/
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            /*找到数组中的尽可能小的“大数，退出循环就说明nums[i] < nums[j]”*/
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            /*交换“小数”和“大数”的位置*/
            swap(nums, i, j);
        }
        /*将“大数”后面的所有数重置为升序*/
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] nums1  = {5,3,1,6,2,4};
        int[] nums2  = {1,2,3,4,5,6};
        new NextPermutation_31().nextPermutation(nums1);
    }

}

旋转图像

	public void rotate(int[][] matrix) {
        if(matrix.length == 0 || matrix.length != matrix[0].length) {
            return;
        }
        int maxIndex = matrix.length - 1;
        /*先沿右上 - 左下的对角线镜像翻转*/
        for (int x = 0; x <= maxIndex; ++x){
            for (int y = 0; y <= maxIndex - x; ++y){
                int temp = matrix[x][y];
                matrix[x][y] = matrix[maxIndex - y][maxIndex - x];
                matrix[maxIndex - y][maxIndex - x] = temp;
            }
        }
        /*再沿水平中线上下翻转*/
        for (int i = 0; i <= (maxIndex >> 1); ++i){
            for (int j = 0; j <= maxIndex; ++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[maxIndex - i][j];
                matrix[maxIndex - i][j] = temp;
            }
        }
    }

螺旋矩阵

	 public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0)
            return list;
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        int plies = 0;/*层数指示器*/

        /*获得矩阵的层数*/
        int count = (Math.min(rowLength, colLength)+1)/2;
        /*从外部向内部遍历，逐层打印数据*/
        while(plies < count) {
            /*每层矩阵的起始元素都是matrix[plies][plies]*/
            /*从左至右，到matrix[plies][colLength-1-plies]时停止，准备转向*/
            for (int j = plies; j < colLength-plies; j++) {
                list.add(matrix[plies][j]);
            }
            /*从上往下，本列的第一个元素已经在上面的“从左至右”中处理了，
            * 所以行从应该从plies+1开始，列(colLength-1-plies)维持不变，
            * 起始元素就是matrix[plies+1][colLength-1-plies]，
            * 到matrix[rowLength-1-plies][colLength-1-plies]时停止，准备转向*/
            for (int j = plies+1; j < rowLength-plies; j++) {
                list.add(matrix[j][(colLength-1)-plies]);
            }
            /*从右往左，本行的第一个元素已经在上面的“从上往下”中处理了，
            * 所以列应该从(colLength-1-plies)-1开始，行维持不变，
            * 起始元素就是matrix[rowLength-1-plies][(colLength-1-plies)-1]，
            * 到matrix[rowLength-1-plies][plies]时停止，准备转向*/
            /*rowLength-1-plies == plies，表示本层只有单行，不必再处理*/
            for (int j = (colLength-1)-(plies+1); j >= plies && (rowLength-1-plies != plies); j--) {
                list.add(matrix[(rowLength-1)-plies][j]);
            }
            /*从下往上，本列的第一个元素已经在上面的“从右往左”中处理了，
             * 所以行从应该从(rowLength-1-plies)-1开始，列(plies)维持不变，
             * 起始元素就是matrix[(rowLength-1-plies)-1][plies]，
             * 到matrix[plies+1][plies]时停止*/
            /*colLength-1-plies != plies，表示本层只有单列，不必再处理*/
            for (int j = (rowLength-1)-(plies+1); j >= plies+1 && (colLength-1-plies != plies); j--) {
                list.add(matrix[j][plies]);
            }
            plies++; /*层数累加*/
        }
        return list;
    }

跳跃游戏

	public boolean canJump(int[] nums) {
        if(nums.length < 2) return true;
        /*从倒数第二个元素开始倒序往前找*/
        for(int curr = nums.length-2; curr>=0;curr--){
            if(nums[curr] == 0){
                /*如果存在当前元素=0的情况，需要找到可以跳过这个0的数组元素值*/
                int neededJumps = 1;
                while(neededJumps > nums[curr]){
                    /*要记得，每倒序往前走一个元素，需要跳过的数值也要加1*/
                    neededJumps++;
                    curr--;
                    if(curr < 0) return false;
                }
            }
        }
        return true;
    }

    /*基于动态规划的实现*/
    public boolean canJumpWithDP(int[] nums) {
        int n=nums.length;
        int maxStep=nums[0];
        for(int i=1;i<n;i++){
            if(maxStep==0)  return false;
            maxStep=Math.max(maxStep-1,nums[i]);
        }
        return true;
    }

数组中的第K个最大元素

这道题是面试的高频考题，同时也是基础排序算法的应用。
仔细分析题目，需要找的是数组排序后的第 k 个最大的元素，所以最简单的办法，首先把数组排序后，返回第 k 个最大的元素就行了。

	 //基于JDK中sort方法实现
	 /*数组排序后，直接返回第 k 个元素*/
    public int findKthLargest(int[] nums, int k) {
        final int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
    }

	 /*基于快速排序的分区实现*/
    public int findKthLargest(int[] nums, int k) {
        if (nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        // 转换一下，第 k 大元素的下标是 len - k
        int target = len - k;

        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }

    /**
     * 快速排序分区方法
     */
    public int partition(int[] array, int start, int end) {
        /*只有一个元素时，无需再分区*/
        if(start == end) return start;
        /*随机选取一个基准数*/
        int pivot = (int) (start + Math.random() * (end - start + 1));
        /*zoneIndex是分区指示器，初始值为分区头元素下标减一*/
        int zoneIndex = start - 1;
        /*将基准数和分区尾元素交换位置*/
        swap(array, pivot, end);
        for (int i = start; i <= end; i++){
            /*当前元素小于等于基准数*/
            if (array[i] <= array[end]) {
                /*首先分区指示器累加*/
                zoneIndex++;
                /*当前元素在分区指示器的右边时，交换当前元素和分区指示器元素*/
                if (i > zoneIndex)
                    swap(array, i, zoneIndex);
            }
        }
        return zoneIndex;
    }

    /**
     * 交换数组内两个元素
     */
    public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

	//堆排序方式
    /* 直接利用JDK中的优先队列来实现堆排序，进而实现题目的要求
     * JDK中的优先队列默认是最小堆，最大堆需要自行实现Comparator*/
    public int findKthLargestWithPQ(int[] nums, int k) {
        /*使用一个含有 k 个元素的最小堆*/
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            pq.add(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            /*获取但并不弹出栈顶元素*/
            /*当前遍历的元素比堆顶元素大，当前元素替换栈顶元素*/
            if (nums[i] > pq.peek()) {
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        return pq.peek();
    }

    /*利用最大堆实现本题要求*/
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        /*1.构建一个最大堆*/
        buildMaxHeap(nums,len);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --len;
            adjustHeap(nums, 0,len);
        }
        return nums[0];
    }

    /* 建立最大堆*/
    public void buildMaxHeap(int[] array, int heapSize) {
        /*从最后一个非叶子节点开始向上构造最大堆*/
        for (int i = (heapSize/2-1); i >= 0; i--) {
            adjustHeap(array, i,heapSize);
        }
    }

    /* 调整使之成为最大堆*/
    public void adjustHeap(int[] array, int i, int heapSize) {
        int maxIndex = i;
        int left = 2*i+1;
        int right = 2*(i+1);
        /*如果有左子树，且左子树大于父节点，则将最大指针指向左子树*/
        if (left < heapSize && array[left] > array[maxIndex])
            maxIndex = left;
        /*如果有右子树，且右子树大于父节点且大于左子树，则将最大指针指向右子树*/
        if (right < heapSize && array[right] > array[maxIndex]&&array[right]>array[left])
            maxIndex = right;
        /*如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。*/
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex,heapSize);
        }
    }

    /* 交换数组内两个元素*/
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

前 K 个高频元素

 /*LeetCode官方解法
    直接利用JDK中的优先队列来实现堆排序，进而实现题目的要求
     * 这里需要自行实现Comparator*/
    public int[] topKFrequentWithPQ(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        /*每个放进优先队列的数组int[]只有两个元素，
        第一个元素代表数组的值，第二个元素代表了该值出现的次数**/
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(k,(a,b)->(a[1]-b[1]));
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            int count = entry.getValue();
            if (minHeap.size() == k) {
                if (minHeap.peek()[1] < count) {
                    minHeap.poll();
                    minHeap.offer(new int[]{entry.getKey(), count});
                }
            }else{
                minHeap.offer(new int[]{entry.getKey(), count});
            }
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = minHeap.poll()[0];
        }
        return ret;
    }

寻找两个正序数组的中位数

	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        /*将数组元素个数总数为奇数和偶数情况统一处理
        * 奇数个数: left==right
        * 偶数个数: right==left+1
        * 比如 m=4,n=6,则left = 5,right = 6
        * m=4,n=5,则left = 5,right = 5 */
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (getkth(nums1, 0, nums2, 0, left)
                + getkth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    public double getkth(int[] nums1, int nums1Start, int[] nums2, int nums2Start, int k) {
        /*有任何一个数组空了，直接返回另外一个非空数组的中位数结果*/
        if (nums1Start > nums1.length - 1)
            return nums2[nums2Start + k - 1];
        if (nums2Start > nums2.length - 1)
            return nums1[nums1Start + k - 1];
        /*找第1小的数字，所以只需判断两个数组中第一个数字哪个小就可以了*/
        if (k == 1)
            return Math.min(nums1[nums1Start], nums2[nums2Start]);
        /*获得两个数组中第k/2个元素的值*/
        int num1Mid = Integer.MAX_VALUE, num2Mid = Integer.MAX_VALUE;
        if (nums1Start + k/2 - 1 < nums1.length)
            num1Mid = nums1[nums1Start + k/2 - 1];
        if (nums2Start + k/2 - 1 < nums2.length)
            num2Mid = nums2[nums2Start + k/2 - 1];

        /*比较两值的大小，然后以递归的形式继续更小数组的处理*/
        if (num1Mid < num2Mid)
            /*num1Mid更小，排除num1[]中小于等于num1Mid的部分*/
            return getkth(nums1, nums1Start + k/2,
                    nums2, nums2Start,k - k/2);
        else
            /*num2Mid更小，排除num2[]中小于等于num2Mid的部分*/
            return getkth(nums1, nums1Start, nums2,
                    nums2Start + k/2, k - k/2);
    }

链表类

两数相加

	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode p, dummy = new ListNode(0);
        p = dummy;
        while (l1 != null || l2 != null || carry != 0) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            p.next = new ListNode(carry%10);
            carry /= 10;
            p = p.next;
        }
        return dummy.next;
    }

删除链表的倒数第 N 个结点

	 public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        slow.next = head;

        /*先移动快指针n步*/
        for(int i=1; i<=n+1; i++)   {
            fast = fast.next;
        }
        /*同时移动快慢指针*/
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        /*去除不要的第N个结点*/
        slow.next = slow.next.next;
        return start.next;
    }

反转链表 II

	public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode preNode = dummy;
        /*将preNode移动left-1步
        *preNode的next就是反转的开始 */
        for(int i = 0; i<left-1; i++) preNode = preNode.next;

        /*要反转的链表结点就是preNode的下个结点*/
        ListNode startNode = preNode.next;
        /*同时记录要反转的下一个结点*/
        ListNode nextNode = startNode.next;

        for(int i=0; i<right-left; i++) {
            startNode.next = nextNode.next;
            nextNode.next = preNode.next;
            preNode.next = nextNode;
            nextNode = startNode.next;
        }
        return dummy.next;
    }

重排链表

/**
 * @description ：(LeetCode-143) 重排链表
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *  L0 → L1 → … → Ln-1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */
	public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;

        /*寻找链表的中间结点，和876不同
        这里如果结点数是偶数个，
        返回的是中间结点的第一个结点*/
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }

        /*反转后半部分链表*/
        ListNode preMiddle=slow;
        ListNode preCurrent=slow.next;
        while(preCurrent.next!=null){
            ListNode current=preCurrent.next;
            preCurrent.next=current.next;
            current.next=preMiddle.next;
            preMiddle.next=current;
        }

        /*“梅花间隔”的形式将反转后的链表插入到前半部分链表*/
        slow=head;
        fast=preMiddle.next;
        while(slow!=preMiddle){
            preMiddle.next=fast.next;
            fast.next=slow.next;
            slow.next=fast;
            slow=fast.next;
            fast=preMiddle.next;
        }
    }

LRU 缓存机制

/**
 * @description ：(LeetCode-146) LRU 缓存机制
 * 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字已经存在，则变更其数据值；
 * 如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，
 * 它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 */
public class LRUCache {

    /*双向链表的结点定义，凡是使用过的结点都会移动到链表的头部*/
    class LinkedNode {
        int key;
        int value;
        LinkedNode pre;
        LinkedNode next;
    }

    /*头插法插入结点*/
    private void addNode(LinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    /*将结点从链表摘除*/
    private void removeNode(LinkedNode node){
        LinkedNode pre = node.pre;
        LinkedNode post = node.next;
        pre.next = post;
        post.pre = pre;
    }

    /*将结点移动到头部*/
    private void moveToHead(LinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }

    /*移除尾部结点*/
    private LinkedNode removeTail(){
        LinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }

    private HashMap<Integer, LinkedNode> cache = new HashMap<Integer, LinkedNode>();
    /*链表的头尾指针结点，不存放实际业务数据*/
    private LinkedNode head, tail;

    public LRUCache(int capacity) {
        head = new LinkedNode();
        /*用head结点的key存放容量
        * value存放当前链表中结点的实际数量*/
        head.key = capacity;
        head.value = 0;
        head.pre = null;
        tail = new LinkedNode();
        tail.next = null;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        LinkedNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        /*结点被使用了，移动到头部*/
        this.moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        LinkedNode node = cache.get(key);
        if(node == null){
            LinkedNode newNode = new LinkedNode();
            newNode.key = key;
            newNode.value = value;
            this.cache.put(key, newNode);
            this.addNode(newNode);
            ++head.value;
            if(head.value > head.key){
                /*超出了容量限制，移除尾部结点*/
                LinkedNode tail = this.removeTail();
                this.cache.remove(tail.key);
                --head.value;
            }
        }else{
            /*更新结点数据，并移动到头部*/
            node.value = value;
            this.moveToHead(node);
        }
    }
}

合并K个升序链表

	public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1;
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    /*循环+双指针解决两个链表的合并
    * 代码来自(LeetCode-21)合并两个有序链表
    * MergeTwoSortLists_21.java*/
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode resultNode  = new ListNode(0);
        ListNode p = resultNode ;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1 != null)
            p.next = l1;
        if(l2 != null)
            p.next = l2;
        return resultNode.next;
    }

    /*使用堆排序的思想来实现，利用了JDK中的优先队列*/
    public ListNode mergeKListsWithPQ(ListNode[] lists) {
        if (lists==null||lists.length==0) return null;

        PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1,ListNode o2){
                if (o1.val<o2.val)
                    return -1;
                else if (o1.val==o2.val)
                    return 0;
                else
                    return 1;
            }
        });

        /*dummy用以返回结果链表
        *tail用以获得堆顶元素并合并链表*/
        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;

        /*首先将所有链表的首节点放入队列，进行初始化*/
        for (ListNode node:lists)
            if (node!=null)
                queue.add(node);

        while (!queue.isEmpty()){
            /*将堆顶的元素放入结果链表*/
            tail.next=queue.poll();
            tail=tail.next;
            /*将堆顶的元素的下一个结点放入队列*/
            if (tail.next!=null)
                queue.add(tail.next);
        }
        return dummy.next;
    }

K 个一组翻转链表

/**
 * @description ：(LeetCode-25) K 个一组翻转链表
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 */
public class ReverseNodesInKGroup_25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode begin;
        if (head==null || head.next ==null || k==1)
            return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        begin = dummy;
        int i=0;
        while (head != null){
            i++;
            if (i%k == 0){
                begin = reverse(begin, head.next);
                head = begin.next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }

    /*反转链表结点的方法*/
    public ListNode reverse(ListNode preSubList, ListNode subListNext){
        ListNode startNode = preSubList.next;
        ListNode nextNode = startNode.next;
        ListNode inPreNode = preSubList;
        while(startNode.next != subListNext){
            startNode.next = nextNode.next;
            nextNode.next = inPreNode.next;
            inPreNode.next = nextNode;
            nextNode = startNode.next;
        }
        return startNode;
    }
}

part4

栈与队列

每日温度

	/**
	 * @description ：(LeetCode-739) 每日温度
	 * 请根据每日气温列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。
	 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
	 */

	/*标准栈的解法*/
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new LinkedList<Integer>();;
        int[] ret = new int[temperatures.length];
        for(int i = 0; i < temperatures.length; i++) {
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                ret[idx] = i - idx;
            }
            stack.push(i);
        }
        return ret;
    }

    /*用倒序遍历数组来求解*/
    public int[] dailyTemperaturesUseArray(int[] temperatures) {
        int length = temperatures.length;
        int[] ret = new int[length];

        /*从右向左遍历，数组最后一个元素无需处理*/
        for (int i = length - 2; i >= 0; i--) {
            /*backIdx表示从当前元素开始往后寻找获得需要的结果，
            backIdx=backIdx+ret[backIdx]是为了利用已经有的结果进行跳跃*/
            for (int backIdx = i + 1; backIdx < length; backIdx=backIdx+ret[backIdx]) {
                if (temperatures[backIdx] > temperatures[i]) {
                    ret[i] = backIdx - i;
                    break;
                } else if (ret[backIdx] == 0) {/*遇到0表示后面不会有更大的值，那当然当前值就应该也为0*/
                    ret[i] = 0;
                    break;
                }
            }
        }
        return ret;
    }

柱状图中最大的矩形

	/**
	 * @description ：(LeetCode-84) 柱状图中最大的矩形
	 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
	 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
	 */
	 /*基于单调栈的实现*/
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }

        int result = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        /*遍历数组*/
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                /*当前需要计算面积的元素的下标*/
                int curIndex = stack.pollLast();
                /*获得当前元素的值，也就是矩形的高*/
                int curHeight = heights[curIndex];
                /*计算矩形的宽*/
                int curWidth;
                if (stack.isEmpty()) {
                    /*栈为空，表示目前遍历过所有元素都比当前的i要大，i是最小的一个，
                    宽度就可以直接取i的值*/
                    curWidth = i;
                } else {
                    curWidth = i - stack.peekLast() - 1;
                }
                result = Math.max(result, curHeight * curWidth);
            }
            stack.addLast(i);
        }

        /*处理目前还在栈中的元素*/
        while (!stack.isEmpty()) {
            int curHeight = heights[stack.pollLast()];
            int curWidth;
            if (stack.isEmpty()) {
                curWidth = len;
            } else {
                curWidth = len - stack.peekLast() - 1;
            }
            result = Math.max(result, curHeight * curWidth);
        }
        return result;
    }

    /*基于单调栈+哨兵的实现*/
    public int largestRectangleAreaWithSentinel(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        int result = 0;

        int[] heightsWithSentinel = new int[len + 2];
        /*头哨兵，不会大于输入数组里任何一个元素，它肯定不会出栈，因此栈一定不会为空*/
        heightsWithSentinel[0] = 0;
        System.arraycopy(heights, 0, heightsWithSentinel, 1, len);
        /*尾哨兵，它不会大于输入数组里任何一个元素，
        它会让所有输入数组里的元素出栈（头边的哨兵元素除外）*/
        heightsWithSentinel[len + 1] = 0;
        len += 2;
        heights = heightsWithSentinel;

        Deque<Integer> stack = new LinkedList<Integer>();
        /*先放入头哨兵，在循环里就不用做非空判断*/
        stack.addLast(0);

        for (int i = 1; i < len; i++) {
            while (heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast() - 1;
                result = Math.max(result, curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return result;
    }

    /*基于数组的实现*/
    public int largestRectangleAreaWithArray(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        /*存放元素右侧和左侧仅次于当前元素高度（或相同高度）的邻居元素下标的数组*/
        int[] leftLower = new int[heights.length];
        int[] rightLower = new int[heights.length];
        /*初始化*/
        rightLower[heights.length - 1] = heights.length;
        leftLower[0] = -1;

        /*正序遍历，对当前元素寻找左侧第一个小于当前元素高度（或相同高度）的邻居元素*/
        for (int i = 1; i < heights.length; i++) {
            /*从当前元素左侧第一个邻居元素开始，往左侧寻找*/
            int neighbourLeft  = i - 1;
            /*不断的往左寻找,一直到数组头或者左侧第一个小于等于当前元素的邻居元素为止*/
            while (neighbourLeft >= 0 && heights[neighbourLeft] >= heights[i]) {
                /*在我们的遍历过程中，当前元素的所有左侧元素我们已经处理过了，
                那就是说我们可以重用先前计算的结果快速跳转，比如数组
                {3,6,5,7,4,8,1,0}，
                假如当前元素是下标为4的元素4，很明显，前面的3,6,5,7都已经处理过,
                leftLower=
                [-1, 0, 0, 2, 0, 0, 0, 0],
                7会被5卡住，5和6都会被3卡住，4比7、5、6都小，
                可以快速到达5或6被卡住的地方判断4会不会也被卡住，
                neighbourLeft的变化将是 (4-1)3-->2=leftLower[3]-->0=leftLower[2]
                而heights[0]<heights[4]，退出循环，最终leftLower[4]=0*/
                neighbourLeft  = leftLower[neighbourLeft];
            }
            leftLower[i] = neighbourLeft ;
        }

        /*逆序遍历，对当前元素寻找右侧第一个小于当前元素高度（或相同高度）的邻居元素
        * 思想和上面的正序遍历一样，请自行分析*/
        for (int i = heights.length - 2; i >= 0; i--) {
            int neighbourRight = i + 1;
            while (neighbourRight < heights.length && heights[neighbourRight] >= heights[i]) {
                neighbourRight = rightLower[neighbourRight];
            }
            rightLower[i] = neighbourRight;
        }

        /*已经找到了所有元素对应的邻居元素，寻找最大的那个*/
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (rightLower[i] - leftLower[i] - 1));
        }
        return maxArea;
    }

基本计算器

	/**
	 * @description ：(LeetCode-224) 基本计算器
	 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
	 * 示例 1：
	 * 输入：s = "1 + 1"
	 * 输出：2
	 */
	 public int calculate(String s) {
        /*存放当前的计算结果*/
        int result = 0;
        /*存放当前待计算数字*/
        int num = 0;
        /*符号，加号(+1)或者减号(-1)*/
        int sign = 1;
        Deque<Integer> stack = new LinkedList<Integer>();

        char[] chars = s.toCharArray();
        int len = chars.length;

        for (int i = 0; i < len; i++) {
            char c = chars[i];
            /*如果当前字符为' '，无需处理*/
            if (c == ' ') {
                continue;
            }
            /*如果当前字符是一个数字，则用num进行记录，当然需要考虑到数字不止一位
            所以 num = num * 10 + c - '0'*/
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
                /*判断当前数字是否已经取完，只要后续字符在'0'到'9'之间，说明当前数字还未结束*/
                if (i < len - 1 && '0' <= chars[i + 1] && chars[i + 1] <= '9') {
                    continue;
                }
            /*如果当前字符为计算符号*/
            } else if (c == '+' || c == '-') {
                num = 0;
                sign = c == '+' ? 1 : -1;
            /*如果当前符号为'('，需要将前面的计算结果和符号入栈*/
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            /*如果当前符号为')'，括号里的表达式已经计算完成了，
            可以和括号外的结果进行合并计算了*/
            } else if (c == ')') {
                /*计算符号出栈*/
                sign = stack.pop();
                /*将num替换为括号中的计算结果*/
                num = result;
                /*将result替换为括号前边的计算结果*/
                result = stack.pop();
            }
            /*每循环一次，得到一个新的结果*/
            result += sign * num;
        }
        return result;
    }

树

验证二叉搜索树

/**
 * @description ：(LeetCode-98) 验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 有效 二叉搜索树定义如下：
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 */

    /*基于二叉搜索树定义/性质实现*/
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        /*要么根节点本身为null，要么递归到了叶子节点，所以同时也是递归终止条件*/
        if (root == null) return true;
        /*节点不满足二叉搜索树定义，直接返回false*/
        if (root.val >= maxVal || root.val <= minVal) return false;
        /*对当前节点下的左右子树递归去判断，变化左子树的最大范围和右子树的最小范围*/
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }

    /*基于中序遍历的栈实现*/
    public boolean isValidBSTInOrderWithStack(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        /*用来存储前一个节点的值*/
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            /*如果当前节点的值不大于前一个节点的值，不符合二叉搜索树定义*/
            if(pre != null && root.val <= pre.val) return false;
            pre = root;
            root = root.right;
        }
        return true;
    }

    TreeNode pre=null;
    /*基于中序遍历的递归实现*/
    public boolean isValidBSTInOrder(TreeNode root) {
        if(root==null) return true;
        if(!isValidBST(root.left))
            return false;
        /*这里用于判断是不是找到最左边的节点了，如果是就不用比较*/
        if(pre==null)
            pre=root;
        /*如果不是就比较这个节点和前一个节点的值*/
        else if(root.val<=pre.val)
            return false;
        pre=root;
        return isValidBST(root.right);
    }

二叉树的层序遍历

/**
 * @description ：(LeetCode-102) 二叉树的层序遍历
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。
 * （即逐层地，从左到右访问所有节点）。
 */
    /*基于队列的实现*/
    public List<List<Integer>> levelOrderWithQueue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> result = new LinkedList<List<Integer>>();

        if(root == null) return result;

        /*放入根结点*/
        queue.offer(root);
        while(!queue.isEmpty()){
            /*获得每层的节点数*/
            int levelNodeNum = queue.size();
            /*每层的结果集*/
            List<Integer> subList = new LinkedList<Integer>();
            /*处理本层的节点，包括输出节点值和将节点的左右子树入队*/
            for(int i=0; i<levelNodeNum; i++) {
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            result.add(subList);
        }
        return result;
    }

    /*基于递归的实现*/
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        levelPreVisit(result, root, 0);
        return result;
    }

    public void levelPreVisit(List<List<Integer>> result, TreeNode root, int height) {
        if (root == null) return;
        /*新的层需要增加新的子List*/
        if (height >= result.size()) {
            result.add(new LinkedList<Integer>());
        }
        /*对当前结点的处理需要注意所在的层*/
        result.get(height).add(root.val);
        levelPreVisit(result, root.left, height+1);
        levelPreVisit(result, root.right, height+1);
    }

二叉树的锯齿形层序遍历

/**
 * @description ：(LeetCode-103) 二叉树的锯齿形层序遍历
 * 给定一个二叉树，返回其节点值的锯齿形层序遍历。
 * （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root)
    {
        List<List<Integer>> sol = new ArrayList<>();
        travel(root, sol, 0);
        return sol;
    }

    private void travel(TreeNode root, List<List<Integer>> result, int height){
        if(root == null) return;

        /*新的层需要增加新的子List*/
        if (height >= result.size()) {
            result.add(new LinkedList<Integer>());
        }

        List<Integer> subList  = result.get(height);
        /*因为要锯齿形层序遍历，所以对层高需要进行判断
        * 如果是从左到右，按普通的尾部追加节点即可
        * 如果是从右到左，使用头插法增加节点
        * */
        if(height % 2 == 0)
            subList.add(root.val);
        else
            subList.add(0, root.val);

        travel(root.left, result, height + 1);
        travel(root.right, result, height + 1);
    }

从前序与中序遍历序列构造二叉树

/**
 * @description ：(LeetCode-105) 从前序与中序遍历序列构造二叉树
 * 给定一棵树的前序遍历 preorder 与中序遍历inorder。请构造二叉树并返回其根节点。
 */
    /*基于递归的实现*/
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(0, 0, inorder.length - 1, preorder, inorder);
//        Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();
//
//        for(int i = 0; i < inorder.length; i++) {
//            inMap.put(inorder[i], i);
//        }
//        return buildTreeWithMap(0, 0, inorder.length - 1, preorder, inorder,inMap);
    }

    /**
     * @param preStart 前序数组的第一个元素，也就是根结点
     * @param inStart 中序数组的开始元素
     * @param inEnd 中序数组的结束元素
     * @return
     */
    public TreeNode buildTree(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        /*构建二叉树的根结点*/
        TreeNode root = new TreeNode(preorder[preStart]);
        /*存放根结点在中序数组的位置*/
        int inIndex = 0;
        /*在中序数组中寻找根结点所在位置*/
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }

        /*递归的处理左右子树*/
        /*左子树的根结点就是前序数组中preStart的后一个元素，
        范围则是中序数组的inStart到inIndex - 1之间*/
        root.left = buildTree(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        /*右子树的根结点所在位置需要跳过整个左子树节点数目，也就是inIndex - inStart，
        所以根结点的位置就是preStart + inIndex - inStart再加1
        范围则是中序数组的inIndex + 1到n之间*/
        root.right = buildTree(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }

    /*使用Map加速查找过程*/
    public TreeNode buildTreeWithMap(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder,
                                     Map<Integer, Integer> inMap) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        /*构建二叉树的根结点*/
        TreeNode root = new TreeNode(preorder[preStart]);
        /*存放根结点在中序数组的位置*/
        int inIndex = inMap.get(root.val);

        root.left = buildTreeWithMap(preStart + 1, inStart, inIndex - 1,
                preorder, inorder,inMap);
        root.right = buildTreeWithMap(preStart + inIndex - inStart + 1, inIndex + 1, inEnd,
                preorder, inorder,inMap);
        return root;
    }

二叉树展开为链表

/**
 * @description ：(LeetCode-114) 二叉树展开为链表
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * 展开后的单链表应该同样使用 TreeNode ，
 * 其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树先序遍历顺序相同。
 */
    /*递归实现，但是空间复杂度为O(n)*/
    public void flatten(TreeNode root) {
        if (root == null) return;
        /*将二叉树展开为链表之后会破坏二叉树的结构，需要事先存储左右子树*/
        TreeNode leftSave = root.left;
        TreeNode rightSave = root.right;
        /*将根结点的左子树置为null*/
        root.left = null;
        /*递归处理左右子树*/
        flatten(leftSave);
        flatten(rightSave);
        /*将左子树的节点加入链表，替换根结点的右子树*/
        root.right = leftSave;
        TreeNode cur = root;
        /*将右子树的节点加入链表*/
        while (cur.right != null) cur = cur.right;
        cur.right = rightSave;
    }

    /*循环实现，空间复杂度为O(1)*/
    public void flattenWithLoop(TreeNode root) {
        while (root != null) {
            if (root.left == null) {
                root = root.right;
            } else {
                /*寻找左子树最右边的节点*/
                TreeNode rightmost = root.left;
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                /*将原来的右子树挂到左子树的最右边节点的右指针上*/
                rightmost.right = root.right;
                /*将左子树挂到root节点的右指针上*/
                root.right = root.left;
                root.left = null;
                /*此时root节点的左子树已经为null,
                向下寻找，看看下面的节点上是否还存在着左子树，重复上述过程*/
                root = root.right;
            }
        }
    }

二叉树的右视图

/**
 * @author ：Mark老师
 * @description ：(LeetCode-199) 二叉树的右视图
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧
 * 按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 */
    /*递归实现*/
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }

    public void rightView(TreeNode root, List<Integer> result, int depth){
        if(root == null){
            return;
        }
        /*对于右子树来说，遇到一个右子树的节点，就加入结果集
        对左子树来说，只有结果集不存在右子树的节点，才会加入结果集*/
        if(depth == result.size()){
            result.add(root.val);
        }
        /*往下一层寻找，优先寻找右子树*/
        rightView(root.right, result, depth + 1);
        rightView(root.left, result, depth + 1);
    }

    /*利用层序遍历逆序和队列实现*/
    public List<Integer> rightSideViewWithQueue(TreeNode root) {
        List<Integer> result = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        if (root == null) return result;

        queue.offer(root);
        while (!queue.isEmpty()) {
            /*获得每层的节点数*/
            int levelNodeNum = queue.size();
            /*处理本层的节点*/
            for (int i=0; i<levelNodeNum; i++) {
                TreeNode cur = queue.poll();
                if (i == 0) result.add(cur.val);
                /*和层序遍历不同，应该是右子树先入队*/
                if (cur.right != null) queue.offer(cur.right);
                if (cur.left != null) queue.offer(cur.left);
            }
        }
        return result;
    }

实现 Trie (前缀树)

/**
 * @description ：(LeetCode-208) 实现 Trie (前缀树)
 * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，
 * 用于高效地存储和检索字符串数据集中的键。
 * 这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
 * 请你实现 Trie 类
 */
    /*树节点的定义*/
    static class TrieNode {
        TrieNode[] children;
        boolean isEnd;
        TrieNode() {
            /*word和prefix仅由小写英文字母组成，只有26种可能*/
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    static class Trie {
        /*Trie的根节点*/
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            insertChar(word, 0, root);
        }

        public boolean search(String word) {
            return searchChar(false,word,0, root);
        }

        public boolean startsWith(String prefix) {
            return searchChar(true,prefix,0, root);
        }

        /*用递归实现插入字符串*/
        void insertChar(String word, int index, TrieNode currNode) {
            /*字符串中的字符已经全部插入完成，增加结束标识*/
            if (index == word.length()) {
                currNode.isEnd = true;
                return;
            }
            /*计算字符在数组中的下标*/
            int charIndex = word.charAt(index) - 'a';
            if (currNode.children[charIndex] == null) {
                currNode.children[charIndex] = new TrieNode();
            }
            insertChar(word, index + 1, currNode.children[charIndex]);
        }

        /*用递归实现查找字符串，
        题目要求实现的search和startsWith本质上是一回事，所以共用一个查找方法
        用参数isPrefix区分*/
        boolean searchChar(boolean isPrefix,String word, int index, TrieNode currNode) {
            /*整个字符串遍历完成，要返回true，要么是前缀查找，要么达到了子树的最后*/
            if (index == word.length()) {
                return isPrefix || currNode.isEnd;
            }
            int charIndex = word.charAt(index) - 'a';
            if (currNode.children[charIndex] == null) {
                return false;
            }
            return searchChar(isPrefix,word, index + 1, currNode.children[charIndex]);
        }
    }
}

二叉树的最近公共祖先

/**
 * @description ：(LeetCode-236) 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
 * 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先
 * 且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /*找到p或者q所在节点，终止递归；或者找到叶子节点也没找到p或者q*/
        if(root == null || root == p || root == q)  return root;
        /*返回时left和right的返回结果是p或者q或者为null，
        或者p和q的最近公共祖先node*/
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        /*left和right不为空，说明p和q就在当前root节点下，
        root节点就是我们需要的最近公共祖先*/
        if(left != null && right != null)   return root;
        /*left和right有一个为空，返回不为空的那个
        * left和right的都为空，返回哪个都可以，这里统一返回right*/
        return left != null ? left : right;
    }

路径总和 III

/**
 * @author ：Mark老师
 * @description ：(LeetCode-437) 路径总和 III
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，
 * 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，
 * 但是路径方向必须是向下的（只能从父节点到子节点）。
 */
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> prefixSum = new HashMap();
        /*Map的key就是前缀和，value记录是前缀和出现的次数
        初始化，任何节点本身也可以形成一个路径。
        如果某个节点的值就为target，
        那么它本身就是一个解。前缀和为0正好可以与它形成这个解。
        给所有节点一个可单独形成合法路径的机会。*/
        prefixSum.put(0,1);
        /*从根结点开始遍历*/
        return traversal(root, 0, sum, prefixSum);
    }

    public int traversal(TreeNode root, int currSum, int target,
                         HashMap<Integer, Integer> prefixSum) {
        if (root == null) {
            return 0;
        }
        /*已有的前缀和加上当前节点的值形成的当前节点前缀和*/
        currSum = currSum+ root.val;
        /*差值 = 当前节点的前缀和-targetSum
        在前面保存的前缀和map中寻找有没有等于差值的记录
        result用来记录当前节点下满足条件的路径数*/
        int result = prefixSum.getOrDefault(currSum - target, 0);
        /*将当前节点的前缀和放入Map,有就说明现在多了一条满足题目要求的路径，+1，
        没有，这个前缀和初始的value为1*/
        prefixSum.put(currSum, prefixSum.getOrDefault(currSum, 0) + 1);
        /*向下层节点递归遍历寻找满足条件的节点，左右子树的都要加上*/
        result = result + traversal(root.left, currSum, target, prefixSum)
                + traversal(root.right, currSum, target, prefixSum);
        /*一个节点的前缀和信息更新到map里时，它应当只对其子节点们有效,所以
        往上层返回的时候要减一*/
        prefixSum.put(currSum, prefixSum.get(currSum) - 1);
        return result;
    }

删除二叉搜索树中的节点

/**
 * @description ：(LeetCode-450) 删除二叉搜索树中的节点
 * 给定一个二叉搜索树的根节点 root 和一个值 key，
 * 删除二叉搜索树中的 key 对应的节点，
 * 并保证二叉搜索树的性质不变。
 * 返回二叉搜索树（有可能被更新）的根节点的引用。
 */
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return null;

        /*如果目标节点小于当前节点值，则去左子树中删除*/
        if(key<root.val){
            root.left = deleteNode(root.left,key);
        }
        /*如果目标节点大于当前节点值，则去右子树中删除*/
        else if(key>root.val){
            root.right = deleteNode(root.right,key);
        }
        /*找到了当前节点*/
        else{
            /*当前节点的左子树为空，返回当前节点的右子树后，
            上级节点指向当前节点的指针会被这个返回值所代替
            因为叶子节点的左右子树均为null，通过这种方式，
            叶子节点自然而然会被删除*/
            if(root.left==null){
                return root.right;
            }
            /*当前节点的右子树为空，返回当前节点的左子树后，
            上级节点指向当前节点的指针会被这个返回值所代替*/
            else if(root.right==null){
                return root.left;
            }
            else{/*当前节点的左右子树均不为空*/
                /*寻找当前右子树的最左节点*/
                TreeNode rightMin = root.right;
                while(rightMin.left!=null){
                    rightMin = rightMin.left;
                }
                /*当前节点左子树成为其右子树的最左节点的左子树*/
                rightMin.left = root.left;
                /*当前节点的的右子顶替其位置，节点被删除*/
                root = root.right;
            }
        }
        return root;
    }

把二叉搜索树转换为累加树

/**
 * @description ：(LeetCode-538) 把二叉搜索树转换为累加树
 * 给出二叉 搜索 树的根节点，该树的节点值各不相同，
 * 请你将其转换为累加树（Greater Sum Tree），
 * 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
 */
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        accessTree(root);
        return root;
    }

    public void accessTree(TreeNode root) {
        if (root == null) return;
        accessTree(root.right);
        root.val += sum;
        sum = root.val;
        accessTree(root.left);
    }

二叉树的直径

/**
 * @author ：Mark老师
 * @description ：(LeetCode-543) 二叉树的直径
 * 给定一棵二叉树，你需要计算它的直径长度。
 * 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
 * 这条路径可能穿过也可能不穿过根结点。
 */
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        /*递归计算当前节点左子树计算深度*/
        int left = maxDepth(root.left);
        /*递归计算当前节点右子树计算深度*/
        int right = maxDepth(root.right);

        /*取已有深度最大值以及当前节点左右子树深度和两者的最大值*/
        max = Math.max(max, left + right);

        /*返回以当前节点为根的树的深度*/
        return Math.max(left, right) + 1;
    }

二叉树中的最大路径和

/**
 * @description ：(LeetCode-124) 二叉树中的最大路径和
 * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。
 * 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 */
    int maxValue = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxPathDown(root);
        return maxValue;
    }

    private int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        /*递归计算当前节点通往左子树节点的节点值之和，节点值之和<0，抛弃*/
        int left = Math.max(0, maxPathDown(node.left));
        /*递归计算当前节通往右子树节点的节点值之和，节点值之和<0，抛弃*/
        int right = Math.max(0, maxPathDown(node.right));

        /*取已有最大值以及“当前节点值和左右子树节点值之和的和”两者的最大值*/
        maxValue = Math.max(maxValue, left + right + node.val);

        /*返回以当前节点为根的树的节点值之和*/
        return Math.max(left, right) + node.val;
    }

part 5

搜索旋转排序数组

/**
 * @description ：(LeetCode- 33) 搜索旋转排序数组
 * 整数数组 nums 按升序排列，数组中的值 互不相同 。
 * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，
 * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
 * 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
 * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
 */

    /*二分查找*/
    public int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end)/2;
            int numMid = nums[mid];
            if(numMid == target) return  mid;
            /*numMid和target都大于nums[0]或者都小于nums[0]，说明nums[mid]和target在同一段
            *nums[mid]和target不在同一段，将numMid变为正无穷∞或者负无穷-∞*/
            if (!((numMid < nums[0]) == (target < nums[0]))) {
                numMid = target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            /*mid所指示的数num比target小，移动start，否则移动end*/
            if (numMid < target)
                start = mid + 1;
            else
                end = mid - 1;
        }
        return -1;
    }

    /*基于数组一半有序的原理*/
    public int search2(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            int num = nums[mid];
            if (target == num) {
                return mid;
            }
            /*左半段是有序的*/
            if (nums[start] <= num) {
                /*target 在这段里*/
                if (target >= nums[start] && target < num) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            /*右半段是有序的*/
            } else {
                if (target > num && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }

在排序数组中查找元素的第一个和最后一个位置

/**
 * @description ：(LeetCode- 34) 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。
 * 找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 进阶： * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 */
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findFirst(nums, target);
        /*如果第一个没找到，最后一个也不必找了*/
        if(result[0] == -1) return new int[]{-1,-1};
        /*找到第一个，寻找最后一个不需要从数组第0个元素开始寻找*/
        result[1] = findLast(result[0],nums, target);
        return result;
    }

    private int findFirst(int[] nums, int target){
        int idx = -1;
        int start = 0;
        int end = nums.length - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            /*等于的情况下也不能停止寻找，一直要找到start > end为止，
            才是第一个target所在位置*/
            if(nums[mid] >= target){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
            if(nums[mid] == target) idx = mid;
        }
        return idx;
    }

    private int findLast(int first,int[] nums, int target){
        int idx = -1;
        int start = first;
        int end = nums.length - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(nums[mid] <= target){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
            if(nums[mid] == target) idx = mid;
        }
        return idx;
    }

寻找旋转排序数组中的最小值

/**
 * @description ：(LeetCode- 153) 寻找旋转排序数组中的最小值
 * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。
 *  * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，
 *  并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
 */
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            /*如果start和end只相差一个元素，直接比较两者大小*/
            if (start + 1 == end) {
                return Math.min(nums[start], nums[end]);
            }
            int mid = (start + end) / 2;
            if(nums[start]<=nums[mid] && nums[mid]<=nums[end]){
                return nums[start];
                /*最小值在 left半区*/
            }else if(nums[start]>=nums[mid] && nums[mid]<nums[end]){
                end = mid ;
            }
            /*最小值在 right半区*/
            else{
                start = mid ;
            }
        }
        return -1;
    }

搜索二维矩阵 II

	/**
	 * @description ：(LeetCode- 240) 搜索二维矩阵 II
	 * 编写一个高效的算法来搜索 m * n 矩阵 matrix 中的一个目标值 target 。
	 * 该矩阵具有以下特性：
	 * 每行的元素从左到右升序排列。
	 * 每列的元素从上到下升序排列。
	 */
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null) {
            return false;
        }
        /*矩阵行和列下标的最大值*/
        int cols = matrix[0].length-1;
        int rows = matrix.length-1;
        /*目标值大于矩阵元素的最大值*/
        if(target > matrix[rows][cols]) return false;

        int currentCol = cols;
        int currentRow = 0;
        /*循环中的变化情况为，要么当前行递增，要么当前列递减*/
        while(currentCol >= 0 && currentRow <= rows) {
            if(target == matrix[currentRow][currentCol]) {
                return true;
            } else if(target < matrix[currentRow][currentCol]) {
                currentCol--;
            } else if(target > matrix[currentRow][currentCol]) {
                currentRow++;
            }
        }
        return false;
    }

无重复字符的最长子串

/**
 * @description ：(LeetCode- 3) 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */
 /*LeetCode官方解法，使用HashSet判断是否有重复的字符*/
    public int lengthOfLongestSubstringWithHash(String s) {
        /*哈希集合，记录每个字符是否出现过*/
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        /*右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动*/
        int rk = -1, ans = 0;
        /*遍历字符串，i代表左指针*/
        for (int i = 0; i < n; ++i) {
            /*i = 0,hash集合中还没有字符，自然就不需要移除*/
            if (i != 0) {
                /*左指针向右移动一格，移除一个字符*/
                occ.remove(s.charAt(i - 1));
            }
            /*i = 0时，rk + 1=0，从字符串第0个字符开始*/
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                /*不断地移动右指针*/
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            /*第 i 到 rk 个字符是一个极长的无重复字符子串*/
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    /*使用HashMap优化*/
    public int lengthOfLongestSubstringWithMap(String s) {
        /*map用来记录每个字符的最近一次的索引*/
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        /*end负责遍历整个字符串*/
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)){
                /*如果map中已经包含当前字符，说明出现了重复，
                将start位置跳转到当前字符上一次出现位置+1，比如："abcabcdbb"
                0 1 2 3 4 5 6 7 8
                a b c a b c d b b
                      ^       ^
                    start    end
                end=7,start=3，这个时候start可以直接跳至 5*/
                start = Math.max(map.get(ch)+1,start);
            }
            max = Math.max(max,end - start + 1);
            map.put(ch,end);
        }
        return max;
    }

最长回文子串

/**
 * @description ：(LeetCode-5) 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */
    public String longestPalindrome(String s) {
        int maxStart = 0, maxEnd = 0;
        for (int i = 0; i < s.length(); i++) {
            /*以当前字符为中心，进行左右扩展*/
            int charCenterLen = expandAroundCenter(s, i, i);
            /*以当前字符后的空白为中心，进行左右扩展*/
            int BlackCenterLen = expandAroundCenter(s, i, i + 1);
            int len = Math.max(charCenterLen, BlackCenterLen);
            /*更新最长的回文子串的长度*/
            if (len > maxEnd - maxStart) {
                maxStart = i - (len - 1) / 2;
                maxEnd = i + len / 2;
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        /*从中心，进行左右扩展判断字符是否相等，每次步进一个字符*/
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

字符串转换整数 (atoi)

/**
 * @description ：(LeetCode-8)  字符串转换整数 (atoi)
 * 请你来实现一个 myAtoi(string s) 函数，
 * 使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
 */
    public int myAtoi(String s) {
        int len = s.length();
        /*因为要逐个字符处理，先转换为字符数组*/
        char[] charArray = s.toCharArray();
        int idx = 0;

        /*1、检查是否空格*/
        while (idx < len && charArray[idx] == ' ') {
            idx++;
        }

        /*2、idx和字符串的长度相等，说明字符串全部是空格*/
        if (idx == len) {
            return 0;
        }

        /*3、此时idx指向为第一个非空格字符，idx前面字符均可忽略
        如果出现符号字符，用sign记录正负*/
        int sign = 1;
        char firstChar = charArray[idx];
        if (firstChar == '+') {
            idx++;
        } else if (firstChar == '-') {
            idx++;
            sign = -1;
        }

        /*4、读取后续出现的数字字符并进行转换*/
        int result = 0;
        while (idx < len) {
            char currentChar = charArray[idx];
            /*出现了'0'~'9'之外的字符终止循环，比如示例4：“words and 987”，会直接返回0*/
            if (currentChar > '9' || currentChar < '0') {
                break;
            }

            /*只能存储 32 位大小的有符号整数，
            如果在已有数字的基础上*10再加上当前数字，很有可能溢出，
            需要提前判断乘以 10 以后是否溢出,
            result>Integer.MAX_VALUE/10用以判断result本身乘以 10是否溢出
            (result == Integer.MAX_VALUE / 10 && (currentChar - '0') > Integer.MAX_VALUE % 10)
            用以判断result本身乘以10后的个位数部分，是否可以容纳下当前数字，当然直接写数字7也可以，
            比如：(result == Integer.MAX_VALUE / 10 && (currentChar - '0') > 7
            */
            if (result > Integer.MAX_VALUE / 10
                    || (result == Integer.MAX_VALUE / 10 && (currentChar - '0') > Integer.MAX_VALUE % 10)) {
                return Integer.MAX_VALUE;
            }
            /*和上面代码的意义一致
            if中后面的条件也可以改成(result == Integer.MIN_VALUE / 10 && (currentChar - '0') > 8
            */
            if (result < Integer.MIN_VALUE / 10
                    || (result == Integer.MIN_VALUE / 10 && (currentChar - '0') > -(Integer.MIN_VALUE % 10))) {
                return Integer.MIN_VALUE;
            }

            /*转换，并更新result，准备处理下一个字符*/
            result = result * 10 + sign * (currentChar - '0');
            idx++;
        }
        return result;
    }