【LeetCode】 LeetCode(重点题型总结)

LeetCode

字数统计: 26.1k阅读时长: 116 min

 2021/08/21 

Leetcode

Array

摩尔投票

题目背景：从一个数组中找到关键元素（关键元素的数量大于数组中元素总数的一半）

算法思路：

维护一个majority，用来记录可能的关键元素
维护一个count，用来记录投票数
- 对数组中的元素进行一次循环，如果count == 0，说明此时还没有确定关键元素，majority = num[i]， count++
- 如果count != 0，说明，majority中已经有了备选方案，如果当前元素 == majority，count++；否则count- -
遍历完成后，
- 如果count == 0，说明没有关键元素，返回-1
- 如果count != 0，只能说明现在的majority是众数，但不一定大于数组的一半
验证：判断这个数的出现次数是否超过了一半
完毕

伪代码：

int majorityElement(int[] nums){
    //如果数组长度为0，返回-1
    if(nums.length()<=0){
        return -1;
    }
    //维护两个变量majority和count
    int majority = 0;
    int count = 0;
    //循环遍历所有元素
    for(int i = 0; i<nums.length; i++){
        if(count == 0){
            majority = nums[i];
            count++;
        }else{
            if(nums[i] == majority){
                count++;
            }else{
                cout--;
            }
        }
    }
    
    //此时已经获得了众数majority
    //接下来判断是否满足关键元素
    if(count == 0){
        return -1;
    }
    int identify = 0;
    for(int i = 0; i<nums.length; i++){
        if(nums[i] == majority){
            identify++;
        }
        if(identify>nums.length/2){
            return majority;
        }
    }
}

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

要求：线性时间，常数空间

算法：

数组只能遍历一次，不能有额外的外部空间
考虑到可以使用位运算：

位运算的特征

所以整个数组中的数，相同的数两两组合，最后剩下的数就是唯一的一个数，因为遵循交换律和结合律，所以可以直接遍历数组的数，求所有数的异或

设定result初始值为0，遍历所有数，连续异或

int result = 0;
for(int i = 0; i < nums.length; i++){
    result ^= nums[i];
}
return result;

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
1
2
3
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

算法：

对数组排序：O(nlogn)
对a枚举O(n)
对b和c采用双指针，两侧逼近target O(n)
优化：
1. 如果三数之和为target，直接返回
2. 如果pb或者pc所指的数和之前相同，继续移动，直到一个新的数

总的时间复杂度：O(n²)

代码：

//暴力解法
    public static int threeSumClosest(int[] nums, int target) {
        int sub = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 0; i<nums.length; i++){
            for(int j = i+1; j<nums.length; j++){
                for(int k = j+1; k<nums.length; k++){
                    int newSub = Math.abs(nums[i]+nums[j]+nums[k]-target);
                    if (newSub<sub){
                        sub = newSub;
                        sum = nums[i]+nums[j]+nums[k];
                    }
                }
            }
        }
        return sum;
    }

    //双指针法
    public static int threeSumClosest2(int[] nums, int target) {
        int best = 10000000;
        Arrays.sort(nums);
        for(int i = 0; i<nums.length; i++){
            int pb = i+1;
            int pc = nums.length-1;
            while(pb<pc){
                int sum = nums[i] + nums[pb] + nums[pc];
                if(sum == target){
                    return target;
                }
                if(Math.abs(best-target)>Math.abs(sum-target)){
                    best = sum;
                }
                if(sum < target){
                    pb++;
                    //如果当前位置和上一个位置相同，则继续前往下一个位置，直到当前位置的数和之前不同，
                    //所以需要判断的是当前位置和之前位置的数是否相同，
                    //如果判断条件是：nums[pb+1] == nums[pb]；则当前位置的数会被跳过，可能会导致指针pb和pc不能指向数值想同的不同位置
                    //比如下面的例子：{-1，0，1，1，55}；无法使得pb指向第一个1，pc指向第二个1
                    while(pb<pc && nums[pb] == nums[pb-1]){
                        pb++;
                    }
                }

                if(sum > target){
                    pc--;
                    while(pb<pc && nums[pc+1] == nums[pc]){
                        pc--;
                    }
                }
            }
        }
        return best;

    }


    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,1,55};
        System.out.println(threeSumClosest2(nums, 3));
    }

1588. 所有奇数长度子数组的和

题目：

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。子数组定义为原数组中的一个连续子序列。请你返回 arr 中所有奇数长度子数组的和。

输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

我的想法：维护一个窗口，编写一个可以从窗口中求和的方法，在外界循环中不断的缩小窗口，内侧循环中不断地向后移动窗口

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int maxOdd = arr.length%2 == 0 ? arr.length-1 : arr.length;
        int result = 0;
        while(maxOdd>0){
            int leftBound = 0; 
            int rightBound = leftBound+maxOdd-1;
            while(rightBound<arr.length){
                result += sum(arr, leftBound, rightBound);
                leftBound++;
                rightBound = leftBound+maxOdd-1;
            }
            maxOdd -= 2;
        }
        return result;
    }

    public int sum(int[] nums, int leftBound, int rightBound){
        int sum = 0;
        for(int i = leftBound; i<=rightBound; i++){
            sum += nums[i];
        }
        return sum;
    }
}

LeetCode方法：

归根到底计算的是每一个元素出现的次数，当遍历到下标为 i 的元素（第i+1个元素），左边有 i 个元素，右边有length-1-i个元素

元素数为奇数的条件：左边元素的数量+1（当前元素）+右边元素的数量 = 奇数

情况1：奇数+1+奇数

情况2：偶数+1+偶数

从n个数中选择奇数个数的可能情况：(n+1)/2

从n个数中选择偶数个数的可能情况：(n/2)+1

那么当前元素可参与的长度为奇数的连续数组的可能情况：

1	leftOdd * rightOdd + leftEven * rightEven

只要计算出每一个数的出现次数即可：

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int result = 0;
        for(int i = 0; i<arr.length; i++){
            int leftOdd = (i+1)/2;
            int leftEven = (i/2)+1;
            int rightOdd = (arr.length-i)/2;
            int rightEven = (arr.length-1-i)/2+1;
            result += arr[i]*(leftOdd*rightOdd+leftEven*rightEven);
        }
        return result;
    }
}

832. 反转图像

给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。

反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。

示例 1:

输入: [[1,1,0],[1,0,1],[0,0,0]]
输出: [[1,0,0],[0,1,0],[1,1,1]]
解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
     然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
示例 2:

输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        for(int i = 0; i<m; i++){
            for(int j = 0; j<(n+1)/2; j++){ //注意这里，当列数为奇数的时候，中间的一位也需要和1异或，所以交换次数要+1
                swap(A[i], j, n-1-j);
            }
        }
        return A;

    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i]^1; //这里通过和1异或可以改变当前数的值
        nums[i] = nums[j]^1;
        nums[j] = temp;
    }
}

1160 拼写单词

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

算法：

准备一个长度为26的数组1，用来存放chars中每个英语字母出现的次数
将chars中的字母都存放进去，索引代表字母，值代表出现的次数
遍历words中的每个单词，再准备一个数组2，用来存放每一个单词中字母的出现次数
遍历两个数组，如果可以保证每一个数组2中的对应数字都小于数组1中的数字，那么这个单词就记住了，加上它的长度就可以了

代码：

public int countCharacters(String[] words, String chars) {
        int[] cArr = new int[26];
        for (char c:chars.toCharArray()
             ) {
            cArr[c-'a']++;
        }
        int result = 0;
        for (String word:words
             ) {
            int[] wArr = new int[26];
            for (char w:word.toCharArray()
                 ) {
                wArr[w-'a']++;
            }
            boolean can = true;
            for (int i = 0; i < 26; i++) {
                if (wArr[i]>cArr[i]){
                    can = false;
                    break;
                }
            }
            if (can) {
                result += word.length();
            }
        }
        return result;
    }

3 最长无重复子串


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

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

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

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

输入: s = ""
输出: 0

算法：滑动窗口+集合

准备左右两个指针
右指针向右移动，并将指向的字符存进set中
如果遇到重复的字母（set中存在），则右指针停下，记录此时的长度，从set中删除左指针指向的字符，左指针向右移动，
右指针遍历完毕整个字符串，结束，返回长度size

进阶版：滑动窗口+哈希表：

直接跳转到左指针移动的情况：原方法是左指针一个一个移动，直到将set中和 ==右指针==指向字符重复的字符删除，但是这样左指针会遍历一些无用的字符：原左指针的位置——>发生重复字符的位置（比如：gqcdef==a== babc，即从g到标记的a的位置），这一段是多余的。

改进方案：用map存储每个字符的位置信息，如果遇到了重复字符，左指针直接跳到该重复字符的下一个位置：从g直接跳到b，从常数时间上降低了复杂度

public static int lengthOfLongestSubstring(String s) {//用map优化去重
       if(s.length() == 0){
           return 0;
       }
       int maxSize = 0;
       HashMap<Character, Integer> map = new HashMap<>();
       int l = 0;
       int r = 0;
       while(l<=r && r<s.length()){
           if(map.containsKey(s.charAt(r))){
               l = Math.max(l, map.get(s.charAt(r))+1);
           }
           map.put(s.charAt(r), r++);
           maxSize = Math.max(maxSize, (r-l));
       }
       return maxSize;
   }

   public static int lengthOfLongestSubstring2(String s){//用set去重
       int maxSize = 0;
       HashSet<Character> set = new HashSet<>();
       int l = 0;
       int r = 0;
       while(l<=r && r<s.length()){
           while(r<s.length() && (!set.contains(s.charAt(r)))){
               set.add(s.charAt(r++));
           }
           maxSize = Math.max(maxSize, r-l);
           if(r == s.length()-1){
               return maxSize;
           }
           set.remove(s.charAt(l));
           l++;
       }
       return maxSize;
   }

239 滑动窗口最大值

public int[] maxSlidingWindow(int[] nums, int k) {
       PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
           public int compare(int[] pair1, int[] pair2){
               return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair2[1];
           }
       });
       
       int[] result = new int[nums.length - k + 1];

       for(int i = 0; i<k; i++){
           queue.offer(new int[]{nums[i],i});
       }
       result[0] = queue.peek()[0];
       for(int i = 1; i+k-1<nums.length; i++){
           queue.offer(new int[]{nums[i+k-1], i+k-1});
           while(queue.peek()[1]<i){
               queue.poll();
           }
           result[i] = queue.peek()[0];
       }
       
       return result;
   }

左神的方法：利用双端队列中的单调性：

public int[] maxSlidingWindow(int[] nums, int k) {
       if(nums == null || nums.length<k || k<1){
           return null;
       }
       LinkedList<Integer> queue = new LinkedList<>();
       int[] result = new int[nums.length - k + 1];
       int index = 0;
       for(int i = 0; i<nums.length; i++){
           while(!queue.isEmpty() && nums[i]>=nums[queue.peekLast()]){
               queue.pollLast();
           }
           queue.addLast(i);
           if(queue.peekFirst()<=(i-k)){//如果被窗口抛下了（在窗口左边界的左侧）
               queue.pollFirst();
           }
           if(i>=k-1){
               result[index++] = nums[queue.peekFirst()];
           }
       }
       return result;
   }

189 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

算法：旋转数组：

步骤	旋转后的效果
旋转整个数组（镜像）	[7,6,5,4,3,2,1]
旋转前k个数	[5,6,7, 4,3,2,1]
旋转剩下的数	[5,6,7, 1,2,3,4]

class Solution {
    public void rotate(int[] nums, int k) {
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k%(nums.length)-1);
        reverse(nums, k%(nums.length), nums.length-1);
    }

    public void reverse(int[] nums, int left, int right){
        while(left<=right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

剑指offer 03

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/yuan-di-zhi-huan-shi-jian-kong-jian-100-by-derrick/705525

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

算法：利用一个萝卜一个坑的方式去想，因为一共有0个数，所有数字的范围都在0～n-1之间，所以在没有重复的情况下，排序完成之后的数组将是0位置对应的数字为0，1位置对应的数字为1……每个位置的数字即为其下标的数字。

我们从第一个下标i和元素m不对应的位置i开始，将元素换到下标和元素相同的位置m，直到当前下标i的元素值为i.如果发现m位置的元素已经为m，说明m为重复元素，直接返回即可。

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0; i<nums.length; i++){
            while(nums[i] != i){
                if(nums[nums[i]] != nums[i]){
                    swap(nums, i, nums[i]);
                }else{
                    return nums[i];
                }
            }
        }
        return -1;
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

栈和队列

最小栈（剑指offer 30）

最大队列（剑指offer59）

单调栈：

739 每日温度

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

算法：

准备一个栈，一个结果数组res[]
从头开始遍历参数-温度数组
如果栈为空，加入当前温度下标
如果栈不为空，且当前栈顶元素peek小于当前遍历到的元素cur（注意，当前存入的是温度数组的下标，比较的却是下标对应的温度值），弹出栈顶元素，且在结果数组中，栈顶元素peek的位置，存入栈顶元素peek和当前遍历到的元素cur差（表示：栈顶元素找到了第一个比自己大的温度）
如果栈为空，或者栈顶元素peek不小于当前遍历到的元素cur，将当前遍历到的元素cur压栈
循环完毕

class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int n = T.length;
        int[] res = new int[n];
        for(int i = 0; i<n; i++){
            while(!stack.isEmpty() && T[i]>T[stack.peek()]){
                res[stack.peek()] = i-stack.pop();//出栈，且将两个下标差存入出栈的下标的位置
            }
            stack.push(i);
        }
        return res;
    }
}

单调双端队列

滑动窗口最大值

进制问题

168 Excel列表的名称

给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，
    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...

将n看作是一个26进制的数字，而且每一位的最小值为A，通过不断尝试得到以下结果：

class Solution {
    public String convertToTitle(int n) {
        StringBuilder result = new StringBuilder();
        while(n>0){
            int rem = (n-=1) % 26;//注意在这里：关键点在于要对n减1，这样可以保证当n==26的时候，余数不会为0，导致插入的字母为A
            result.insert(0, (char)('A'+rem));
            n/=26;
        }
        return result.toString();
    }
}

ListNode

86 分隔链表

利用哨兵节点，将内容分成两个链表，然后再按照要求将两个链表合并起来

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

示例：
输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

public ListNode partition(ListNode head, int x) {
       if(head == null){
           return null;
       }
       ListNode less = new ListNode(0);//哑节点，用来防止nullPointer
       ListNode more = new ListNode(0);
       ListNode lessPtr = less;
       ListNode morePtr = more;
       while(head != null){
           if(head.val>=x){
               morePtr.next = new ListNode(head.val);
               morePtr = morePtr.next;
           }else{
               lessPtr.next = new ListNode(head.val);
               lessPtr = lessPtr.next;
           }
           head = head.next;
       }
       lessPtr.next = more.next;
       return less.next;
   }

160 相交链表

算法：

对于两个链表，A+C和B+C，C是两个链表公有的部分。同时遍历两个链表的时候可以发现A+C+B = B+C+A。
准备两个指针指向链表开头，分别同时向下遍历，如果ptrA指向了null（链表结尾），就跳转到headB；如果ptrB指向了null，就跳转到headA，（这是为了应对在两个链表长度不等的情况下，指针可以在重合部分之前走过相同的节点，这样就可以同时达到公共节点了）
当两个指针指向的节点相同的时候（公共节点或者null），将这个节点返回

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode lA = headA;
        ListNode lB = headB;
        while(lA!=lB){
            lA = lA == null ? headB : lA.next;
            lB = lB == null ? headA : lB.next;
        }
        return lA;
    }
}

24 两两交换链表中的节点

算法：

首先创建一个dummyNode哑节点，其next指向head
准备一个temp指针指向当前要处理的节点
对temp后面的两个节点，做如下交换：
temp.next = node2; node1.next = node2.next; node2.next = node1;

将temp节点向后移动，移动两个位置，如果当前位置后面还有两个节点，继续调换，如果没有节点了或者只有一个节点，停止

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyHead = new ListNode(-1);//哑节点
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while(temp.next != null && temp.next.next != null){//两步一交换
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}

445 两数相加

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

算法：

利用两个栈来逆序链表，计算好结果后通过头插法插入到新的链表中

贪心算法

435 不重叠的区间的个数

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

算法：

将数组中的区间按照右边界的大小进行排序（从小到大）
因为右边界小的区间会给其他区间更多的可能，贪心策略就是尽可能的寻找右边界小的区间，而且左边界没有小于上一个有效区间的右边界
如果找到一个满足条件的区间，计数加一，当前区间变为有效区间
最后用总的区间数减去不发生重叠的区间数就可以了

public int eraseOverlapIntervals(int[][] intervals) {
       if(intervals == null || intervals.length <= 1){
           return 0;
       }

       //排序，自己重写比较器
       Arrays.sort(intervals, new Comparator<int[]>(){
           public int compare(int[] arr1, int[] arr2){
               return arr1[1] - arr2[1];
           }
       });

       int count = 1;
       int index = 0;//指向（左边界）>=前者（有边界的区间）的
       for(int i = 1; i<intervals.length; i++){
           if(intervals[i][0]>=intervals[index][1]){
               count++;
               index = i;//因为当前区间满足要求，index就指向了当前区间
           }
       }
       return intervals.length - count;
   }

406 根据身高和序号重组队列

算法：

根据身高h从大到小排序
相同身高则根据k的大小排序
将排好序的数组按照顺序添加到链表中，这样可以保证先将身高较高的同学排好，再去排身高较低的几个同学，可以保证身高较低的同学的位置是正确的（不会被推到后面）

ps：其中h表示当前同学的身高，k表示在当前同学之前有k个同学的身高>=当前同学

public int[][] reconstructQueue(int[][] people) {
       //按照身高从大到小排序，相同身高按照前面的人数从小到大排序
       Arrays.sort(people, new Comparator<int[]>(){
           public int compare(int[] arr1, int[] arr2){
               return arr1[0] == arr2[0] ? arr1[1] - arr2[1] : arr2[0] - arr1[0];
           }
       });

       LinkedList<int[]> list = new LinkedList<>();
       for(int[] p:people){
           list.add(p[1],p);
       }
       return list.toArray(new int[list.size()][]);
   }

122 买卖股票的最大收益

题目描述：可以进行多次交易，多次交易之间不能交叉进行，可以进行多次交易。
举例：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加到收益中。

public int maxProfit(int[] prices) {
       if(prices.length <= 1){
           return 0;
       }
       int result = 0;
       for(int i = 1; i<prices.length; i++){
           if(prices[i]>prices[i-1]){
               result+=prices[i]-prices[i-1];
           }
       }
       return result;
   }

392 判断是否为子序列

1
2
3

s = "abc", t = "ahbgdc"
Return true.

很骚的方法：用时0ms

public boolean isSubsequence(String s, String t) {
       int index = -1;
       char[] letters = s.toCharArray();
       for(char c:letters){
           index = t.indexOf(c, index+1);//从index+1开始查找当前字符所在的位置，如果没有当前字符，返回-1
           if(index == -1){
               return false;
           }
       }
       return true;
   }

String

最长回文字串

//方法2，利用数组，桶计数
    public static int longestPalindrome2(String s){
        //将所有的字符按照ASCII码装到对应的bucket中
        int[] letters = new int[128];
        for (int i = 0; i < s.length(); i++) {
            letters[s.charAt(i)]++;
        }

        int count = 0;
        for (int n:letters
             ) {
            if (n>1){
                count+=(n/2*2);
            }
            if (n%2==1&&count%2==0){
                count++;
            }
        }

        return count;
    }

验证回文字串

算法：双指针

指针p1指向字符串头，指针p2指向字符串尾
两个指针相向而行，循环跳出条件：p1==p2
对于每个指针，如果当前指向的元素不是字母或者数字，向下移动一位，直到是字母或者数字为止
两个指针静止后，比较两个指针指向的元素
如果相等，p1++， p2- -，下一次循环
如果不相等，return false
最后return true

public static boolean isPalindrome(String s){
        if (s.length()==0){
            return true;
        }
        int p1 = 0;
        int p2 = s.length()-1;
        while(p1<p2){
            while(p1<p2&&!Character.isLetterOrDigit(s.charAt(p1))){
                p1++;
            }
            while(p1<p2&&!Character.isLetterOrDigit(s.charAt(p2))){
                p2--;
            }
            if (p1<p2) {
                if (Character.toLowerCase(s.charAt(p1)) == Character.toLowerCase(s.charAt(p2))) {
                    p1++;
                    p2--;
                }else {
                    return false;
                }
            }
        }
        return true;
    }

广度优先搜索

模板1

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

queue中添加的节点都是待处理的节点
每进行一次while循环，都距离根节点远一些，step+1
每次处理的都是queue中剩余的节点
将每一个node的邻居都加进来，之后再将被处理的节点弹出
缺点：如果出现环状链表，可能会导致无限循环

模板2

为了防止环状链表导致的无限循环，利用set来存储已经处理过的节点，保证下一次不会再被遍历到

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> used;     // store all the used nodes
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

动态规划

198 打家劫舍

一道入门的动态规划题，通过尝试法，尝试使用暴力递归完成题目，然后优化为动态规划算法

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

对于数组中的每一个位置（每一间房），我们都有两种选择：进入这间房/不进入这间房。

如果进入这间房：则和这间房相邻的房间必然不能进入

如果没有进入这间房： 则这间房相邻的房间可以随意进入

当我们遍历完整个数组的时候，我们才能知道所有房间的情况，包括我们该选择哪个房间，所以我们要从数组末尾开始进入递归。

当确认了最后一个房间的选择情况，我们就可以向前确认其他房间的情况，即从数组的末端向前方递归。

递归出口：

如果只有一个房间让小偷去偷，小偷的最大收获只能是这个房间的内容
如果有两个房间给小偷，小偷的最大收获是这两个房间中价值最高的那一个

设计递归函数：

在递归函数中我们需要传入数组（所有房间的选择），和一个变量 i（表示当前我们在考虑的是哪一间房子）

假设我们要传入的房子数组是 int[ ] houses = {2,7,9,3,1} ，则对于递归函数：process( int[ ] houses, int i )，

当i == 0的时候，应该返回==houses[0]==，

当i == 1的时候，应该返回==houses[0] 和hosues[1]中最大的那个==

当i为其他值的时候，我们要考虑当前i表示的房子要不要去偷，如果偷，那么上一间房子就不能去偷了：==返回 process(houses, i-2) + houses[i]==

如果不去偷，那么上一间房子就可以去偷：返回==process(houses, i-1)==

递归函数如下：

public int process(int[] nums, int i){
    if(i == 0){
        return nums[0];
    }

    if(i == 1){
        return Math.max(nums[0], nums[1]);
    }

    int A = process(nums, i-1); //不偷当前房子
    int B = process(nums, i-2)+nums[i]; //偷当前房子
    return Math.max(A, B); //选择两者中最大的值
}

递归的复杂度为O(2ⁿ)，递归的弊端

当我们来到第5间房间的时候，如果偷第5间房：需要计算==第3间房==的情况；如果不偷第5间房：需要计算第4间房的情况

当我们来到第4间房的时候，如果去偷第4间房：需要计算第2间房的情况；如果不偷第4间房：需要计算==第3间房==的情况

综上可见：在数组的遍历过程中，第3间房的情况被计算了两次，如果用一种方法将第3间房的值保存起来，就可以加速递归的过程

动态规划的解法：

准备一个dp数组dp[ ]，数组的长度即为房间的数量（因为我们不存在一个都不偷的情况）
我们要求的最后的结果即为dp[dp.length-1]，即走完所有的房子之后，我们才能知道最大收益可以是多少
当我们关注最后一个房间的情况（即dp[dp.length-1]）的时候，我们还需要考虑它的前一位和前两位的值
最终的迭代出口在数组的第0位和第1位
dp[0] = houses[0]，dp[1] = Math.max(houses[0], houses[1]）
从第二位开始，每一位的值 dp[ i ] 都是：Math.max ( dp[ i - 1] , dp[ i - 2 ] + houses[ i ] )
从第2位开始向后迭代，我们便可以将这个数组填满，取最后一位的值返回即可

public int rob(int[] nums) {
       if(nums == null || nums.length == 0){
           return 0;
       }
       if(nums.length == 1){
           return nums[0];
       }
       int[] dp = new int[nums.length]; //动态规划迭代法需要的数组
       dp[0] = nums[0]; //先将第0位和第1位填好
       dp[1] = Math.max(nums[0], nums[1]);
       for(int i = 2; i<nums.length; i++){
           int A = dp[i-1];
           int B = dp[i-2]+nums[i];
           dp[i] = Math.max(A,B);
       }
       return dp[nums.length-1];
   }

排序

堆排序


public class HeapSort {
    public static void main(String[] args) {
        int[] nums = {3, 5, 6, 1, 2, 7, 9, 8, 0, 4};
        sort(nums);
        System.out.println(Arrays.toString(nums));

    }

    /*
    1. 让数组整体形成大根堆
    2. 最后一个位置和堆顶位置交换， size-1
    3. 重新调整为大根堆
    4. 重复2-3步骤
    5. 直到 size == 0
     */
    public static void sort(int[] nums){
        if (nums == null || nums.length<2){
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            insert(nums, i);
        }
        int size = nums.length;
        while (size>0){
            swap(nums, 0, size-1);
            heapify(nums, 0, --size);
        }

    }
    /**
     * 每当顶部元素发生了改变，就进行一次堆化，将最大的值推到堆顶
     * @param nums
     * @param index
     * @param size
     */
    public static void heapify(int[] nums, int index, int size){
        int left;
        while((left = index*2+1)<size){
            int largestPos = (left+1)<size&&nums[left+1]>nums[left]?left+1:left;
            largestPos = nums[largestPos]>nums[index]?largestPos:index;
            if (largestPos == index){
                break;
            }
            swap(nums, largestPos, index);
            index = largestPos;
        }
    }
    /**
     * 每插入一个新的元素，都调整成大根堆
     * @param nums
     * @param index
     */
    public static void insert(int[] nums, int index){
        while(nums[index]>nums[(index-1)/2]){
            swap(nums, index, (index-1)/2);
            index = (index-1)/2;
        }
    }

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

归并排序


public class MergeSort {
    public static void main(String[] args) {
        int[] nums = {3, 5, 6, 1, 2, 7, 9, 8, 0, 4};
        sort(nums, 0, nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

    public static void sort(int[] nums, int L, int R){
        if (R == L){
            return;
        }

        int mid = (R+L)/2;
        sort(nums, L, mid);
        sort(nums, mid+1, R);
        merge(nums, L, R, mid);
    }

    public static void merge(int[] nums, int L, int R, int mid){
        int[] temp = new int[R-L+1];
        int p = 0;
        int p1 = L;
        int p2 = mid + 1;
        while(p1<=mid&&p2<=R){
            temp[p++] = nums[p1]<nums[p2]?nums[p1++]:nums[p2++];
        }

        //如果p2遍历完了
        while(p1<=mid){
            temp[p++] = nums[p1++];
        }
        //如果p1遍历完了
        while(p2<=R){
            temp[p++] = nums[p2++];
        }

        //将temp拷贝回nums中
        System.arraycopy(temp, 0, nums, L, temp.length);
    }
}

快速排序


public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {3,5,6,1,2,7,9,8,0,4};
        quickSort(nums, 0, nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

    public static void quickSort(int[] nums, int leftBound, int rightBound)	{
        if (leftBound>=rightBound){
            return;
        }
        int partition = partition(nums, leftBound, rightBound);
        quickSort(nums, leftBound, partition-1);
        quickSort(nums, partition+1, rightBound);

    }

    public static int partition(int[] nums, int leftBound, int rightBound){
        int pivot = rightBound;
        int p1 = leftBound;
        int p2 = rightBound-1;
        while (p1<=p2){
            while(p1<=p2&&nums[p1]<=nums[pivot]) p1++;
            while(p1<=p2&&nums[p2]>nums[pivot]) p2--;
            if (p1<p2){
                swap(nums, p1, p2);
            }
        }
        swap(nums, p1, pivot);
        return p1;
    }

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

桶排序

补充问题

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度位O(N)，且要求不能用非基于比较的排序

题解：

总体：利用桶排序的思想，将数据分类，但是核心的排序方法仍是基于比较的排序

步骤：

面对n个元素的数组，创建辅助数组，长度为n+1，主要是为了用于记录每个桶中的最大值，最小值，是否加入了新的元素。
为什么桶的数量为n+1:

为了保证最大gap不会出现在桶内（max-min），而是相邻两个有数据的桶之间的gap（下一个桶的最小值-上一个桶的最大值）
求出整个数组中的最大值和最小值，通过入桶算法，求出每一个元素应该进的桶号
将每个元素入桶
创建一个全局变量gap
遍历所有的桶，计算下一个桶最小值和当前桶的最大值的差值，根据大小情况更新gap
最后返回的gap即是全局最大的gap

源代码：


public class MaxGap {
    public static void main(String[] args) {
        int[] nums = RandomArrayGenerator.generate(100,100);
        System.out.println(truthValue(nums));
        System.out.println(solution(nums));
    }

    public static int solution(int[] nums){
        //n个数，创建n+1个桶
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        //取出了数组的最大最小值
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        if (min == max){
            return 0;
        }
        //创建3个辅助数组
        boolean[] hasNum = new boolean[nums.length+1];
        int[] maxValue = new int[nums.length+1];
        int[] minValue = new int[nums.length+1];
        //重新遍历数组，将数值填入辅助数组的桶中
        int bucket = 0;
        for (int i = 0; i < nums.length ; i++) {
            //用算法求出当前数应该在哪个桶中
            bucket = bucket(nums[i], nums.length, min, max);
            //如果桶中还没有值，就将最小值置为nums[i],如果有了，就取两者之间的最小值
            minValue[bucket] = hasNum[bucket]?Math.min(minValue[bucket],nums[i]):nums[i];
            maxValue[bucket] = hasNum[bucket]?Math.max(maxValue[bucket],nums[i]):nums[i];
            //此时肯定已经有值了，将boolean置为true
            hasNum[bucket] = true;
        }

        //桶装好后，开始找最大值,遍历所有的桶。最大值发生在相邻两个数组之间，后一个数组的min-前一个数组的max
        int res = 0;
        int lastMax = maxValue[0];
        for (int i = 1; i < nums.length+1; i++) {
            if (hasNum[i]){
                res = Math.max(res, minValue[i]-lastMax);
                lastMax = maxValue[i];
            }
        }
        return res;
    }

    /**
     *
     * @param num 当前数
     * @param len 一共有几个数
     * @param min 数组中最小值
     * @param max 数组中最大值
     * @return 当前数应该在第几个桶
     */
    public static int bucket(long num, long len, long min, long max){
        return (int)((num-min)*len/(max-min));
    }

    //用于校验结果的正确性
    public static int truthValue(int[] nums){
        Arrays.sort(nums);
        int gap = 0;
        for (int i = 1; i < nums.length; i++) {
            gap = Math.max(gap, nums[i]-nums[i-1]);
        }
        return gap;
    }

}

347 出现频率最多的k个元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

算法1：

通过HashMap将数组中的元素和其出现的次数对应起来
通过优先级队列（堆）根据出现次数从大到小排序
通过k次迭代从堆顶拿出k个数

算法2：

第一步同上
准备一个桶数组（数组由nums.length()+1个List组成，目的是为了使得下标和频次对应）
遍历Map中的Entry，将桶数组填好，天然的，桶数组右侧的元素频次大于左侧
从桶数组的右侧开始遍历，如果当前桶不为空，就遍历桶中的元素，加入到结果中，直到满足数量为k

public static int[] topKFrequent(int[] nums, int k){
       //用来存储每个不同的数字和它出现的次数
       HashMap<Integer, Integer> map = new HashMap<>();
       for(int n : nums){
           map.put(n, map.getOrDefault(n, 0)+1);
       }
       //准备一个桶数组List[]，下标表示频率，每个桶中的列表存储当前频率下的数值
       ArrayList<Integer>[] buckets = new ArrayList[nums.length+1];
       for (Map.Entry<Integer, Integer> en:map.entrySet()
            ) {
           int num = en.getKey();
           int times = en.getValue();
           if(buckets[times] == null){
               //如果当前频率下的元素不存在，就初始化这个列表
               buckets[times] = new ArrayList<>();
           }
           buckets[times].add(num);//在当前频率的桶中加入符合该频率的数值
       }
   
       //结果数组
       int[] res = new int[k];
       int index = 0;
       a:for(int i = buckets.length-1; i>=0; i--){//遍历整个桶数组
           if(buckets[i] == null){//如果当前桶为空，说明当前频率下没有元素在其中
               continue;
           }
           b:for (int num:buckets[i]//如果当前桶非空，就将桶中的元素一个一个加入到结果数组中
                ) {
               res[index++] = num;//随着元素的加入，结果数组的指针在不断增加
               if (index == res.length){//如果结果数组的指针越界了，说明结果数组已满，直接终止外层循环
                   break a;
               }
           }
       }
       return res;
   }

数据结构

栈

1.1 用数组实现创建栈

1.2 补充问题

设计一个栈，在实现栈的基础功能的前提下，实现返回栈中最小元素的操作

要求：

（1）pop， push， getMin的复杂度都是O(1)

（2）设计的栈类型可以使用现成的栈结构

题解：

准备两个栈：一个普通栈，一个只存储最小值的栈（minStack）
压栈的时候，同时压入第一个元素
压入第二个及以上元素：普通栈正常压，如果此时的元素<minStack的栈顶，将此元素压入，否则重复压入minStack的栈顶
弹出元素：同时弹出两个栈的栈顶


public class NewStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int num){
        stack.push(num);
        if (minStack.size() == 0){
            minStack.push(num);
        }else {
            minStack.push(Math.min(num, this.getMin()));
        }
    }

    public int getMin(){
        if (stack.size() == 0){
            throw new ArrayIndexOutOfBoundsException("栈已空");
        }
        return minStack.peek();
    }

    public int pop(){
        if (stack.size() == 0){
            throw new ArrayIndexOutOfBoundsException("栈已空");
        }
        minStack.pop();
        return stack.pop();
    }

    public static void main(String[] args) {
        NewStack newStack = new NewStack();
        newStack.push(1);
        newStack.push(2);
        newStack.push(3);
        newStack.push(4);
        newStack.push(5);
        newStack.push(0);
        System.out.println("Before pop:----------");
        System.out.println(newStack.getMin());
        newStack.pop();
        System.out.println("After pop:-----------");
        System.out.println(newStack.getMin());
    }
}

1.3 用队列实现栈

要求：只用队列结构实现栈

题解：

准备两个队列，一个是data，一个是help
添加元素的时候总是向data队列中添加元素
要取出元素的时候：（先进后出，后进先出），将data队列中的所有元素除了最后一个元素都添加到help队列中，返回data中的最后一个元素
交换两个队列，即help队列变成了新的data队列
如果只是访问栈顶元素，则同上，但是将data的最后一个元素也push进help中，交换两个队列

import java.util.LinkedList;
import java.util.Queue;

public class TwoQueueStack {
    private Queue<Integer> data;
    private Queue<Integer> help;

    public TwoQueueStack() {
        this.data = new LinkedList<>();
        this.help = new LinkedList<>();
    }

    public void push(int num){
        data.add(num);
    }

    public int peek(){
        if (data.isEmpty()){
            throw new RuntimeException("Stack is empty");
        }
        while(data.size()>1){
            help.add(data.poll());
        }
        int res = data.poll();
        help.add(res);
        swap();
        return res;

    }

    public int pop(){
        if (data.isEmpty()){
            throw new RuntimeException("Stack is empty");
        }
        while (data.size()>1){
            help.add(data.poll());
        }
        int res = data.poll();
        swap();
        return res;
    }

    public void swap(){
        Queue<Integer> temp = data;
        data = help;
        help = temp;
    }

    public String toString(){
        return data.toString();
    }

    public static void main(String[] args) {
        TwoQueueStack stack = new TwoQueueStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        //按顺序弹出栈顶
        for (int i = 0; i < 6; i++) {
            System.out.println(stack.pop());
            System.out.println(stack);
            System.out.println("--------------");
        }
    }
}

1.4 用栈实现队列

要求：只用栈实现队列

算法：

准备两个栈：push栈，pop栈

push栈用于加入元素，pop栈用于弹出元素
加入元素的时候直接将元素加入push栈中
在取出元素之前，先调用pour方法：

pour方法：

将push栈中的元素都弹进pop栈中，目的是为了颠倒取出元素的顺序

注意：

pour的条件：
1. 如果pop栈中还有元素，就不能将push中的元素加入pop中
2. 如果决定要将push栈中的元素倒入pop栈中，则一次性倒完


import java.util.Stack;

public class TwoStackQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    public TwoStackQueue() {
        this.pushStack = new Stack<>();
        this.popStack = new Stack<>();
    }

    public void add(int num){
        pushStack.push(num);
    }

    public int pull(){
        pour();
        if (popStack.isEmpty()){
            throw new RuntimeException("The queue is empty");
        }
        return popStack.pop();
    }

    public int peek(){
        pour();
        if (popStack.isEmpty()){
            throw new RuntimeException("The queue is empty");
        }
        return popStack.peek();
    }

    /**
     * 将push栈中的元素加入pop栈中
     */
    public void pour(){

        //如果pop栈不为空，则一定不能将push栈中的元素加进来
        if (!popStack.isEmpty()){
            return;
        }
        while(!pushStack.isEmpty()){
            popStack.push(pushStack.pop());
        }
    }

    public String toString(){
        return popStack.toString();
    }


    public static void main(String[] args) {
        TwoStackQueue queue = new TwoStackQueue();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);

        for (int i = 0; i < 5; i++) {
            System.out.println(queue.pull());
            System.out.println(queue);
            System.out.println("-------------");
        }
    }
    /*
    1
    [5, 4, 3, 2]
    -------------
    2
    [5, 4, 3]
    -------------
    3
    [5, 4]
    -------------
    4
    [5]
    -------------
    5
    []
    -------------
     */
}

1.5 猫狗队列

题解：

构建两个队列：猫队列和狗队列，这样可以方便的分别按照顺序弹出相应的宠物
如何在pollAll方法中做到两种宠物按照共同的时间进行排列呢？

给每一个加入队列中的宠物添加时间戳：

注意：不能修改宠物类，不能给宠物类添加新的属性

解决方案：添加一个新的包装类，将Pet对象和一个计数变量包装起来
pollAll方法：比较两个队列顶部元素的时间戳大小，将时间戳小的弹出，当其中一个队列为空的时候，直接弹出另一个队列的元素即可
继续完成pollCat和pollDog和其他简单方法

package 练习.队列.猫狗队列;

import java.util.LinkedList;
import java.util.Queue;

public class CatDogQueue {
    public static class Pet {
        private String type;

        public Pet(String type) {
            this.type = type;
        }

        public String getType() {
            return type;
        }
    }

    public static class Dog extends Pet {
        public Dog() {
            super("Dog");
        }
    }

    public static class Cat extends Pet {
        public Cat() {
            super("Cat");
        }
    }


    public static class PetEnter{
        private Pet pet;
        private int count;

        public PetEnter(Pet pet, int count) {
            this.pet = pet;
            this.count = count;
        }

        public Pet getPet() {
            return pet;
        }

        public int getCount() {
            return count;
        }

        public String getEnterPetType(){
            return pet.getType();
        }
    }

    public static class PetQueue{
        private Queue<PetEnter> catQueue;
        private Queue<PetEnter> dogQueue;
        private int count;


        public PetQueue() {
            this.catQueue = new LinkedList<>();
            this.dogQueue = new LinkedList<>();
            this.count = 0;
        }

        public void add(Pet pet){
            if (pet.getType() .equals("Dog")){
                dogQueue.add(new PetEnter(new Dog(), count++));
            }else if (pet.getType().equals("Cat")){
                catQueue.add(new PetEnter(new Cat(), count++));
            }else {
                throw new RuntimeException("Not dog or cat!");
            }
        }

        public Pet pollAll(){
            if (!dogQueue.isEmpty()&&!catQueue.isEmpty()){
                return dogQueue.peek().count<catQueue.peek().count?dogQueue.poll().getPet():catQueue.poll().getPet();
            }
            else if (!dogQueue.isEmpty()){
                return dogQueue.poll().getPet();
            }
            else if (!catQueue.isEmpty()){
                return catQueue.poll().getPet();
            }else {
                throw new RuntimeException("The queue is empty!");
            }
        }

        public Pet pollCat(){
            if (catQueue.isEmpty()){
                throw new RuntimeException("CatQueue is empty!");
            }
            return catQueue.poll().getPet();
        }

        public Pet pollDog(){
            if (dogQueue.isEmpty()){
                throw new RuntimeException("DogQueue is empty");
            }
            return dogQueue.poll().getPet();
        }

        public boolean isEmpty(){
            return dogQueue.isEmpty()&&catQueue.isEmpty();
        }

        public boolean isCatEmpty(){
            return catQueue.isEmpty();
        }

        public boolean isDogEmpty(){
            return dogQueue.isEmpty();
        }
    }
}

1.6 宏观调度问题

1.6.1 矩阵旋转

要求：在空间复杂度为O(1)的前提下，将矩阵旋转90度

算法：

从外向内逐层旋转

旋转的方法：

代码：


public class RotateMatrix {
    public static void rotate(int[][] m){
        //左上角
        int a = 0;
        int b = 0;
        //右下角
        int c = m.length-1;
        int d = m[0].length-1;

        while(a<c){
            rotateEdge(m, a++,b++,c--,d--);
        }
    }

    public static void rotateEdge(int[][] m, int a, int b, int c, int d){
        //循环次数
        int times = d - b;
        for (int i = 0; i < times; i++) {
            int temp = m[a][b+i];
            m[a][b+i] = m[c-i][b];
            m[c-i][b] = m[c][d-i];
            m[c][d-i] = m[a+i][d];
            m[a+i][d] = temp;
        }

    }

    public static void matrixPrint(int[][] m){
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[0].length; j++) {
                System.out.print(m[i][j]+"\t");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1,2,3,4},
                {5,6,7,8},
                {9,10,11,12},
                {13,14,15,16}
        };
        System.out.println("旋转之前---------");
        matrixPrint(matrix);
        rotate(matrix);
        System.out.println("旋转之后---------");
        matrixPrint(matrix);

    }
}
/*
旋转之前---------
1	  2	  3	  4	
5	  6	  7	  8	
9	  10	11	12	
13	14	15	16	
旋转之后---------
13	9 	5	  1	
14	10	6	  2	
15	11	7	  3	
16	12	8	  4
*/

1.6.2 之字形打印矩阵

要求：之字形打印数组中的元素

算法：

从左上角开始，准备两个点A和B
A向右跑，B向下跑
A到达最右端后，向下移动，B到达最下端后向右移动
用一个算法打印出A和B之间的数字（以AB为端点的对角线）

在算法中：

先更新A的row，再更新A的col
先更新B的col，再更新B的row

代码

在算法中：

* 先更新A的row，再更新A的col
* 先更新B的col，再更新B的row

代码

1.6.3 在行和列都排好序的矩阵中找数

要求：给定的M*N矩阵已经有序，现在给一个K，判断K是否在矩阵中

时间复杂度为O(M+N), 空间复杂度为O(1)

算法：

从矩阵的右上角开始，如果当前值大于K，则向左移动；如果当前值小于K，向下移动；否则当前值就是K，返回true
终止条件，指针移动到了左下角都没有找到K，返回false
边界条件：移动到右下角后，当前数<K，直接返回false；移动到左上角后，当前数>K，直接返回false（最大值都比K小，说明K肯定不在矩阵的范围内，同理最小值也是如此）

代码：

package 练习.从有序矩阵中寻找K;

/**
 * @program: leetcode
 * @description
 * @author: ClarkLevis
 * @create: 2020-12-02 08:45
 **/
public class FindK {

    public static void main(String[] args) {
        int[][] matrix = {
                {1,3,5,6},
                {2,5,7,9},
                {4,6,8,10}
        };
        System.out.println(findK(matrix,12));
    }

    public static boolean findK(int[][] matrix, int k){
        //从右上角开始寻找，如果当前数大于K，则该列中的数都会比K大，切换到前一列
        int row = 0;
        int col = matrix[0].length-1;
        //边界条件：如果k不在当前矩阵范围内，返回false
        if (k<matrix[0][0] || k>matrix[matrix.length-1][matrix[0].length-1]){
            return false;
        }
        //终止条件：到达左下角
        while(!(row == matrix.length-1&& col == 0)){
            if (matrix[row][col] > k){
                col--; // 因为已经确定了边界条件，这里不会出现越界问题了
            }else if (matrix[row][col] == k){
                return true;
            }else {
                while(row<matrix.length){
                    if (matrix[row][col] == k){
                        return true;
                    }else if(matrix[row][col] < k){
                        row++;// 因为已经确定了边界条件，这里不会出现越界问题了
                    }else {
                        col--;
                        break;
                    }
                }
            }
        }
        return false;
    }
}

1.7 链表题目

1.7.0 链表生成器

//可以根据一个数组生成对应数值的链表，并且可以根据链表的样子打印出来
public static class Node{
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            StringBuilder result = new StringBuilder();
            Node temp = this;
            while(temp!=null){
                result.append(temp.next==null?temp.val:temp.val+" -> ");
                temp = temp.next;
            }
            return result.toString();
        }
    }

    public static Node linkGenerator(int[] nums){
        Node head = new Node(nums[0]);
        Node temp = head;
        for (int i = 1; i < nums.length; i++) {
            temp.next = new Node(nums[i]);
            temp = temp.next;
        }
        return head;
    }

1.7.1 找到链表中的相同节点

题目：给定两个有序链表头指针head1和head2，打印两个链表的公共部分

算法：外部排序（Merge过程）

1.7.2 判断一个链表是不是回文结构

题目：

算法1：

遍历链表，将node加入栈中，再遍历栈，和原始链表比对，如果相等，说明是回文链表

算法1增强版：

快慢指针：当快指针走到结尾的时候，慢指针走到中点的下一个位置
将慢指针和之后的节点压栈
弹栈，和链表的前半部分比较

算法2：

快慢指针：当快指针走到结尾的时候，慢指针走到中点
逆序从慢指针开始的后半部分
新建两个指针从头和尾遍历，到终点node为止
如果都相等，返回true，否则返回false
最后再将后半部分恢复回来

package 练习.回文链表;

import java.util.Stack;

/**
 * @program: leetcode
 * @description
 * @author: ClarkLevis
 * @create: 2020-12-02 10:34
 **/
public class Palindrome {
    public static void main(String[] args) {
        Node head = linkGenerator(new int[]{1,2,3,4,5,5,4,3,2,1});
        System.out.println(head);
        System.out.println(isPalindrome3(head));
    }

    //空间复杂度为n
    public static boolean isPalindrome1(Node head){
        Stack<Integer> stack = new Stack<>();
        Node pointer = head;
        while (pointer!=null){
            stack.push(pointer.val);
            pointer = pointer.next;
        }
        pointer = head;
        while (!stack.isEmpty()){
            if (stack.pop()!=pointer.val){
                return false;
            }
            pointer = pointer.next;
        }
        return true;
    }

    //空间复杂度为n/2
    public static boolean isPalindrome2(Node head){
        if (head == null || head.next == null){
            return true;
        }
        Node slow = head.next;//注意这里慢指针的初始位置
        Node fast = head;

        //当循环终止时，fast在最后一位（奇数），或者在倒数第二位（偶数）
        //slow在中间位置的下一位（奇数）1->2->3->(2)->1，或者在中间相等两数的第二个数（偶数）1->2->3->(3)->2->1
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //将此时从slow开始的链表压栈
        Stack<Integer> stack = new Stack<>();
        while (slow!=null){
            stack.push(slow.val);
            slow = slow.next;
        }

        while(!stack.isEmpty()){
            if (head.val != stack.pop()){
                return false;
            }
            head = head.next;
        }
        return true;
    }

    //空间复杂度为O(1)
    public static boolean isPalindrome3(Node head){
        if (head == null || head.next == null){
            return true;
        }

        Node n1 = head;//慢指针
        Node n2 = head;//快指针
        //慢指针移动到中点，或者中间偏左的位置（偶数）
        while(n2.next!=null&&n2.next.next!=null){
            n1 = n1.next;
            n2 = n2.next.next;
        }
        //开始反转后半部分的链表
        n2 = n1.next;
        n1.next = null;//mid.next = null
        Node n3 = null;
        while(n2!=null){
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }

        //两个节点分别从两端遍历，查看每个节点的相等情况
        n3 = n1;
        n2 = head;
        boolean res = true;
        while (n1!=null&&n2!=null){
            if (n1.val!=n2.val){
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }

        //再将后半部分的链表反转回来
        n1 = n3.next;
        n3.next = null;
        while(n1!=null){
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }
}

1.7.2 链表的荷兰国旗问题

要求：给定一个链表和一个数字，将比这个数字小的节点放在左边，比这个数字大的节点放在右边，和这个数字相等的节点放在中间

时间复杂度为O(N)，空间复杂度为O(1)

1.7.3 复制含有随机指针节点的链表

题目：在链表的结点中，除了val，next之外，还有一个类型为Node的随机指针，它可能指向链表中的任何一个节点，也可能指向null

算法1：

使用HashMap ：

将原链表中的节点作为key，将copy后的节点作为value，放入HashMap中。
重建新的链表
通过映射关系，重建rand关系：1’和 2’之间的关系可以通过1和2之间的关系得到

需要额外空间

代码：


public class DeepCopy {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.rand = head;
        head.next.next.rand = null;


    }

    //需要额外的存储空间
    public static Node copyListWithRand1(Node head){
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while(cur!=null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while(cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

}

class Node{
    int val;
    Node next;
    Node rand;

    public Node(int val) {
        this.val = val;
    }
}

算法2：不用HashMap

空间复杂度为O(1)

通过第一次遍历，将原来的链表：

每个copy节点都连接在原节点的后面

当确定rand或者next关系的时候，首先通过原来链表的rand关系找到（1找到2），因为2’就在2的下一位，所以1’可以直接找到2’（通过这种结构关系，巧妙地避免了HashMap的使用）
最后，分离混合的链表（在这里面重新确定next关系）

代码：

//不需要额外的存储空间
    public static Node copyListWithRand2(Node head){
        Node cur = head;
        Node next = null;
        //构造出 1 -> 1 -> 2 -> 2 -> 3 -> 3 这种结构
        while(cur!=null){
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        //设置 “复制Node”的rand指针
        while(cur!=null){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand == null? null:cur.rand.next;
            cur = next;
        }

        Node res = head.next;
        cur = head;
        //分离混合在一起的链表
        while(cur!=null){
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next==null?null:next.next;
            cur = next;
        }
        return res;
    }

1.7.4 两个链表相交的一系列问题

题目：

算法：

因为是单链表，所以右图的情况是不可能的

首先判断两个链表是否有环（用下面问题的方法）
则分别求出他们的入环节点loop1和loop2
如果没有环（loop1 == null ，loop2 == null），通过遍历每个节点，维护两个变量：len和endNode
- 如果endNode1!=endNode2，两个链表不相交；否则相交
- 如果相交，则比较len
  - 如果len1-len2 = 10，则先让链表1遍历10个node，然后两个链表一起遍历，相遇的节点就是交叉的第一个节点
如果两个一个链表有环一个链表无环，不可能相交（loop1 ，loop2中有一个为null）

如果两个链表都有环（loop!=null loop2!=null）：

各自成环，不相交
先相交，再共享一个环（loop1 == loop2）
从环上两个地方切入

public static Node getIntersectNode(Node head1, Node head2){
        if (head1 == null || head2 == null){
            return null;
        }
        if (head1 == head2){
            return head1;
        }
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if (loop1 == null && loop2 == null){
            return noLoop(head1, head2);
        }else if(loop1 != null&&loop2 != null){
            return bothLoop(head1, head2, loop1, loop2);
        }else {
            return null;
        }
    }

    public static Node getLoopNode(Node head){
        if (head == null || head.next == null || head.next.next == null){
            return null;
        }
        //两个只针的位置要错开
        Node fast = head.next.next;
        Node slow = head.next;
        //第一次重合
        while(fast != slow){
            if (fast.next == null||fast.next.next==null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        //重合后，快指针放回head
        fast = head;
        //寻找第二次重合
        while (fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        //返回当前重合节点
        return fast;
    }

    public static Node noLoop(Node head1, Node head2){
        if (head1 == null || head2 == null){
            return null;
        }
        //遍历head1
        int len1 = 0;
        Node endNode1 = null;
        Node cur = head1;
        while(cur != null){
            if (cur.next == null){
                endNode1 = cur;
            }
            len1++;
            cur = cur.next;
        }
        //遍历head2
        int len2 = 0;
        Node endNode2 = null;
        cur = head2;
        while(cur != null){
            if (cur.next == null){
                endNode2 = cur;
            }
            len2++;
            cur = cur.next;
        }
        //结尾节点不相等，肯定不相交
        if (endNode1!=endNode2){
            return null;
        }
        //结尾节点相等
        //长的链表先遍历sub步
        Node longerHead = len1>len2?head1:head2;
        Node shorterHead = len1>len2?head2:head1;
        int sub = len1>len2?len1-len2:len2-len1;

        for (int i = 0; i < sub; i++) {
            longerHead = longerHead.next;
        }
        while(longerHead!=shorterHead){

            longerHead = longerHead.next;
            shorterHead = shorterHead.next;
        }
        return longerHead;
    }

    public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2){

        if (loop1 == loop2){
            int len1 = 0;
            Node cur1 = head1;
            while(cur1 != loop1){
                len1++;
                cur1 = cur1.next;
            }

            //遍历head2
            int len2 = 0;
            Node cur2 = head2;
            while(cur2 != loop1){
                len2++;
                cur2 = cur2.next;
            }
            //结尾节点相等
            //长的链表先遍历sub步
            Node longerHead = len1>len2?head1:head2;
            Node shorterHead = len1>len2?head2:head1;
            int sub = len1>len2?len1-len2:len2-len1;

            for (int i = 0; i < sub; i++) {
                longerHead = longerHead.next;
            }
            while(longerHead!=shorterHead){

                longerHead = longerHead.next;
                shorterHead = shorterHead.next;
            }
            return longerHead;
        }

        Node cur = loop1.next;
        while (cur!=loop1){
            if (cur == loop2){
                return loop2;
            }
            cur = cur.next;
        }
        return null;
    }


    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

1.7.5 判断一个单链表是否有环（若有环，将环的起点返回）

算法1：快慢指针：

如果两个指针重合，说明这个链表有环；如果其中一个指针遇到了null，则必然无环。
当两个指针重合后，快指针回到起点，速度变为1步每次，则两个指针一定会在环的起点相遇

注意：快慢指针的起点：

要么都在起点（推荐）

Node fast = head;
     Node slow = head;
     while(true){
         fast = fast.next.next;
         slow = slow.next;
         if (fast == slow){
             break;
         }
     }

要么在起点的下两个位置

Node fast = head.next.next;
      Node slow = head.next;
      while(fast != slow){
          fast = fast.next.next;
          slow = slow.next;
      }

否则：在寻找环入口的时候可能会陷入死循环

算法2：HashMap：遍历链表，每次将node存进表中，如果第一次出现了重复的node，就返回这个node

二叉树相关问题

1 二叉树的遍历

1.7.1 二叉树的递归遍历

1.7.2 二叉树的非递归遍历

栈：为什么用栈：

栈是一个可以反向输出的结构，因为二叉树的遍历一定是从上往下遍历每一个节点，是单向的，但是在递归中，子节点遍历完后可以返回父节点，形成了反向的遍历，这时候选择栈结构比较合适。而且递归本身就是一个方法栈。

先序遍历：

算法：

准备一个栈
将头节点压进去
弹出头节点，打印，如果有的话，将右节点压入，再将左节点压入
如果最后一个元素弹出，且没有新的节点加入，说明遍历完成，栈已空

public static void preOrderNoRecur(Node head){
        if (head != null){
            Stack<Node> stack = new Stack<>();
            Node cur = head;
            stack.push(cur);
            while(!stack.isEmpty()){
                cur = stack.pop();
                System.out.print(cur.value+" ");
                if (cur.right!=null){
                    stack.push(cur.right);
                }
                if (cur.left!=null){
                    stack.push(cur.left);
                }
            }
        }
    }

中序遍历：

算法：

如果栈不为空或者当前节点不为null，开始执行
如果当前节点不为null：不停的将该节点的left 节点压栈，直到当前节点为null
如果当前节点为null，但是stack不为空，开始弹栈，当前节点为弹出的节点，打印
当前（如果当前节点有right子节点）节点变为right子节点
直到栈为空且当前节点为空，终止

public static void inOrderNoRecur(Node head){
        if (head!=null){
            Stack<Node> stack = new Stack<>();
            Node cur = head;
            while(!stack.isEmpty() || cur != null){
                //如果当前节点不为空，一直将当前节点和左子节点压入栈中
                if (cur!=null){
                    stack.push(cur);
                    cur = cur.left;
                }else {
                    cur = stack.pop();
                    System.out.print(cur.value+" ");
                    cur = cur.right;
                }
            }
        }
    }

直观逻辑：

将包括当前节点在内的左边树全部压入栈中-->压入完成
弹出栈顶元素，如果这个元素有右子节点，将包括右子节点在内的，以右子节点为首的左边树压入栈中-->压入完成
继续弹出栈顶元素

后序遍历

算法：

用两个栈，实现相反的先序遍历

考虑到：在先序遍历中，首先会pop头节点，然后将右节点和左节点压栈（因为栈会反向输出，所以输出顺序为左-右）
如果将输出变为压入另一个栈，pop头节点后，将先将左节点压栈，再压右节点，之后弹出的时候顺序就为右-左
所以会以中-右-左的顺序压入第二个栈
遍历第二个栈，就会以左-右-中的方式弹出

public static void posOrderNoRecur(Node head){
        if (head != null){
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            Node cur = head;
            stack1.push(cur);
            while(!stack1.isEmpty()){
                cur = stack1.pop();
                stack2.push(cur);
                if (cur.left!=null){
                    stack1.push(cur.left);
                }
                if (cur.right!=null){
                    stack1.push(cur.right);
                }
            }
            while(!stack2.isEmpty()){
                System.out.print(stack2  .pop().value+" ");
            }
        }
    }

2.0 打印一棵二叉树

2.1 寻找二叉树的后继节点和前驱节点

2.2 二叉树的序列化和反序列化

序列化即是将二叉树的节点变成字符串，而且后期可以恢复回来

2.2.1 通过先中后序遍历将节点都序列化

用相同的方式来反序列化

2.2.2 通过层序遍历将节点序列化

2.3 判断一棵树是平衡二叉树

对于任何一个节点，如果左子树的高度和右子树的高度差不超过1，就是平衡的

套路：因为递归可以经过一个节点三次（第一次；左子树返回（第二次）；右子树返回（第三次）），所以我们可以收集到两个子节点的信息再返回到父节点

算法：

如果以每一个节点为头节点的子树都是平衡的，那么整棵树就是平衡的

左树是否平衡
右树是否平衡
左树高度h1，和右树高度h2比较，看是否平衡
设计递归返回结构（1. 当前子树的高度 2. 当前子树是否平衡），这两个信息需要返回给父节点（可以构建一个返回类）

public static class ReturnValue{
        boolean isBalance;
        int height;

        public ReturnValue(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

用递归列出所有的可能性：

public static ReturnValue process(Node head){
    //如果根节点是null，则这个子树是平衡的
        if (head == null){
            return new ReturnValue(true, 0);
        }
        ReturnValue leftValue = process(head.left);
        ReturnValue rightValue = process(head.right);
	//如果左子树不平衡，这棵树就不平衡
        if (!leftValue.isBalance){
            return new ReturnValue(false,0);
        }
    //如果右子树不平衡，这棵树就不平衡
        if (!rightValue.isBalance){
            return new ReturnValue(false,0);
        }
    //如果左右高度差大于1，这棵树就不平衡
        if (Math.abs(rightValue.height-leftValue.height)>1){
            return new ReturnValue(false,0);
        }
    //则目前子树平衡，返回这个子树的相关信息
        return new ReturnValue(true, Math.max(rightValue.height, leftValue.height)+1);
    }

图解：

2.4 如何判断一棵树是搜索二叉树

右子树比当前节点都大，左子树比当前节点都小，而且通常是没有重复节点的

判断标准：一棵树的中序遍历结果是依次升序的，就是搜索二叉树

2.5 如何判断一棵树是完全二叉树

判断逻辑：

二叉树的按层遍历

如果一个Node只有右节点没有左节点，返回false，一定不是完全二叉树
如果一个Node只有左节点，或者没有子节点，那么后面遇到的所有节点都必须是叶子节点（层序遍历），否则一定不是完全二叉树
以上都可以保证，就是完全二叉树

public static boolean isCBT(Node head){
        if (head == null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        boolean beginLeaf = false;//是否进入之后的节点都是叶子节点模式？
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            Node left = cur.left;
            Node right = cur.right;
            //这一条判断语句将两个条件都进行了判断
            if (beginLeaf&&(left!=null || right!=null) || left==null&&right!=null){
                return false;
            }
            //层序遍历，将子节点都加进来
            if (left!=null){
                queue.offer(left);
            }
            if (right!=null){
                queue.offer(right);
            }
            //如果出现左√右x的情况，开启叶子节点模式
            if (left!=null&&right==null){
                beginLeaf = true;
            }
        }
        return true;
    }

2.5.1 求完全二叉树节点的个数

要求：如果二叉树的节点个数为n，时间复杂度应该低于O(n)

已知情况：如果满二叉树的层数为 L，那么这棵二叉树的节点数量为 2^L-1；如果一棵二叉树有n个节点，那么它的层数为log（n）

算法：

先遍历head的左边界，可以得到二叉树的层数L
遍历head右子树的左边界：
1. 如果右子树的左边界到了最后一层，那么这个head节点的左子树是满的：左树的高度就为L-1，可以求得左树的节点数：2^(L-1) -1，加上头节点为 2^(L-1) 。递归去求右子树的节点个数（其中这个L-1中的1是变化的，表示的是当前head节点所在的层数）
2. 如果右子树左边界没有到最后一层，那么右子树一定是满的，只是高度为L-1-1。可以求得右子树的节点个数为2^(L-1-1) -1，加上头节点为2^(L-1-1) ，递归左子树的节点个数

代码：

//求出以当前节点为头节点的子树的最大深度（绝对深度）
/**
     *
     * @param head 当前节点
     * @param level 当前节点所在的层数
     * @return 返回当前节点最深层的左节点的层数（相对于整棵树的层数）
     */
public static int mostLeftLevel(Node node, int level){
    while(node!=null){
        level++;
        node = node.left;
    }
    return level;
}

/**
     *
     * @param node 当前被处理的节点
     * @param level 当前节点所在的层数
     * @param h 整棵树的最大层数
     * @return 当前节点为头节点的子树的节点数
     */
public static int process(Node node, int level, int h){
    //如果当前节点到达了最大深度，肯定没有子节点了
    if(level == h){
        return 1;
    }
    //右子树的深度到达了最大深度,则左子树一定是满二叉树
    if(mostLeftLevel(node.right, level+1) == h){
        return (1<<(h-level))+process(node.right, level+1, h);
    }else{//右子树的深度没有到达最大深度，右子树一定是满二叉树
        return (1<<(h-level-1))+peocess(node.left, level+1, h);
    }
}

//计算最终的节点数量
public static int nodeCount(Node head){
    if(head == null){
        return 0;
    }
    return process(head, 1, mostLeftLevel(head, 1));
}

时间复杂度分析：

每一层遍历一个节点（只遍历那个具有满二叉树的节点）一共有n个节点，logn层，复杂度为logn
判断深度的时候，只遍历右子树的左边界，依旧是logn
所以一共是log²n的复杂度

哈希函数和哈希表

1 哈希函数

性质：

输入域：无穷大
输出域：固定大小
相同的输入必定会有相同的hashcode
存在不同输入对应相同hashcode的情况
hashcode具有离散型（而且和输入没有关系，可以打乱输入规律）
如果hashcode是均匀分布的，那么对hashcode取余之后，结果也是均匀分布的
hashcode中每一位和其他位都是相互独立的

默认：哈希表的增删改查是O(1)的

1.1 大数据类型问题

利用hash函数来对大文件进行分流

1.2 设计RandomPool结构

算法：

注意：要求是等概率，而且时间复杂度还要是O(1)，等概率考虑到使用随机数生成，但是需要index，所以想到Map结构；在删除操作中可能会在0~size-1之间产生一个洞，所以需要用最后一位来填

准备两个Map，一个全局变量size。第一个map用于存放key和index，其中index是我们自己用来构建索引的；第二个map用于存放index和key，其中index是用来通过随机数获取key的
add操作：map1中，加入<String1， index1>， map2中加入<index1， String1>， size++
当需要getRandom的时候，用Math.Random()*size获得 [0, size) 区间内的随机一个数，从map2中查找
当进行remove(key)操作的时候，将map1的最后一位覆盖key对应的一位，将map2的最后一位覆盖key对应的一位，然后将最后一条数据删除， size- -

2 布隆过滤器

应用场景：爬虫去重问题，黑名单问题

布隆过滤器存在的问题：宁可错杀3000，也不放过1人（会存在比较低的失误率）

底层为一个bit数组

2.1 在一个32000bit长的数组中，如何将第30000个位置的bit置1？

int[] arr = new int[1000];
int index = 30000;
int intIndex = index/32;
int bitIndex = index%32;

arr[intIndex] = (arr[intIndex] | (1<<bitIndex));

2.2 实际的布隆过滤器（判断Url是否在黑名单里）

详细了解：布隆过滤器(Bloom Filter)详解 - 李玉龙 - 博客园 (cnblogs.com)

准备一个足够大的数组
准备黑名单：将url经过hash函数之后，生成一个code，对数组长度取模（类似上面的方法），将相应桶中相应位置描黑
用k个hash函数做同样的操作，数组中最多将有k个位置被描黑（置1）
当要检查一个url是否在黑名单中时，对这个url取k次hashcode，看对应的k位置是否被描黑
如果k个位置全部被描黑，那么这个url可能就属于这个黑名单中
只要有一个位置不是被描黑的，就能够判断这个url没有在黑名单中

如何决定n的大小（bit数组的大小）：

\(n = -\frac{m\times\ln(p)}{(\ln2)^2}\)

n是数组的长度，m是样本量，p预期失误率

如何确定hash函数的个数：

\(k = \ln2\times\frac{n}{m}\) 向上取整

真实失误率：

\((1-e^-\frac{m\times k}{n})^k\)

3 一致性哈希

降低数据迁移的代价，仍能保证负载均衡

在负载均衡的时候，面对服务器设备增加的情况，需要进行全部的数据迁移，重新进行哈希。

而在一致性哈希的结构下，可以避免对hashcode取模，高效的应对设备数量变化的情况

如何实现在环形结构中找到顺时针最近的服务器？

面临的问题：

当服务器数量很少的时候很难做到均匀负载，即便做到了均匀负载，加入新的服务器的时候，负载又会被破坏

解决方案：虚拟节点技术

一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布

4 并查集

非常快的检查两个元素是否属于一个集合isSameSet(A, B)

两个元素各自所在的集合合并在一起 union(A, B) ，A所在的集合和B所在的集合合并在一起

初始状态下，每个节点都是自己集合的代表节点
和其他集合合并的时候，元素数量少的集合将挂载到元素集合多的代表节点下面
如果要判断两个元素是否在同一个集合：就向上找他们各自的代表节点，如果是同一个代表节点，则判断是同一个集合

优化：

因为向上寻找代表节点的时候会存在链表的遍历，为了降低复杂度，在一次遍历中可以将结构扁平化：链表上的所有节点都直接连接在代表节点后面

代码：

public static class Node{

    }

    public static class unionFindSet{
        public HashMap<Node, Node> fatherMap;//key: child, value: father
        public HashMap<Node, Integer> sizeMap;//key: 当前节点， value：当前节点所在集合的size

        public unionFindSet(List<Node> nodes) {
            makeSets(nodes);
        }

        private void makeSets(List<Node> nodes){
            this.fatherMap = new HashMap<>();
            this.sizeMap = new HashMap<>();
            //集合初始化的时候，每个元素自成一个集合
            for (Node node:nodes) {
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        /**
         * 递归版本
         * @param node
         * @return
         */
        public Node findHead(Node node){
            Node father = fatherMap.get(node);
            //通过递归找到整个集合的代表节点
            if (father != node){
                father = findHead(father);
            }
            //将所有节点连到那个代表节点上去
            fatherMap.put(node, father);
            return father;
        }

        /**
         *
         * 非递归版本
         * @param node
         * @return
         */
        public Node findHead2(Node node){
            Stack<Node> nodeStack = new Stack<>();
            Node father = fatherMap.get(node);
            while(father!=node){
                nodeStack.push(node);
                node = father;
                father = fatherMap.get(node);
            }
            while(!nodeStack.isEmpty()){
                fatherMap.put(nodeStack.pop(),father);
            }
            return father;
        }

        /**
         * 判断是否是同一个集合
         * @param a
         * @param b
         * @return
         */
        public boolean isSameSet(Node a, Node b){
            return findHead(a) == findHead(b);
        }

        public void union(Node a, Node b){
            if (a == null || b == null){
                return;
            }
            Node aHead = findHead(a);
            Node bHead = findHead(b);
            //只有两个代表节点不相等才需要合并
            if (aHead!=bHead){
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if (aSetSize>bSetSize){
                    //将bSet挂载到aSet下面
                    fatherMap.put(bHead, aHead);
                    //更新aSet的size（两个set size的和）
                    sizeMap.put(aHead, aSetSize+bSetSize);
                }else {
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize+bSetSize);
                }
            }
        }
    }

复杂度分析：

查询次数+合并次数的数量级逼近O(n)及以上，单次查询的效率为O(1)

4.2 岛问题

算法：

遍历整个数组，如果遇到1，开始进行感染函数；如果遇到0，跳过
感染函数：以当前位置开始，在不越界的前提下，将上下左右的位置全部感染，1变成2
继续遍历，如果遇到2，继续向下进行

代码：

public class IslandCount {

    public static int countIsland(int[][] m){
        if (m == null || m[0] == null){
            return 0;
        }
        int N = m.length;
        int M = m[0].length;
        int res = 0;
        for (int i = 0; i < N ; i++) {
            for (int j = 0; j < M; j++) {
                if (m[i][j] == 1){
                    res++;
                    infect(m,i,j,N,M);
                }
            }
        }
        return res;
    }

    /**
     *
     * @param m 包含岛的矩阵
     * @param i 当前点所在的位置x
     * @param j 当前点所在的位置y
     * @param N 行数
     * @param M 列数
     */
    public static void infect(int[][] m, int i, int j, int N, int M){
        //如果坐标越界，或者当前位置的值不为1，不做任何操作
        if(i<0 || i>=N || j<0 || j>=M || m[i][j] != 1){
            return;
        }
        m[i][j] = 2;
        infect(m, i+1, j, N, M);
        infect(m, i-1, j, N, M);
        infect(m, i, j+1, N, M);
        infect(m, i, j-1, N, M);
    }

    public static void main(String[] args) {
        int[][] island = new int[][]{
                {0,0,1,0,1,0},
                {1,1,1,0,1,0},
                {1,0,0,1,0,0},
                {0,0,0,0,0,0}
        };
        System.out.println(countIsland(island));
    }

如果岛的数组很大很大，可以将数组分块来分别求数量。可能遇到分块中岛的数量之和不等于总数量的情况。可以用并查集去处理边界条件。

5 前缀树

新建一个头节点，对于每一个字符串，从头节点看，有没有可以到达每一个字符的路径，如果没有就新建一个路径。每一个字符表示一个路径而不是节点

功能：

可以查找是否有以“be”为前缀的字符串在树中
查找具体的字符串“be”是否被加入到了树中（需要添加一个属性：给每个节点添加一个计数，即以当前节点为结尾的字符串的数量。如：如果树中加过“be”，那么e后的节点中的计数就变为1）

以“be”为前缀的字符串有几个？（需要再添加一个属性：这个节点被扫过的次数，每有一个以“be”为前缀的字符串生成，e后面的节点中次数就增加1次）

代码：

public static class TrieNode{
        int path;//经过该节点的次数
        int end;//以当前node为节点的次数
        TrieNode[] nexts;

        public TrieNode() {
            this.path = 0;
            this.end = 0;
            this.nexts = new TrieNode[26];//规定当前String中的字符都是26个英文字母（小写）
        }
    }

    public static class Trie{
        TrieNode root;

        public Trie() {
            this.root = new TrieNode();
        }
        /**
         * 插入word
         * @param s 要插入的word
         */
        public void insert(String s){
            if (s == null){
                return;
            }
            char[] chars = s.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i<chars.length; i++) {
                index = chars[i] - 'a';//确定是nexts中的哪一条支路
                if (node.nexts[index] == null){
                    node.nexts[index] = new TrieNode();
                }
                node = node.nexts[index];//node变为下一个节点
                node.path++;//这个节点被经过，path++
            }
            node.end++;//循环结束，此时停到的节点就是String末尾，end++
        }

        /**
         * 查看要查找的值插入了几次
         * @param word
         * @return
         */
        public int search(String word){
            if (word == null){
                return 0;
            }
            TrieNode node = root;
            int index = 0;
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                index = chars[i]-'a';
                if (node.nexts[index] == null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        /**
         * 删除提供的word
         * @param word
         */
        public void delete(String word){
            //只有这个word存在才能删除
            if (search(word)!=0){
                TrieNode node = root;
                int index = 0;
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    index = chars[i] - 'a';
                    node = node.nexts[index];
                    //将经过node的次数-1
                    node.path--;
                    //如果删除之后，经过当前节点的次数==0，说明没有word会经过此节点了，直接指向null
                    if (node.path == 0){
                        node = null;
                        return;
                    }
                }
                node.end--;
            }
        }

        /**
         * 给定前缀的出现次数
         * @param prefix 提供的前缀
         * @return 前缀在树中的出现次数
         */
        public int prefixNum(String prefix){
            if (prefix == null){
                return 0;
            }
            TrieNode node = root;
            int index = 0;
            char[] chars = prefix.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.path;
        }
    }

    public static void main(String[] args) {
        Trie tree = new Trie();
        tree.insert("root");
        tree.insert("root");
        tree.insert("root");
        tree.insert("root");
        tree.insert("root");
        tree.insert("root");

        tree.delete("root");
        tree.delete("root");
        tree.delete("root");

        tree.insert("hello");
        tree.insert("hello");
        tree.insert("hello");

        tree.insert("this");
        System.out.println(tree.search("root")); //3
        System.out.println(tree.search("hello"));//3
        System.out.println(tree.search("this"));//1
        System.out.println(tree.prefixNum("ro"));//6
    }

算法中的结构：

每个节点中包含变量 path 和变量 end，一个节点数组，数组的每一个位置代表一个字符
每个节点选择数组中的某一个节点作为next（如上图中，选择的路径为 a -> c ），没有被选择的节点即为 null
每经过一个节点的时候，path++，遍历完整个word，当前节点即为word结尾的节点，end++， path++
删除的时候，将path - -，对于最后一个节点，end - -，如果当前节点的path已经被减为0，当前节点直接指向null

6 贪心策略

字典序：当长度相等的时候，按顺序比较每一位的ascii值；当长度不相等的时候，将短的补齐（用最小的字面值），在按照每一位的ascii码比较

贪心策略：

将问题分为一些子问题

对每个子问题求出局部最优解

将局部最优解整合，得到全局最优解

题目：有一个字符串数组，将其中的每一项拼接在一起形成一个大的字符串，要求形成的字符串字典序最小。例如 {"ab","cd","ef"}，拼成的最小字典序的字符串是“abcdef”

错误的解法：

将所有的字符串排好序（按照字典序），再按照顺序拼接起来。错误的原因："b"和"ba"，按照字典序为"b, ba"，但是拼接后的结果为"bba"，其字典序是小于"bab"的

正确的解法：利用贪心

String1和String2拼接：如果（String1+String2）<（String2+String1），则String1放前面，否则String2放前面

（在每两个String排序的时候，就可以实现局部最优的顺序）

贪心策略的正确性：

需要用数学方法证明两两比较具有可传递性（排序策略具有可传递性）
证明拼接之后的字符串的字典序是最小的（任意子串的位置交换之后都会得到更大的字典序）
3，3交换，4，4交换类比于两两交换

贪心策略的问题，要把重点放在贪心的策略上，而不是寻找方法去证明贪心策略的正确性，可以用对数器去证明结果的正确性，因为贪心策略的证明非常之难

6.1 金条题目（哈夫曼编码问题）

算法：

先将数组所有内容构建出一个小根堆
取出小根堆中最小的两个元素，堆中的两个元素删除
将两个元素相加，将结果加回小根堆（记录此结果为一个代价）
继续重复2-4步操作
直到小根堆中只有一个元素，将所有代价相加即是整个方法的总代价

哈夫曼算法就是将数组中的元素按照完美二叉树的要求构建，（代价小的距离根节点较远，代价大的距离根节点近），将其中所有的非叶节点的代价相加即是整个方法的代价当总共的代价等于局部代价之和的时候（本题），就首先考虑使用哈夫曼编码

代码：

public static class MinCostComparator implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    }
//如果不添加比较器，那么默认的排序就是大根堆
    public static int lessMoney(int[] nums){
        //构造小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new MinCostComparator());
        for (int i = 0; i < nums.length; i++) {
            queue.add(nums[i]);
        }
        int result = 0;
        while(queue.size()>1){
            result = result + queue.poll()+queue.poll();
            queue.add(result);
        }
        return result;
    }

6.2 利润最大

你要完成K个项目：所有项目的花费和利润都存储在两个数组中：

cost[x, x, x, x, x, x]

profit[x, x, x, x, x, x]

i = 0,1,2,3,4,5,6

现在又启动资金W，每一次只能选择一个项目，比如，如果我第一次选择了i=0项目，

cost = 40， profit = 30， W = 100；那么第一次完成项目之后，我手中的资金变成了130，我就可以接下来去选择cost<=130的项目了

在只能进行K次项目的情况下，求该如何选择项目，使得利润最大

算法：

准备一个小根堆，按照项目的cost为依据进行构建，小根堆的顶部就是cost最小的项目
将堆顶满足低于启动资金的项目都弹出，构建一个大根堆，大根堆的顶部就是在满足要求的前提下收益最大的项目
弹出大根堆的顶点，这个顶点即是当下要做的项目。之后启动资金W被更新（因为当前项目的收益）
向小根堆中加入新的项目（因为W的的变化，新的项目会被解锁）

当更新过的启动资金不能再解锁新的项目了，这时候就不会有新的项目加入到大根堆中，算法就只能结束

代码：

/**
     * 项目节点类，包含了项目的花费和利润
     */
    public static class Node{
        int cost;
        int profit;

        public Node(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

    public static class MinCostComparator implements Comparator<Node>{

        @Override
        public int compare(Node o1, Node o2) {
            return o1.cost-o2.cost;//小的放前面
        }
    }

    public static class MaxProfitComparator implements Comparator<Node>{

        @Override
        public int compare(Node o1, Node o2) {
            return o2.profit-o1.profit;//大的放前面
        }
    }

    public static int findMaxCapital(int k, int W, int[] profit, int[] cost){
        Node[] projects = new Node[profit.length];
        for (int i = 0; i < profit.length; i++) {
            projects[i] = new Node(cost[i],profit[i]);
        }
        //构建小顶堆
        PriorityQueue<Node> minCostHeap = new PriorityQueue<>(new MinCostComparator());
        //构建大顶堆
        PriorityQueue<Node> maxProfitHeap = new PriorityQueue<>(new MaxProfitComparator());
        //将所有项目添加到小顶堆中
        minCostHeap.addAll(Arrays.asList(projects));
        //保证总项目数不超过k
        for (int i = 0; i < k; i++) {
            //一旦小顶堆不空，且小根堆顶的cost不大于W，就将这个项目添加到大根堆
            while(!minCostHeap.isEmpty()&&minCostHeap.peek().cost<=W){
                maxProfitHeap.add(minCostHeap.poll());
            }
            //如果此时大根堆空掉了，返回当前的W
            if (maxProfitHeap.isEmpty()){
                return W;
            }
            //如果没有空，就取出大根堆的顶（利润最高的项目），收益加给W
            W += maxProfitHeap.poll().profit;
        }
        return W;
    }

6.3 会议室的日程

算法：

贪心策略：哪个项目早结束就先安排哪个项目，然后淘汰掉因为这个项目而不能进行的项目

public static class Program{
        int start;
        int end;

        public Program(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /**
     * 按照项目的终止时间来设定比较器
     */
    public static class ProgramComparator implements Comparator<Program>{

        @Override
        public int compare(Program o1, Program o2) {
            return o1.end - o2.end;
        }
    }

    /**
     * 求出在一天之内会议室可以安排的宣讲会的最大数量
     * @param programs 包含所有宣讲会的数组
     * @param current 当前时刻
     * @return 返回可以安排的宣讲会的数量
     */
    public static int bestArrange(Program[] programs, int current){
        Arrays.sort(programs, new ProgramComparator());
        int result = 0;
        
        for (int i = 0; i < programs.length; i++) {
            //只有满足在当前时间之后开始的项目才可以被安排
            if (current<=programs[i].start){
                result++;
                current = programs[i].end;
            }
        }
        return result;
    }

7 递归和动态规划

递归：（递归代表尝试）

把问题转化为规模缩小了的同类子问题
有明确的不需要继续进行递归的条件（base case）
有当得到了子问题的结果之后的决策过程
不记录每一个子问题的解

动态规划：（用于优化暴力递归）

从暴力递归中来
将每一个子问题的解记录下来，避免重复计算
把暴力递归过程抽象成状态表达
并且存在化简状态表达，使其更加简洁的可能

递归代表的问题就是，不知道具体怎么算，但是知道怎么尝试

P = NP问题：

P代表：有具体的计算方法（多项式时间内可以解决的问题）；

NP代表：可以进行尝试的问题（非确定性多项式时间可以解决的问题），不知道怎么算，但是知道怎么尝试

P问题举例：

计算1-1000的连续整数之和：这个问题就比较简单，无论是编程还是使用高斯求和公式都可以在有限可接受的时间内完成，这种算是P类问题。

NP问题举例：

计算地球上所有原子个数之和：这个问题就很困难甚至无解，但是现在有个答案是300个，显然是错的，所以很容易验证但不容易求解，这种算NP类问题。

7.1 暴力递归

7.1.1 n！问题

7.1.2 汉诺塔问题

算法：

准备三个杆：from， to， help（from上有n个圆盘，要全部移动到to上，借助help实现）
步骤：
1. 将1~n-1移动到help上
2. 将n移动到to上
3. 再将1~n-1移动到to上

代码：

public class HanoiTower {

    /**
     * 打印出汉诺塔的详细步骤
     * @param N 问题的规模（一共N个圆片）
     * @param from 最开始所有圆片都在的柱子
     * @param to 最后所有圆片要前往的柱子
     * @param help 用于辅助操作的柱子
     */
    public static void process(int N, String from, String to, String help){
        if (N == 1){
            System.out.println("move 1 from "+from+" to"+to);
            return;
        }
        process(N-1, from, help, to);
        System.out.println("move "+N+" from "+from+" to"+to);
        process(N-1, help, to, from);

    }

    public static void main(String[] args) {
        process(3, "柱子1", "柱子3", "柱子2");
    }

}

7.1.2 打印字符串所有的子序列，包括空字符串

代码：

public class SubStrings {
    /**
     * 打印出当前字符串的所有子序列
     * @param strs 字符串转成的字符数组
     * @param i 当前指针的位置
     * @param result 返回的字符串结果
     */
    public static void printAllSub(char[] strs, int i, String result){
        if(i == strs.length){
            System.out.println(result);
            return;
        }
        printAllSub(strs, i+1, result);
        printAllSub(strs, i+1, result+strs[i]);
    }

    public static void main(String[] args) {
        String s = "abcde";
        char[] chars = s.toCharArray();
        printAllSub(chars, 0, "");
    }
}

算法：

如果字符串指针指到了最后一位的下一位，说明已经遍历完毕，直接返回当前的结果
每个位置上有两种情况：打印当前位置的字符 / 不打印当前位置的字符

7.1.4 字符串的全排列

7.1.5 母牛问题

尝试：

证明递归逻辑的正确性：

今年的牛 = 去年的牛的数量（因为牛不会死，会被完整地保留下来）+ 三年前的牛的数量（因为三年前的牛在今年会全部成熟，每一头都会贡献一只小牛）

将O(2^N)复杂度转化为O(log₂n)的方法：

2020-12-30_12-29-18

问题从此被转化为O(log₂N)的规模：

如何进行矩阵的==快速==幂运算：

2020-12-30_12-49-15

	public static long countCows(long n){
        if(n<1){
            return 0;
        }
        if(n == 1 || n==2 || n==3){
            return n;
        }
        
        long[][] base = {{1,1,0},{0,0,1},{1,0,0}};
        long[][] res = matrixPow(base, n-3);
        return 3*res[0][0]+2*res[1][0]+res[2][0];
        
    }
    
    //求矩阵m的n次方
    public static long[][] matrixPow(long[][] m, long n){
        long[][] res = new long[m.length][m[0].length];
        for(int i = 0; i<res.length; i++){
            res[i][i] = 1;
        }
        
        long[][] temp = m;
        while(n!=0){
            if((n&1)==1){
                res = dotProduct(res, temp);//只有当前位上为1的时候，才将自乘后的m乘到res上
            }
            temp = dotProduct(temp, temp);//m自乘
            n>>=1;
        }

        return res;
        
        
    }
    
//矩阵相乘
    public static long[][] dotProduct(long[][] m1, long[][] m2){
        long[][] res = new long[m1.length][m2[0].length];
        for(int i = 0; i<m1.length; i++){
            for(int j = 0; j<m2[0].length; j++){
                for(int k = 0; k<m2.length; k++){
                    res[i][j] += m1[i][k]*m2[k][j];
                }
            }
        }
        return res;
    }

这种题就是先试几个情况，然后找规律

7.1.5 路径和问题

所有没做过的动态规划问题都可以先写出暴力递归的尝试版本，再优化成为动态规划

暴力递归：其中包含了重复的状态，造成了计算上的不必要的浪费

/**
     * 从当前位置i，j到右下角的最短路径和
     * @param matrix 要行走的矩阵
     * @param i 行位置
     * @param j 列位置
     * @return 最短路径和
     */

//方法一：暴力递归，时间复杂度很大
    public static int walk(int[][] matrix, int i, int j){
        //如果已经到达了右下角位置
        if(i == matrix.length-1 && j == matrix[0].length-1){
            return matrix[i][j];
        }
        //如果到达了最后一行
        if(i == matrix.length-1){
            return matrix[i][j]+walk(matrix, i, j+1);
        }
        //如果到达了最后一列
        if(j == matrix[0].length-1){
            return matrix[i][j]+walk(matrix, i+1, j);
        }
        //向右寻找最短路径和
        int right = walk(matrix, i, j+1);
        //向左寻找最短路径和
        int down = walk(matrix, i+1, j);
        return matrix[i][j]+Math.min(right, down);
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1,3,5,9},
                {8,1,3,4},
                {5,0,6,1},
                {8,8,4,0}
        };
        System.out.println(walk(matrix, 0,0));
    }




方法二：使用dp数组：
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int col = in.nextInt();
        int[][] m = new int[row][col];
        for(int i = 0; i<row; i++){
            for(int j = 0; j<col; j++){
                m[i][j] = in.nextInt();
            }
        }
        System.out.println(getMinPath2(m));
    }
    
//使用二维dp数组，占用空间较大，但是适用于需要求解出具体路径的dp问题
    public static int getMinPath(int[][] m){
        if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for(int i = 1; i<row; i++){
            dp[i][0] = dp[i-1][0]+m[i][0]; 
        }
        
        for(int j = 1; j<col; j++){
            dp[0][j] = dp[0][j-1]+m[0][j];
        }
        
        for(int i = 1; i<row; i++){
            for(int j = 1; j<col; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+m[i][j];
            }
        }
        
        return dp[row-1][col-1];
    }
    
//使用一维dp数组，可以重复使用，占用空间较小，不适用于求解具体路径的dp问题，但是可以适用于求出最短路径数值的问题
    public static int getMinPath2(int[][] m){
        if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){
            return 0;
        }
        int less = Math.min(m.length, m[0].length);
        int more = Math.max(m.length, m[0].length);
        //判断较大的数据是行还是列
        boolean moreIsRow = more == m.length;
        int[] dp = new int[less];//dp数组只需要和短边一样长就好了
        dp[0] = m[0][0];
        for(int i = 1; i<less; i++){
            dp[i] = dp[i-1] + (moreIsRow?m[0][i]:m[i][0]);
        }
        for(int i = 1; i<more; i++){
            dp[0] = dp[0] + (moreIsRow?m[i][0]:m[0][i]);
            for(int j = 1; j<less; j++){
                dp[j] = Math.min(dp[j-1], dp[j])+(moreIsRow?m[i][j]:m[j][i]);
            }
        }
        return dp[less-1];
    }

无后效性问题可以改成动态规划（在本题中，每一个位置的返回值都是确定的，不论该位置是怎么被达到的）

算法（暴力递归改成动态规划）：

设置好边界位置（base case）：右下角；右边界；下边界
绘制dp图
对于普遍位置：当前位置可以由下一个右侧位置和下一个下侧位置求出，看看当前的普遍位置需要依赖什么位置，逆回去就是动态规划的路径

7.1.6 累加问题

算法：

尝试版本
列出可变参数的变化范围
终止位置是什么
base case提前填好
由普遍位置推出它所依赖的位置

字符串问题

1 KMP算法

区分子序列和子串：子序列不一定连续，子串一定连续

求每一个位置上的字符：其前面字符串的最长前缀和最长后缀（前缀不包含最后一位，后缀不包含第一位）的最长匹配位数

2020-12-29_08-59-52

找到String1中和String2中不匹配的第一个字符，计算String2中最长匹配的前后缀：
从String1中找到对应String2中后缀开端的位置，将String2推过去，起点重合，再从后缀结束的下一个位置开始匹配：

本质：我们在继续尝试从J位置开始的匹配情况，==并且已经可以保证 J之前的位置全部没有匹配上==

寻找next数组：假设最长相等前后缀长度为LPP

设当前位置是 i 位置，目前已知 i-1位置的==LPP==为n，比较==i-1位置的前缀的下一位==是否和==i-1位置==的字符相等
如果相等：当前位置的==LPP== = cn++ （如果跳到了cn位置，那么cn位置之前回有cn个字符，也就是i-1位置的==LPP==）
如果不相等，cn继续跳到next[cn]的位置，进行上述操作
如果cn已经等于0都不能达到步骤2的相等，则 i 位置的值为0

代码：

public static int KMP(String str1, String str2){
        if (str1 == null || str2 == null || str1.length()<1 || str1.length()<str2.length() || str2.length()<1){
            return -1;
        }
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        //得到str2的next数组
        int[] next = getNextArray(s2);
        //两个指针，分别指向str1和str2当前比较的位置
        int p1 = 0;
        int p2 = 0;
        while(p1<str1.length() && p2<str2.length()){
            if (s1[p1] == s2[p2]){
                p1++;
                p2++;
            }else {//当前位置不匹配了
                if (next[p2] == -1){//如果已经到了str2的第一个字符还没有匹配
                    p1++;//就继续尝试str1的下一个字符
                }else {
                    p2 = next[p2];//指针指向str2前缀的下一个位置
                }
            }
        }
        return p2 == str2.length()?p1-p2:-1;//如果，p2跑完了整个str2，说明匹配完毕，此时p1肯定也停在str2的末尾，则开始位置就是p1-p2
        //否则说明两个字符串没有匹配上，返回-1

    }

    public static int[] getNextArray(char[] str2){
        if (str2.length == 1){
            return new int[]{-1};
        }
        //要返回的next数组
        int[] next = new int[str2.length];
        next[0] = -1;//认为规定：0位置上的值为-1
        next[1] = 0;//因为前后缀不包括前缀的最后一个数和后缀的第一个数，所以这里唯一的一个数不属于前缀和后缀，值为0；
        int i = 2;//从第二个位置开始遍历
        int cn = 0;//跳跃到的位置：
        while (i<str2.length) {
            if (str2[i - 1] == str2[cn]) {//如果当前位置的上一个位置和cn指向的位置相等，cn++， 且当前位置值=cn
                next[i++] = ++cn;
            } else if (cn > 0) {//如果当前位置的上一个位置和cn指向的位置不相等，cn跳到next[cn]
                cn = next[cn];
            } else {//如果不相等且cn==0，则i位置的值也为0
                next[i++] = 0;
            }
        }
        return next;
    }

应用：

1. 一道京东面试题：

已知一个字符串，构建一个大字符串，使得大字符串中小字符串出现两次：
比如：
String1 = "abcabc"    得到的大字符串为："abcabcabc"
String1 = "abcbab"    得到的大字符串为："abcbabcbab"

算法：利用KMP中求next数组的方法：
求出每一位的LPP值，最后再求出终止位（string1的末尾的下一位的LPP值），这个值就在说明整个字符串的前后缀重复的长度，
只要如下操作：
	abcb|ab|
	    |ab|cbab
这样错位对上，补足后面的cbab就可以了===>abcbabcbab

2. 判断子树问题

判断Tree1是不是Tree2的子树：
算法：
1. 先将两棵树序列化，
2. 如果Tree1的序列化字符串是Tree2序列化字符串的子串，则Tree2中必定包含Tree1

3. 判断一个String是不是由某一个子串重复得到的

1	abcabcabcabc

2. Manahcer 算法

从一个字符串中找到最长的回文子串

暴力解法：

比如：11311这个字符串：
向其中加入特殊字符将他们分开：#1#1#3#1#1#
遍历整个字符串，以每一个字符为中心向两边扩展（直到某一边扩展到边缘），
# 1 # 1 # 3  # 1 # 1 #
1 3 5 3 1 11 1 3 5 3 1
得到的最长长度除以二就是最大回文串的长度
（时间复杂度为O(n^2)）

Manacher算法：

概念：

回文直径

回文半径

回文半径数组：将每个位置的回文半径存在数组中

最右回文右边界

当前回文右边界对应的中心（记录第一次到达该右边界的中心）

情况讨论：

1. i在最右边界的外面，最右边界向右扩张O(n)
2. i在最右边界的内部，三种情况：
	（1）i的对称i'的左边界（小L）在L的内部：[ (...^...) C ...^... ]    则i所在位置的半径就是i'的半径O(1)
	                                     L l   i'  r      i    R
	（2）i的对称i'的左边界（小L）在L的外面：(...[ ^...) C ...^ ]       则i所在位置的半径就是R-i  O(1)
	                                     l   L i'  r      i R
	（3）i的对称i'的左边界（小L）在L的上面（重合）： [...^...) C ...^... ]  则从i到R可以不用验证了，R后面的需要继续验证（验证i的回文半径需不需要扩张）O(n)
	                                             Ll  i'  r      i    R

总的时间复杂度是O(n)

应用：

只向字符串末尾添加字符串，怎么让字符串成为回文串，要求添加的字符最少

比如：abc12321----->abc12321cba

算法：
1. 求出在必须包含最后一位的前提下，最长回文串（12321）
2. 再将不属于回文串内部的部分（abc）逆序加上去（cba）

Next Post

【LeetCode】数值的整数次方
Previous Post

【LeetCode】 343.剪绳子2

CATALOG

1. Leetcode
2. 排序
3. 数据结构
1. 3.1. 栈
2. 3.2. 二叉树相关问题
4. 哈希函数和哈希表
5. 字符串问题
1. 5.1. 1 KMP算法
2. 5.2. 2. Manahcer 算法