[数据结构与算法]leetcode选题

先刷了一遍leetcode前100和hot100，许多题目用的是自己的“土办法”。这里总结了一下，结合自己的解法和题解中一些大佬的解法，形成了对一道题目的的分析，包括巧妙的数据结构，常用的算法思想，冷门的api以及固定的套路和牛逼的技巧。

1.数组

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

• 提高部分是利用二分法来逐步搜索，二分法需要直到，以什么二分，递归边界返回，子递归的边界确定
• 先确定以k为标准二分，这里参数和下标一致，0表示找第0个，1表示找第一个1，需要排除1个
• 假如k=1，显然，num1和num2各拿出第一个元素比较
• 假如k=2，此时，拿出1各还是2个，举例如果是2个，因为需要排除2个，比如: 1 4和2 3 一看，4>3，把2和3全排除了，然后显然取1了，肯定是错的，所以只能取1个，先排除一个，减低k为1，再排除一个
• 如果k=3，此时，可以举例或证明，拿出两个，一次性排除2个是没问题的，此时规律也即确定
• 对于这种规律，似乎只能举例，来确定边界，难题也就是难在这里
• 另外，k也可以表示数量，那么部分边界要发生改变。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len = nums1.length + nums2.length;
    if((len & 1) == 0)
        return (deletehalfKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, len 				 / 2)+ deletehalfKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length 			   - 1, len / 2 - 1) ) * 0.5;
    else
        return deletehalfKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length-1,len/2);
}
private int deletehalfKth(int[] nums1,int s1,int end1,int[] nums2,int s2,int end2,int k) {
    if(s1 >= nums1.length)  return nums2[s2 + k];	//处理数组越界递归边界
    if(s2 >= nums2.length)  return nums1[s1 + k];	
    if(k == 0)	return Math.min(nums1[s1], nums2[s2]);	//处理正常递归边界返回
    int p1 = Math.min(end1,  s1 + (k - 1) / 2);	//k-1很精妙，即对k=2不能+1
    int p2 = Math.min(end2, s2 + (k - 1) / 2);
    if(nums1[p1] > nums2[p2])   //nums2的前k/2个元素就可以删掉掉了，即不可能包含最终结果
        return deletehalfKth(nums1, s1, end1, nums2, p2 + 1, end2, k - (p2 - s2) - 1);
    else
        return deletehalfKth(nums1, p1 + 1, end1, nums2, s2, end2, k - (p1 - s1) - 1);
}

L581_最短无序连续子数组

题目：比如对于[2,6,4,8,10,9,15]，只需要重排[6, 4, 8, 10, 9]就可以使原数组有序，返回最短这样数组的长度

分析：

• 暴力发：左指针遍历，右指针从左指针出发遍历，要求：左指针以左升序且小于[l-r]最小值，右指针升序且大于[l-r]最大值，O(n^3)的复杂度
• 左指针遍历，右指针从左指针出发，这时候[l] > [r]说明，说明左边界要移到l处，还能说明右边界可以在r处；后续遍历左指针，无论初步出现[l] > [r]，左边界第一次即确定，右边界其实可能会右移；另一种换位思考就是从后面遍历
• 再优化，就是想知道，对于l，l右边的最小元素是多少，如果[l]比最小元素大，显然边界就该确定了

public int findUnsortedSubarray(int[] nums) {  
    int rb = -1;
    int lmax = nums[0];
    for(int i = 0; i < nums.length; i ++){
        lmax = Math.max(lmax, nums[i]);
        if(nums[i] < lmax)	rb = Math.max(rb, i);
    }
	int lb = nums.length;
    int rmin = nums[nums.length - 1];
    for(int i = nums.length - 1; i >= 0; i --){
        rmin = Math.min(rmin, nums[i]);
        if(nums[i] > rmin)	lb = Math.min(lb, i);
    }
    return Math.max(0, rb - lb + 1);
}

2.字符串

L3_无重复字符的最长字串

• 对于字符串寻找某某最长通常可以考虑滑动窗口
  1. 记录出现的字母：可以用数组，遍历中发现字母ch计数值已经等于1，开始调整左指针，直到指向ch，将计数值减1，移动下一个元素
  2. 这个移动过程其实就是找ch对应的下标，因此，可以优化为map存，注意一点：左指针从map取值可能会后退，比如abccba，遍历到第二个c，左指针会移动到3下标，但是遍历到第二b，左指针回退到下标1

L76_最小覆盖子串

题目：s是主串，t是模式串，求s中覆盖t的最小串，没有则返回空串

分析：

• 首先要统计t串中各个字符的数量
• 统计完后，就可以遍历s串，假设遍历到i下标出，发现满足要求了，那么这时候应该：
  • 比较当前长度，如果比初始小，初始可设为s串长度，那么记录开始位置和长度
  • 然后这时候需要判断段左指针位置是不是t串字符，如果不是，将左指针右移1，继续统计长度记录左边位置
  • 如果发现是t串字符，那么将统计的t串字符数量-1，将对应位置的字符数+1，同时右移左指针1，继续回到遍历s串
• 要考虑一种机端情况，比如，s串是a，t串是aa，那么遍历完之后，就会返回开始位置0，长度为1的串，即a，而不是空串。对于这种情况，即遍历完s都没包含t串，需要区分开来
• 还有一种情况是：确实包含了，但是又将cnt-1了，即cnt数量不能判断有没有包含完t串
• 对于这种情况，巧妙设置初值，即设初始长度不为s.length()，而是s.length() + 1，这样，最终判断，该值如果大于s.length()，就说明没有在遍历中改变过符合要求的串的长度的值，但凡长度等于s.length()，也说明寻找到了，就是s串全部

对字符串滑动窗，一般可以统计两个指标，一个是字符ch有没有出现，另外就是ch这个字符的数量有没有满足要求。通常找到第一个满足条件，然后while循环左指针到不满足条件

public String minWindow2(String s, String t) {
    boolean[] flag = new boolean[128];
    int[] rec = new int[128];
    for (char c : t.toCharArray()) {
        rec[c] ++;
        flag[c] = true;
    }
    int cnt = 0, l = 0, min_l = 0, min_size = s.length() + 1;
    for (int i = 0; i < s.length(); i++) {
        if(flag[s.charAt(i)]){
            if(--rec[s.charAt(i)] >= 0)	cnt ++;
            while (cnt == t.length()){
                if(i - l + 1 < min_size){
                    min_l = l;
                    min_size = i - l + 1;
                }
                if(flag[s.charAt(l)] && ++ rec[s.charAt(l)] > 0)	-- cnt;
                ++ l;
            }
        }
    }
    return min_size > s.length() ? "" : s.substring(min_l, min_l + min_size);
}

3.链表

L148_排序链表

• 数组排序有n多种nlogn，但是链表在常数空间复杂度下的nlogn该怎么写
• 麻烦在于指针处理不像下标交换，因此优先选用归并排序
• 归并排序可以自底向上和自顶向下，通常递归比写while循环逻辑简单

public ListNode sortList(ListNode head) {
    if(head == null || head.next == null)	return head;	//0或者1个元素
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null){	//二分
        slow = slow.next;	//对于偶数元素，slow指向一半偏左，对于奇数元素，slow指向正中间
        fast = fast.next.next;
    }
    ListNode rh = slow.next;    //right head
    slow.next = null;	//左边的末尾
    ListNode l = sortList(head);    //对左边排好序
    ListNode r = sortList(rh);  //对右边排好序
    ListNode dummyHead = new ListNode(0);	//小技巧，虚节点
    ListNode lc = l;	//左一半遍历指针
    ListNode rc = r;	//右一半遍历指针
    ListNode cur = dummyHead;	//返回链的当前指针
    while (lc != null && rc != null){
        if(lc.val < rc.val){
            cur.next = lc;
            lc = lc.next;
        }else{
            cur.next = rc;
            rc = rc.next;
        }
        cur = cur.next;
    }
    if(lc != null)	cur.next = lc;
    else 	cur.next = rc;
    return dummyHead.next;
}

4.二叉树

L96_不同的二叉搜索

题目给定一个整数n，要求返回树的个数，树的节点是从1-n组成的搜索树

分析：

• 遍历，如果根是1-n，依次求出对应的个数
• 以3为例，左孩子取排列1-2，右孩子排列4-n，这时候需要抽象，4-n的排列其实等于1-n-3，因为关注相对大小。进一步抽象，关注的是有多少个元素参与排列，是不是连续都不重要，比如123和134显然种类一样的

public int numTrees(int n) {
    int[] dp = new int[n+1];
    dp[0] = 1;	//边界计算的需要，本身边界值一般可以不与实际意义挂钩
	dp[1] = 1;
    for(int i = 2; i <= n; i ++)
        for(int j = 0; j < i; j ++)
            dp[i] += dp[j] * dp[i - j - 1];
    return dp[n];
}

L98_验证二叉搜索树

分析：

• 第一次做直接递归验证左右孩子是不是满足要求
• 其实还要保证，根节点的左子树所有元素均小于它，对于根左孩子的右孩子，不仅要比左左孩子大，还要比根小，所以其实有两个界，意味着递归也要传两个界

//第一次写法
public boolean isValidBST(TreeNode root) {
    return rec(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean rec(TreeNode root, long minValue, long maxValue) {
    if(root == null)    return true;
    boolean temp = true;
    if(root.left != null ){
        if(root.left.val < root.val && root.left.val > minValue)
            temp &= rec(root.left, minValue, root.val);
        else	return false;
    }
    if(root.right != null){
        if(root.right.val > root.val && root.right.val < maxValue)
            temp &= rec(root.right, root.val, maxValue);
        else	return false;        
    }
    return temp;
}

//改进写法，树的递归尽量减少判断子树，应该交给递归去做
private boolean rec2(TreeNode root, long minValue, long maxValue) {
    if(root == null)    return true;
    if(root.val <= minValue || root.val >= maxValue)    return false;
    return rec2(root.left, minValue, root.val) && rec2(root.right, root.val, maxValue
                                                      );
}

L437_路径总和III

题目：路径定义需要满足向下关系，即父节点到子节点的单向关系，输出路径个数

分析：

• 对数的题目，几乎没有不递归的（数定义就是递归的），对于某个节点，一定有一种情况就是路径以它开始，另外的情况则是正常的加
• 需要两个递归，一个递归尽管可以解决当前元素加还是不加，但是保证不了路径的连续性
• 易错点1：是当某条路径和满足要求时，仍然需要递归，因为负值的存在
• 易错点2：叶子节点的判断要注意，不要重复加了

public int pathSum(TreeNode root, int targetSum) {
    if(root == null)    return 0;
    int cur = add(root, targetSum);
    int a = pathSum(root.left, targetSum);
    int b = pathSum(root.right, targetSum);
    return cur + a + b;
}
private int add(TreeNode root, int sum) {
    if(root == null)    return 0;
    int res = root.val == sum ? 1 : 0;
    return res + add(root.left, sum - root.val) + add(root.right, sum - root.val);
}

L124_二叉树中的任意最大路径和

分析：

• 对于任意一个节点node，包含的情况有：结果路径和中的一个，结果路径和的的转折节点
• 递归真正是从叶子节点开始，对于某个叶子节点node1，node2，及共同的父节点pnode，如果仅考虑三个节点，那么很明显，先考虑1个节点，最大值一定包含在下面情况：node1，node2，pnode，然后考虑大于1个节点的路径，则一定包含pnode，那么如果node1大于0，就应该加到pnode，node2同理。再求最大值。
• 如果树是三层，第二步能求出仅有三个节点的最大值，但是这三个节点构成的子节点对他们的父节点，一定要满足是一条路径，不能是同时包含左右孩子，所以要选一条node1+pnode还是node2+pnode

int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    if(root == null)    return 0;
    dfs(root);
    return res;
}
private int dfs(TreeNode root) {
    if(root == null)    return 0;
    int a = Math.max(dfs(root.left), 0);	//如何是负数，本质自底向上，一定不会加这部分的
    int b = Math.max(dfs(root.right), 0);
    res = Math.max(a + b + root.val, res);	//最值和递归返回是两个变量，和一般保持一致确实不同
    return Math.max(a, b) + root.val;
}

int max = -1000;
public int maxPathSum(TreeNode root) {
    int l = Math.max(calPathAdd(root.left),0); 
    int r = Math.max(calPathAdd(root.right), 0);
    max = Math.max(max, root.val + l + r);
    if(root.left != null)	max = Math.max(max, maxPathSum(root.left));
    if(root.right != null)	max = Math.max(max, maxPathSum(root.right));
    return max;
}
public int calPathAdd(TreeNode root){
    if(root == null)    return 0;
    int l = calPathAdd(root.left);
    int r = calPathAdd(root.right);
    return Math.max(Math.max(l, r) + root.val, root.val);
}

• 上面第二段是后来一次的写法，思路很明确，遍历所有节点，最值肯定出现在以某个节点为中心（左右孩子从它延伸），但是calPathAdd会计算很多重复，可以考虑用map保存。还是第一种牛逼一点，就类似于求公共子节点，一种做法就是判断每一个节点是不是公共子节点，是的话，判断左右都不是，就是它；还有平衡二叉树，对每个节点都求左右孩子的高度差等等，这些想法直接，都会有许多求解的过程。

L543_二叉树的直径

题目：求是是两侧深度和，比如对于二层树，如果左右孩子都有，返回2，只有一个，返回1

分析：

• 很容易联想求最大深度，直接求根得左树深度和右数深度，即求出结果，但是最长路径不一定经过根
• 所以，和上一题L124类似，从叶子节点开始考虑，中间不断的对比当前最大值和以该节点为根能产生的最大值，但是对于该节点，返回同样取决于左右子数谁更高
• 几乎一模一样和L124，这种解法对应于最值可能以任意节点作为根

int res2 = 0;
public int diameterOfBinaryTree(TreeNode root) {
    if(root == null)    return 0;
    dfs2(root);
    return res2 - 1;
}
private int dfs2(TreeNode root) {
    if(root == null)    return 0;
    int l = dfs2(root.left) + 1;
    int r = dfs2(root.right) + 1;
    res2 = Math.max(res2, l + r - 1);
    return Math.max(l, r);
}

L538_把二叉搜索树转化为累加树

题目：加的顺序是右孩子——根节点——左孩子，依次累加整个树

分析：

• 明显要用递归，而且递归顺序也应该是右孩子，根节点，左孩子
• 最后一个右节点肯定是null，此时，就会来到根节点，这里必须要涉及root.val，假如此时有左孩子，那么要把这个值传到左孩子，因此可以给dfs(root.left, root.val)，来到左孩子，左孩子又遍历左孩子的右孩子，不妨设左孩子没有子节点，此时的根节点就已经指向完了dfs
• 然后要考虑返回值，应该返回右孩子的值

public TreeNode convertBST(TreeNode root) {
    dfs(root, 0);
    return root;
}

public int dfs(TreeNode root, int val){
    if(root == null)    return val;
    int a = dfs(root.right, val);
    root.val = root.val + a;
    int b = dfs(root.left, root.val);
    return b;
}

这个递归并不彻底，既然是累加，可以考虑将它设全局变量

int sum = 0;
public TreeNode convertBST(TreeNode root) {
    if(root == null)	return null;
    convertBST(root.right);
    sum += root.val;
    root.val = sum;
    convertBST(root.right);
	return root;  
}

L113_路径总和II

题目：从根到叶子节点的路径和为target的所有路径

分析：

• 如果是输出是否，不用记录路径
• 要输出所有路径，显然有回溯的过程，回溯的关键就是形成闭环，有加有删

List<List<Integer>> res3;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    res3 = new ArrayList<>();
    backtrack(root, targetSum, new ArrayList<Integer>());
    return res3;
}
private void backtrack(TreeNode root, int targetSum, List<Integer> list) {
    if(root == null)	return;
    if((root.left == null && root.right == null && targetSum == root.val)){
        list.add(root.val);
        res3.add(new ArrayList<>(list));
        list.remove(list.size() - 1);
        return;
    }
    list.add(root.val);
    backtrack(root.left, targetSum - root.val, list);
    backtrack(root.right, targetSum - root.val, list);
    list.remove(list.size() - 1);
}

L208_实现Trie(前缀树)

题目：对于字符串前缀树，实现插入、查找字符串是否存在，以及是否存在某前缀

分析：

• 容易想到，构造一个类，这个类属性有boolean[26]存储，可以用0表示没有，1表示有，但是呢，每个元素位置又得指向一个boolean[26]，这样想感觉陷进去了
• 固定思维是26个位置有元素，那么就需要用boolean或者int等类型去表示，但是一旦用具体类型，又很难去做为父元素指向子元素，所以父元素不能是普通类型，需要是对象
• 那么自然而然，该Trie类需要包含Trie[26] childs;

class Trie {
    Trie[] childs;	//它的每一个孩子可以再new Trie，表示这个位置有元素
    boolean end;	//需要标识一个单词的结束位置
    Trie(){
        childs = new Trie[26];
        end = false;
    }
    public void insert(String word) {
        Trie t = this;
        for (int i = 0; i < word.length(); i++) {
            if(t.childs[word.charAt(i) - 'a'] == null){
                t.childs[word.charAt(i) - 'a'] = new Trie();
            }
            t = t.childs[word.charAt(i) - 'a'];
        }
        t.end = true;
    }
    public boolean search(String word) {
        Trie t = this;
        for (int i = 0; i < word.length(); i++) {
            if(t.childs[word.charAt(i) - 'a'] == null){
                return false;
            }
            t = t.childs[word.charAt(i) - 'a'];
        }
        return t.end;
    }
}

L114_二叉树展开为链表

题目：将二叉树展开为单向链表，由右指针指向，按前序遍历顺序

分析：

• 最简单就是实现前序遍历，记录每一个TreeNode，然后连起来
• 用右指针连起来，那么必然要保存右指针的原始元素，容易想到用栈来保存右边的元素，那么遇到左边的就把右指针指向左边元素，遇到右边的元素将其入栈，当没有左边元素，那么就从栈中取出，将当前节点指向取出的节点，同时取出的节点有可能有左孩子，因此要重复上面过程

树和栈奇妙的运用在了一起，凡是想表示层层子结构的，栈或者递归函数都是首选

public void flatten(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    if(root != null)	stack.push(root);
    TreeNode cur = root;
    while (!stack.isEmpty()){
        TreeNode temp = stack.pop();
        if(temp != root) {	//判断非root节点，也就是一个边界判断，不能让root的右孩子指向自己
            cur.right = temp;
            cur = cur.right;	//从栈中取，用当前元素指向取出元素
        }
        while (cur != null) {
            if (cur.right != null)	stack.push(cur.right);	//右孩子进栈
            if(cur.left == null && cur.right != null)	break;	//只有右孩子，那么跳出循环
            if (cur.left != null) {		//把左孩子的指向改变
                cur.right = cur.left;
                cur.left = null;
                cur = cur.right;
            }
            if(cur.left == null && cur.right == null)	break;	//防止死循环
        }
    }
}

• 优化思路：参考官方题解，简单的离谱！

public void flatten(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left != null) {
            TreeNode next = curr.left;
            TreeNode predecessor = next;
            while (predecessor.right != null) {
                predecessor = predecessor.right;
            }
            predecessor.right = curr.right;
            curr.left = null;
            curr.right = next;
        }
        curr = curr.right;
    }
}

• 自己后来的思路

public void flatten(TreeNode root) {
    TreeNode head = root;
    Deque<TreeNode> queue = new LinkedList<>();
    while(root != null){	
        if(root.right != null){
            queue.add(root.right);
            root.right = null;
        }
        if(root.left != null){
            root.right = root.left;
            root.left = null;
        }
        if(root.left == null && root.right == null && !queue.isEmpty()){
            root.right = queue.removeLast();
        }
        root = root.right;
    }
}

?

5.栈

L42_接雨水

题目：输入是整数数组，数值表示墙的高度，求能容纳雨水的体积

分析：

• 难点就在于对于某处空隙体积，很难知道它能到达的高度，考虑维护一个单调递减的栈，如果持续变小，就一直入栈，当遍历元素大于栈顶，说明形成了空隙，此时应该算一下空隙：应该要先出栈，该值记位h，之后的栈顶元素和遍历元素取较小值，之后再减去h，乘左右边界差；

• 接着考虑，相等该怎么办，入不入栈都行，这里采取入栈

• 每出栈一次，都应该计算一次，比如2 1 0 3，遇到3大于栈顶，则0出栈，此时取1和3较小值1，然后减0，该轮空隙为1，然后还得1出栈，此时，2和3较小为2，减高度1为1，但是宽度为2，此时空隙累加2，紧接着2也得出栈，但是此时栈为空，所以不用计算空隙，紧接着3入栈即可

• 对于接雨水，抽象出当前i贡献的val到底取决于什么，进而用dp求对每个i的两侧高度，进而双指针的过度过程

public static int trap(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[stack.peek()] < height[i]){
            Integer pop = stack.pop();
            if(!stack.isEmpty()){
                res += (Math.min(height[stack.peek()], height[i]) - height[pop] ) * (i - stack.peek() -1 );		//核心计算体积，一定要注意要满足的条件1.有出栈；2.出栈后栈不空
            }
        }
        stack.push(i);
    }
    return res;
}

• 统计左右边界更直观

public int trap(int[] height) {
    Deque<Integer> queue = new LinkedList<>();
    int[] lbound = new int[height.length];
    int max = height[0];
    for(int i = 1; i < height.length; i ++){
        lbound[i] = Math.max(height[i - 1], max);
        max = Math.max(max, height[i]);
    }
    int[] rbound = new int[height.length];
    max = height[height.length - 1];
    for(int i =  height.length - 2; i >= 0; i --){
        rbound[i] = Math.max(height[i + 1], max);
        max = Math.max(max, height[i]);
    }
    int res = 0;
    for(int i = 1; i < height.length; i ++){
        res += Math.max((Math.min(lbound[i], rbound[i]) - height[i]), 0);
    }
    return res;
}

L84_柱形图中最大矩形

题目：和接雨水类似，求最大矩形面积

分析：

• 暴力解法为，以每一个heigt[i]为高，求左右边界，然后求出一个面积，遍历，取其中最大值
• 尝试用单调栈的思维考虑，想要做的是对于遍历的下标i，找出以它为高的左右边界，如果维护一个单调递增的栈，当出现遍历位置小于栈顶，说明，以栈顶为高的右边界就是当前遍历位置，左边界其实就是栈顶元素
• 如果出现相等元素，那么考虑不入栈
• 什么时候计算面积？出栈的时候，计算的是以栈顶元素为高的矩形面积
• 最后考虑哨兵插入尾部，防止一路递增的输入而输出为0

public static int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int[] lbound = new int[heights.length];
    Arrays.fill(lbound, Integer.MAX_VALUE);
    int res = 0;
    for (int i = 0; i < heights.length; i++) {//求i的左边界并不简单，第二种解法避免求第i的左边界
        while (!stack.isEmpty() && heights[stack.peek()] > heights[i]){
            Integer pop = stack.pop();
            lbound[i] = stack.isEmpty() ? 0 : stack.peek();
            res = Math.max(res, heights[pop]*(i - lbound[pop] - 1));
        }
        lbound[i] = Math.min(lbound[i], stack.isEmpty() ? -1 : stack.peek());
        stack.push(i);
    }
    while (!stack.isEmpty() && heights[stack.peek()] > 0){
        Integer pop = stack.pop();
        res = Math.max(res, heights[pop]*(heights.length - lbound[pop] - 1));
    }
    return res;
}

第二种解法：不关注第i个柱子的左右边界，关注的是栈顶元素的左右边界

public int largestRectangleArea(int[] heights) {
    int[] height = new int[heights.length + 2];
    Stack<Integer> stack = new Stack<>();
    System.arraycopy(heights, 0, height, 1, heights.length );
    int res = 0;
    for (int i = 0; i < height.length; i++){
        while (!stack.isEmpty() && height[stack.peek()] > height[i]){
            Integer pop = stack.pop();	//考虑该栈顶元素
            Integer left = stack.peek();	//单调递增栈，所以此时栈顶就是左边界，i就是右边界
            res = Math.max(res, (i - left - 1) * height[pop]);
        }
        stack.push(i);
    }
    return res;
}

H85_最大矩形

题目：二维0或1矩阵中，寻找全1的最大矩形面积

分析：

• 首先能不能基于规模，分治法显然不合适，那么动态规划其实也不合适
• 那么基本上只能枚举，就是对每一个[i, j]求出以它为顶点的最大面积
• 直观的想法是从高为1到最大，在这个过程中，其实是可以一次性统计宽度的
• 即可以认为统计的过程是简单的动态规划

public int maximalRectangle(char[][] matrix) {
    if(matrix.length == 0)  return 0;
    int[][] len = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) 
        for (int j = 0; j < matrix[0].length; j++) 
            if (matrix[i][j] == '1') 
                len[i][j] = (j == 0 ? 0 : len[i][j - 1]) + 1;
    int res = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            int width = len[i][j];
            for(int k = 1; k <= i + 1; k ++)
                if(len[i + 1 - k][j] > 0){
                    width = Math.min(width, len[i + 1 - k][j]);
                    res = Math.max(res, k * width);
                }else 
                    break;
        }
    }
    return res;
}

• 从算法思想来讲，如果不能基于规模，那么只能枚举，而遍历的过程大有讲究，可以是穷举，可以是利用滑动窗口（双指针），可以利用队列，栈，堆等等数据结构
• 其实这道题，是可以利用单调栈+第一种求法中简单动态规划来求解，具体而言，遍历每一行，以该行为低，发现是和接雨水以及求柱形图中最大矩形是类似的，只需遍历每一行求出最大值即可；而高度是可以通过第一种解法中的简单动态规划求解

L456_132模式

分析：

• 三层for循环是直接超时的
• 试图减少循环层数，假设遍历到某个元素p，让p就是中间最大元素，此时要做的是从p左边找到最小元素，从p右边找到小于nums[p]的最大元素，然后比较
• 从左边找的，明显可以用dp存起来；如果从右边找，要找小于nums[p]的最大，介绍单调递减栈求
• 栈真是一个奇妙的东西，这里求i位置右边比它小的最大数

public boolean find132pattern(int[] nums) {
    int[] min = new int[nums.length + 1];
    min[0] = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) 	min[i + 1] = Math.min(min[i], nums[i]);
    Deque<Integer> queue = new LinkedList<>();
    int right = Integer.MAX_VALUE;
    for (int i = nums.length - 1; i >= 1; i--) {
        while (!queue.isEmpty() && queue.getLast() < nums[i])	//中间值大才有必要去寻找
            right = queue.removeLast();
        if(nums[i] > right && right > min[i])	return true;
        queue.addLast(nums[i]);
    }
    return false;
}

• 优化：并不需要求出dp，就拿nums[i]和right比较，只要小于就返回true。为什么行？
• 情况1：nums[i]大于等于right了，此时i向左移动，nums[i]持续减小，直到看有没有小于right的
• 情况2：假设i向左移动1，此时值比队尾还大，那么此时，就要将队尾出队，更新right，意味着right又变大或者不变，那么此时寻找合适的i，比right值小就更加容易了
• 正是因为right值会不断变大，才能不漏情况，当然逻辑有点小复杂，而且没有明显复杂度的提高

public boolean find132pattern(int[] nums) {
    Deque<Integer> queue = new LinkedList<>();
    int right = Integer.MIN_VALUE;
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!queue.isEmpty() && queue.getLast() < nums[i])right = queue.removeLast();
        if(nums[i] < right)	return true;
        queue.addLast(nums[i]);
    }
    return false;
}

• 反思：为什么从前遍历不行，看似对称，实则左边元素是最小满足1个条件，但是右边元素需要满足2个条件

L394_字符串解码

题目：输入3[a2[c]]，输出accaccacc

分析：

• 对于嵌套子问题，用递归式最合适的，利用栈的思想
• 一种是if-else if-else形式，i++放外面，这种好处是不用在if里判断是不是越界
• 一种是while+if形式，i++放里面，这种好处是只用判断当前步骤需不需要加1
• 推荐第一种，统一对i++操作，逻辑清晰，对于特殊情况，也可以选第二种

int i = 0;
char[] chs;
public String decodeString(String s) {
    chs = s.toCharArray();
    return dfs().toString();
}
private StringBuilder dfs(){	//3[a2[c]]  acc acc acc
    StringBuilder builder = new StringBuilder();
    int count = 0;
    while (i < chs.length){
        if (Character.isDigit(chs[i]))	count = count * 10 + chs[i] - '0';
        else if(chs[i] == '['){
            i ++;
            StringBuilder sb = dfs();
            while (count > 0){
                builder.append(sb);
                count --;
            }
        }
        else if(chs[i] == ']')	return builder;
        else	builder.append(chs[i]);
        i ++;
    }
    return builder;
}

• 核心点是把什么作为子嵌套，该题中[]是嵌套开始和结束

6.队列

L146_LRU

要做到：get和put时间复杂度O(1)

分析：

• get复杂度为O(1)必为map
• 最近最少适用意味着有个队列，并且队尾可以认为是即将淘汰的
• 当get值时，需要把get的值从队列移除，然后放到队首
• 核心就是LIstNode，包含前后指针，key以及value

L347_前k个高频元素

public int[] topKFrequent(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num : nums)	map.put(num,map.getOrDefault(num,0) + 1);
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, (o1,o2) -> map.get(o1) - map.get(o2));
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        priorityQueue.add(entry.getKey());
        if(priorityQueue.size() > k)	priorityQueue.poll();
    }
    int[] res = new int[k];
    int i = 0;
    for (Integer integer : priorityQueue)	res[i ++] = integer;
    return res;
}

7.递归和动态规划

L72_编辑举例

• 举例：horse和dog，为了便于表示，dp[i][j]表示horse第i个字母和dog第j个字母匹配需要多少步
• 显然，这里r和o不等，那么明显不等于dp[i-1][j-1]
• 这时候，在dp[i-1][j-1]基础上，进行替换操作，那么结果+1即可
• 假设如果dp[i][j-1]是匹配的，即需要n次，那么需要删除元素o，即次数为n+1
• 假设如果dp[i-1][j]匹配需要n次，即ho和do匹配需要n次，那么可以认为把删掉，也可以认为给do后添加r
• 一定意义上，添加和删除是一样的，总之，动态规划，典型与相邻状态相关，非典型的话与题目意义相关

public int minDistance(String word1, String word2) {
    int len1 = word1.length();
    int len2 = word2.length();
    int[][] dp = new int[len1 + 1][len2 + 1];
    for(int i = 0; i <= len1; i ++)	dp[i][0] = i;
    for(int i = 0; i <= len2; i ++)	dp[0][i] = i;       
    for(int i = 1; i <= len1; i ++)
        for (int j = 1; j <= len2; j ++)
            if(word1.charAt(i - 1) == word2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1];
            else 
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;          
    return dp[len1][len2];
}

L139_单词拆分

• 最开始想dfs去搜，但这个题和跳跃问题有点类似，因此动态规划可以用来解

public boolean wordBreak(String s, List<String> wordDict) {
    HashSet<String> set = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 0; i < s.length(); i++) 
        for(int j = i + 1; j <= s.length(); j ++)
            if(dp[i] && set.contains(s.substring(i, j)))
                dp[j] = true; //dp[j]表示前i个可以匹配，然后[i,j)也可以匹配了，即说的是j前可以匹配
    return dp[s.length()];
}

L188_买卖股票的最佳时机IV

public int maxProfit(int k, int[] prices) {
    if(k == 0 || prices.length == 0)    return 0;
    int len = prices.length;
    int[][][] dp = new int[len + 1][2][k + 1];
    for(int i = 0; i < 2; i ++)
        for(int j = 0; j <= k; j ++)
            dp[0][i][j] = Integer.MIN_VALUE / 2;
    dp[0][0][0] = 0;
    for(int i = 0; i < prices.length; i ++){
        dp[i + 1][0][0] = 0;
        dp[i + 1][1][0] = Math.max(dp[i][1][0], dp[i][0][0] - prices[i]);
        for(int j = 1; j < k; j ++){
            dp[i + 1][0][j] = Math.max(dp[i][1][j - 1] + prices[i], dp[i][0][j]);
            dp[i + 1][1][j] = Math.max(dp[i][1][j], dp[i][0][j] - prices[i]);
        }
        dp[i + 1][0][k] = Math.max(dp[i][1][k - 1] + prices[i], dp[i][0][k]);
        dp[i + 1][1][k] = Integer.MIN_VALUE;
    }
    int res = 0;
    for(int i = 0; i < k; i ++){
        res = Math.max(res, dp[len][0][i]);
        res = Math.max(res, dp[len][1][i]);
    }
    res = Math.max(res, dp[len][0][k]);
    return res > 0 ? res : 0;
}

L300_最长递增子序列

分析：

• 两次for循环，dp[i]表示i结尾最大长度
• 优化为nlogn复杂度，状态要边为长度i+1的i增长子序列末尾值，遍历过程就是更新这个数组

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    int maxlen = 0;
    for(int i = 0; i < nums.length; i ++){
        int l = 0; 
        int r = maxlen;
        while(l < r){
            int mid = (l + r) / 2;
            if(dp[mid] < nums[i])   l = mid + 1;
            else    r = mid;	//不能减1，就算一直else，也能保证while循环跳出，这很重要
        }
        dp[l] = nums[i];
        if(l == maxlen) maxlen ++;
    }
    return maxlen;
}

L312_戳气球

题目：n个气球排成一行，依次戳n次，戳完某个气球i，则总分累加：i处的值*i-1处的值*i+1处的值，如果超过数组下标，记为1，戳完的气球从该行移除，戳玩所有气球的最大收益是多少？

分析：

• 对于这种自身规模不断减小，本质寻求每一次的最佳戳球位置，可以联想到矩阵连乘问题，典型的动态规划
• 假如对于第一次戳气球，就要比较：戳0处位置收益+剩余收益，戳1处收益+剩余收益…戳i-1处收益+剩余
• 对于戳i处位置，要求[0 i-1]和[i + 1, len-1]的收益，关键是一旦戳玩第i个气球，原数组将发生变化
• 不行了，所以看答案…往往答案总是在思维上、小技巧上完胜
• 从思维上，dp是肯定的，关键答案选择逆向思维 ，把戳气球当作从无到有填充气球。这种思维在正则表达式等等都有体现。所以逆向思维确实很厉害
• 小技巧的话，通常是观察跟题目密切相关的条件，讲条件用合适的数据结构标识或者从条件中得出推论利用，这个题直接新建len+2的数组，把首位填上1，就类似链表题目中的首指针、尾指针
• 具体的，该如何填充？
• 最主要是思考递归公式，可以从填充1个球问题到填充两个之间的关系，如果rec[i][i]表示填充i，那么等于val[i]*va[i-1]*val[i+1]，那么求rec[i][i+1]，即可以先填充i+1处气球，然后加rec[i][i]，或者先填充i处气球，在加rec[i+1][i+1]，求这两种情况的最大值，第一种：i-1处值*i+1处值*i+处值+rec[i][i]，第二种：i-1处值*i处值*i+2处值，发现共性是：都需要乘i-1处值和i+2处值，因此递推关系也就的出来。
• 在思考，rec[i][j]其实表示的是i到j之外已经填充好了，只剩这里面的没有气球，按某种顺序填充使i到j收益最大，最开始只剩一个空位，遍历所有，然后考虑连续两个空位的情况，紧接着连续三个空位的情况，最终要求的是连续n个空位的收益

public int maxCoins2(int[] nums) {
    int len = nums.length;
    int[] val = new int[len + 2];
    for (int i = 0; i < val.length; i++) {  //预处理
        if(i == 0 || i == val.length - 1)   val[i] = 1;
        else    val[i] = nums[i - 1];
    }
    //需要的数组大小是(0, val.length)
    int[][] rec = new int[len + 2][len + 2];
    for(int i = 0; i < len; i ++){
        rec[i][i + 2] = val[i] * val[i + 1] * val[i + 2]; //注意是开区间，开区间处理逻辑更清晰
    }
    for(int l = 4; l <= len + 2; l ++){	//长度为3已经求过了，所以从4开始，即填充两个空位
        for(int begin = 0; begin <= len + 2 - l; begin ++){
            int temp = 0;
            //统计（begin, begin + l - 1）  长度正好是l  比如[1 2 3 1]，要求(0,1)+(1,3)+val[1]*val[0]*val[3]	和	(0, 3):(0,2) + (2,3) + val[2]*val[0]*val[3]	
            for(int k = begin + 1; k <= begin + l - 2; k ++){
                temp = rec[begin][k] + val[k] * val[begin] * val[begin + l -1] + rec[k][begin + l -1];
                rec[begin][begin + l -1] = Math.max(rec[begin][begin + l -1], temp);
            }

        }
    }
    return rec[0][len + 1];
}

思考：对于dp问题，dp[i][j]应该表示什么，才能被dp[i][j+1]利用

L413_等差数列划分

题目：输入为一维数组，求出等差数列的数量（等差数列长度大于2）

分析：

• 这种其实就是数，但是如果1 3 5 7 9，一旦连续，那么其实就有了动态规划的依赖关系，不要硬数

public int numberOfArithmeticSlices(int[] nums) {
    int len = nums.length;
    int[] dp = new int[len];
    for(int i = 2; i < len; i ++){
        if( nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])	dp[i] = dp[i - 1] + 1;
    int sum = 0;
    for (int i = 0; i < len; i++)	sum += dp[i]; 
    return sum;
}

L91_解码方法

题目：1-26是有对应解码方式，0没有，对于一个字符串，求其可以拆分多少种编码方式

分析：

• 拆分和上楼梯有共同之处，有些时候可以两个连着，有些时候只能一个，甚至有些时候直接返回0

public int numDecodings(String s) {
    char[] chs = s.toCharArray();
    int pre = chs[0] - '0', cur = 0;
    int[] dp = new int[chs.length];
    if(pre == 0)    return 0;
    dp[0] = 1;
    if(chs.length > 1){
        cur = chs[1] - '0';
        if((pre > 1 && cur > 6) || pre > 2){
            if(cur == 0)   return 0;
            dp[1] = 1;
        }else	dp[1] = cur == 0 ? 1 : 2;
        pre = cur;
    }  
    for (int i = 2; i < chs.length; i++) {
        cur = chs[i] - '0';
        if((pre == 0 || pre > 2) && cur == 0)   return 0;
        if((pre > 1 && cur > 6) || pre > 2 || pre == 0)	dp[i] = dp[i - 1];
        else	dp[i] = cur == 0 ? dp[i - 2] : dp[i - 2] + dp[i - 1];
        pre = cur;
    }
    return dp[chs.length - 1];
}

L395_至少有k个重复字符的最长子串

题目：求字符串s的最长字串，要求，s中每一个字符的出现次数都不小于整数k，输出长度

分析:

8.回溯

H301_删除无效括号

题目：给定如"(a))()"形式字符串，要求删除最小括号数量，使之括号合法，返回所有情况

分析

• 一上来，分别从基于规模，首先无法对半分或者按某种规则分割，即分治求解；然后考虑动态规划，发现i到i到i+1的规律很难寻找，贪心通常都不适合返回所有解
• 那么只能枚举所有情况，通常考虑的就是回溯+递归，可是以什么状态去递归呢？
• 再从数据结构角度想，用栈，可以发现第一个多余的右括号，可是也可能使左括号多余，又不行
• 没办法，只能看答案…
• 第一步要做的是统计出到底要删多少右括号，这是很明显也很容易做的，同时也统计要删左括号的数量，就是比右括号多的。左括号不用考虑位置，右括号要考虑位置
• 下一步就是递归，递归就是遍历，针对每个下标i，如果写递归逻辑，要用到哪些状态变量？
• 很明显，下标i算一个，前面求出的要删除的左右括号要放进去，另外，当前的路径即StringBuilder放进去，还有很关键就是当前到底多少个左括号，多少个右括号
• 具体的递归逻辑，其实就一目了然了，大体上分为直接添加到路径和删除当前括号，继续递归两大类情况

int len;
    char[] chs;
    HashSet<String> set;
    public List<String> removeInvalidParentheses(String s) {
        chs = s.toCharArray();
        int lb = 0, rb = 0;
        for (int i = 0; i < chs.length; i++) {
            if(chs[i] == '(')   lb ++;
            else if(chs[i] == ')'){
                if(lb == 0) rb ++;
                if(lb > 0)  lb --;
            }
        }
        len = s.length();
        StringBuilder path = new StringBuilder();
        set = new HashSet<>();
        dfs(0, 0, 0, lb, rb, path);
        return new ArrayList<>(set);
    }
private void dfs(int i, int i1, int i2, int lb, int rb, StringBuilder path) {
    if(len == i) {
        if(i1 == i2)	set.add(path.toString());
        return;
    }
    if(i2 > i1)		return;		//右括号多了，则直接返回 
    if(chs[i] == '('){
        dfs(i + 1, i1 + 1, i2, lb, rb, path.append(chs[i]));	//添加并递归
        path.deleteCharAt(path.length() - 1);	//回溯
        if(lb > 0)	dfs(i + 1, i1, i2, lb - 1, rb, path);	//左括号有多的
    }else if(chs[i] == ')'){
        dfs(i + 1, i1, i2 + 1, lb, rb, path.append(chs[i]));
        path.deleteCharAt(path.length() - 1);	//不能写删i，因为之前有可能添加也可能不添加括号
        if(rb > 0)	dfs(i + 1, i1, i2, lb, rb - 1, path);	//左括号有多的
    }else {
        dfs(i + 1, i1, i2, lb, rb, path.append(chs[i]));
        path.deleteCharAt(path.length() - 1);	//此处不回溯就意味path一直有字母
    }
}

L417_太平洋大西洋水流问题

问题：二维矩阵，左边和上边表示流入太平洋，右边和下边表示流入大西洋，矩阵内可以从高值流向低值（左右和上下方向），求哪些坐标可以同时流向大西洋和太平洋

分析：

• 首先可以把边界搞好，即四周边界标定1表示太平洋，2表示大西洋，3表示都可以
• 然后开始二维遍历，对于(i, j)，可以使用宽搜，直到队列为空也没有满足要求，则不可达，这个过程中是无法记录中间节点到底可达1或者2
• 如果使用深搜，可以搞list，记录下来，把过程也更新一下，奇怪的是复杂度还是很高？？

List<List<Integer>> res, record;
int[][] rec, heights;
int row, col;
boolean[][] flag;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
    res = new ArrayList<>();
    this.heights = heights;
    row = heights.length;
    col = heights[0].length;
    rec = new int[row][col];
    flag = new boolean[row][col];
    for (int i = 0; i < row; i++) {
        rec[i][0] = 1;
        rec[i][col - 1] = 2;
    }
    for (int i = 0; i < col; i++) {
        rec[0][i] = 1;
        rec[row - 1][i] = 2;
    }
    rec[0][col - 1] = 3;
    rec[row - 1][0] = 3;
    if(col == 1 || row == 1){
        for (int i = 0; i < row; i++) 
            for (int j = 0; j < col; j++) res.add(Arrays.asList(i, j));
        return res;
    }
    record = new ArrayList<>();
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            boolean b1 = dfs(i, j, 1);
            boolean b2 = dfs(i, j, 2);
            if(b1 && b2) {
                rec[i][j] = 3;
                res.add(Arrays.asList(i, j));
            }
            else if(b1)   rec[i][j] = 1;
            else if(b2)     rec[i][j] = 2;
            else rec[i][j] = -1;
        }
    }
    return res;
}
private boolean dfs(int i, int j, int ops) {
    if(i < 0 || i >= row || j < 0 || j >= col)  return false;
    if(flag[i][j])  return false;
    if(rec[i][j] == ops || rec[i][j] == 3){
        for (List<Integer> list : record) {
            if(rec[list.get(0)][list.get(1)] + ops == 3){
                rec[list.get(0)][list.get(1)] = 3;
            }else
                rec[list.get(0)][list.get(1)] = ops;
        }
        return true;
    }
    if(rec[i][j] == -1) return false;
    flag[i][j] = true;
    record.add(Arrays.asList(i, j));
    boolean temp = false;
    if(!temp && i + 1 < row && heights[i][j] >= heights[i + 1][j])
        temp |= dfs(i + 1, j, ops);
    if(!temp && i - 1 >= 0 && heights[i][j] >= heights[i - 1][j])
        temp |= dfs(i - 1, j, ops);
    if(!temp && j + 1 < col && heights[i][j] >= heights[i][j + 1])
        temp |= dfs(i, j + 1, ops);
    if(!temp && j - 1 >= 0 && heights[i][j] >= heights[i][j - 1])
        temp |= dfs(i, j - 1, ops);
    flag[i][j] = false;
    record.remove(record.size() - 1);
    return temp;
}

L77_组合

题目：对于数N和k，要求，在1-N中选k个数去组合，输出所有组合（要求排好序）

分析：

• 很明显回溯，既然是排好序，那么回溯的时候，一定要注意下标要增大
• 然后需要思考，需不需要标记位，一般有回头路或者元素重复使用需要标记位

List<List<Integer>> res;
List<Integer> rec;
boolean[] used;
int n, k;
public List<List<Integer>> combine(int n, int k) {
    res = new ArrayList<>();
    rec = new ArrayList<>();
    used = new boolean[n];
    this.n = n;
    this.k = k;
    dfs(1);
    return res;
}
private void dfs(int i) {
    if(rec.size() == k){
        res.add(new ArrayList<>(rec));
        return;
    }
    if(i > n)   return;
    for (int j = i; j <= n; j ++) {
        rec.add(j);
        dfs(j + 1);
        rec.remove(rec.size() - 1);
    }
}

9.位运算

L37_解数独

分析：

• 最开始是用set来存储(i, j )可以使用哪些数字，然后dfs，要用到3个sets数组，存行，列，块
• 对于i位置的候选数字，可以通过位运算压缩空间
  1. row为[0 0 0 0 0 0 1 1 1]表示1，2和3已经出现过，这样，可以使用4-9
  2. 另一个比如col为[0 0 0 0 1 0 1 1 0]表示2，3和5已经使用过，此时row|col表示1，2，3和5已经被使用
  3. 用b来表示(i, j)位置的row|col|block，得到…已经被使用，则~b&0x1ff表示，第n位为1，则n+1可以候选
  4. 用c来表示候选，c&(-c)表示，最低位的1在哪一位，当然这个结果是int类型，调用api得到是第几位即可
  5. 标准回溯过程，先将选择添加进去；递归；将之前的选择回退
  6. 第4步选择过了，就要把它置0，那么c & (c-1)可以达到消除c最低位的1，表示1被选

L338_比特位计数

题目：输入整数n，返回数组，0-n每一个数的二进制有多少个1，要求O(n)复杂度

• 对每个数不断与1与，明显复杂度高于O(n)，另一方面，也说明计算i位置，要么根据某个公式，要么dp
• 分成两种数，一种是上一个是111，下一个是1000，对于这种i&i-1=0
• 另一种，要求1101，只需要求101，在加1

public int[] countBits(int n) {
    int[] res = new int[n + 1];
    int low = 0;
    for(int i = 1; i <= n; i ++){
        if((i & i - 1) == 0){    
            low = i;
            res[i] = 1;
        }
        else	res[i] = res[i - low] + 1;
    }
    return res;
}

10.堆

11.Map

L128_最长连续序列

题目：输入一个无序int数组，求构成连续数值的子集的最大长度

分析：

• 首先，进阶是不使用排序，即用O(n)复杂度
• 必然是伪一次遍历，如果遍历到num，那么怎么知道num+1有没有，num-1有没有，有的话，继续判断num+2，num-2，按这里的逻辑查找的复杂度是O(n)，遍历的复杂度接近O(n*n)
• 一个个优化，查找可以使用hash，采用hashmap或者set，由于只需要知道存不存在，set足够了，即O(1)复杂度的查找必然是哈希
• 遍历的话，似乎没法优化，但是看了答案，有个很重要的优化是，仅考虑单向判断，即num+1，num+2…，这样的好处是，只需判断num-1不在set中的元素，这样，就能省去很多二次遍历，充满利用要求的性质

依次在set找，明显有许多重复性的且不可能是最优解的运算，边界的巧妙判断就避免了无效运算

public int longestConsecutive(int[] nums) {
    int res = 0;
    Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
    for (Integer num : set) {
        if(!set.contains(num - 1)){     //只有这种情况才有可能是边界
            int len = 1;
            while (set.contains(++num))	len ++;
            res = Math.max(res, len);
        }
    }
    return res;
}

L560_和为k的子数组

题目：连续子数组和为k，求个数

分析：

• 首先，该数组包含负数，所以不能滑动窗口
• 最初想法是，用map存每一个下标i对应的可能的值，比如a1 a2 a3，map就存0，a1 + a2，a2三个，依次往后增加，这样结果就是超时
• 连续数组问题，应该利用前缀和，即前5个元素和-前2个元素和=3到5元素之和
• 所以，并不用按第二部那样存，只需存，到每一步累加和放map，这样，当下标到i时，在map中找key为前i个和-k的键，如果有，说明存在这样的前缀和，而且可能多个，这样，就两个前缀和相减自然就是所求子数组

public int subarraySum(int[] nums, int k) {
    HashMap<Integer,Integer> map = new HashMap<>();
    map.put(0,1);	//很灵性的一步
    int sum = 0;
    int count = 0;
    for(int u : nums){
        sum += u;
        if(map.containsKey(sum - k))	count += map.get(sum-k);
        map.put(sum,map.getOrDefault(sum,0)+1);
    }
    return count;
}

12.图

L684_判断二分图

题目：对于无向图，存在两个集合A个B使之分割该图，对于任意一边，一个顶点在A，另一个在B，返回是否可分

分析：对于图的分析，显然不是求解最短距离，那么通常采用遍历。此题可以深搜，也可以用宽搜

DFS

boolean res = true;
int[] color;
int[][] graph;
public boolean isBipartite(int[][] graph) {
    int len = graph.length;
    if(len == 0)    return true;
    this.graph = graph;
    color = new int[len];
    for (int i = 0; i < graph.length; i++) {
        if(color[i] == 0){
            color[i] = 1;
            dfs(i);
        }
    }
    return res;
}
private void dfs(int l) {
    int temp = color[l] == 1 ? 2 : 1;
    for (int g : graph[l]) {
        if(color[g] == color[l]) {
            res = false;
            return;
        }else if(color[g] == 0){
            color[g] = temp;
            dfs(g);
        }
    }
}

BFS

public boolean isBipartite(int[][] graph) {
    int len = graph.length;
    if(len == 0)    return true;
    int[] color = new int[len];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < len; i++) {
        if(deque.size() == 0 && color[i] == 0){
            deque.add(i);
            color[i] = 1;
        }
        while (deque.size() > 0) {
            Integer poll = deque.poll();
            int temp = color[poll];
            for (int in : graph[poll]) {
                if (color[in] == temp) return false;
                if (color[in] == 0) {
                    color[in] = temp == 1 ? 2 : 1;
                    deque.add(in);
                }
            }
        }
    }
    return true;
}

L210_课程表II

题目：给出课程表排序

分析：

• 把依赖关系转为有向图，当某个顶点（即某门课程）没有被指向，说明没有课程依赖它了，此时就可以安排它
• 所以最暴力的方法就是for循环，查看那个顶点的入度为0，出现的话，就记录下来，与此同时，再遍历，把依赖该课程的移除掉
• 然后进入下一轮遍历，最多遍历课程数目轮，可以搞个计数器，最终可以比较是否等于课程数
• 此方法遍历太多

public int[] findOrder(int numCourses, int[][] prerequisites) {
    if (numCourses <= 0) 	return new int[0]
    //[i, j]表示要先j，再i，所以先找到有没有那个下标不出现在依赖位置
    HashSet<Integer>[] sets = new HashSet[numCourses];
    for (int i = 0; i < numCourses; i++) 	sets[i] = new HashSet<>();
    for (int[] ints : prerequisites) {	sets[ints[0]].add(ints[1]);
    int count = 0;
    int[] order = new int[numCourses], used = new int[numCourses];
    boolean find = true;
    while (find){
        find = ! find;
        for (int i = 0; i < sets.length; i++) {
            if(sets[i].size() == 0 && used[i] == 0){
                order[count] = i;
                used[i] = 1;
                find = ! find;
                for (int j = 0; j < sets.length; j++) 
                    if(sets[j].contains(order[count]))	sets[j].remove(order[count]);
                count ++;
                break;
            }
        }
    }
    return count == numCourses ? order : new int[0];
}

• 需要优化：改变sets的存储关系，减少一遍遍历

for (int[] p : prerequisites) {
    sets[p[1]].add(p[0]);	//相反关系，记录的是只有下标i处的课程执行了，那么set[i]里面才可以执行
    inDegree[p[0]]++;	//专门记录长度下标i处的课程依赖的课程数目是多少，为0则可以直接安排
}
while (!queue.isEmpty()) {	//while前要先遍历入队一个元素，才能开始循环
    Integer head = queue.poll();	// 当前入度为 0 的结点
    res[count] = head;
    count++;
    Set<Integer> successors = sets[head];
    for (Integer nextCourse : successors) {
        sets[nextCourse]--;
        if (inDegree[nextCourse] == 0) // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
            queue.offer(nextCourse);
    }
}

L332_重新安排行程

题目：给定一串出发地-目的地行程，指定出发点，求出行程路线，多解返回自然排序

分析：

• 感觉是个回溯过程，即每一步的下一步可能有多种情况，然后选取字母序小的先走

int places = 0;
ArrayList<String> list;
HashMap<String, PriorityQueue<String>> map;
public List<String> findItinerary(List<List<String>> tickets) {
    places = tickets.size() + 1;
    map = new HashMap<>();
    tickets.forEach((li)->{
        if(!map.containsKey(li.get(0)))		map.put(li.get(0), new PriorityQueue<>());
        map.get(li.get(0)).add(li.get(1));
    });
    list = new ArrayList<>();
    list.add("JFK");
    dfs("JFK");
    return list;
}

private boolean dfs(String jfk) {
    if(list.size() == places)	return true;
    if(map.containsKey(jfk)) {
        PriorityQueue<String> strings = new PriorityQueue<>(map.get(jfk));
        ArrayList<String> strs = new ArrayList<>();
        while (strings.size() > 0)	strs.add(strings.poll());	//很重要
        for (String s : strs) {
            map.get(jfk).remove(s);
            list.add(s);
            if (dfs(s))	return true;
            list.remove(list.size() - 1);
            map.get(jfk).offer(s);
        }
    }
    return false;
}

一定要注意：

PriorityQueue<String> strings = new PriorityQueue(){};
strings.addAll(Arrays.asList("AUA", "EZE", "AXA", "EZE", "TIA"));
strings.stream().forEach(System.out::println);
System.out.println("==========================================================");
for(int i = strings.size(); i > 0; i --)	System.out.println(strings.poll());

• 优化点

if(map.containsKey(jfk)) {
    PriorityQueue<String> strings = new PriorityQueue<>(map.get(jfk));
    while(strings.size() > 0) {
        String s = strings.poll();
        map.get(jfk).remove(s);
        list.add(s);
        if (dfs(s))	return true;
        list.remove(list.size() - 1);
        map.get(jfk).offer(s);
    }
}

• 该题其实就是寻找欧拉路径，有经典解法：Hierholzer 算法
• 该算法逆向思维，即先得到最终点，该点即死胡同，然后删除该边，所以得到逆序输出

public void dfs(String curr) {
    while (map.containsKey(curr) && map.get(curr).size() > 0) {
        String tmp = map.get(curr).poll();
        dfs(tmp);
    }
    itinerary.add(curr);
}

13.其它算法

二分法

L69_x的平方根

分析：

• 边界易出错，二分法的边界问题本来就是最容易错的地方，另一个经常出错的地方就是超过int范围

public int mySqrt(int x) {
    int l = 1;	//如果为0，就要考虑后面求s分母为0问题
    int r = x;	//r的选取和l形成对应即可
    int mid = 0;	//很容易出错的是mid*mid和x比较，要考虑会不会越界
    while(l < r){	//一旦不包括等于，那么结束循环后l一定等于r
        mid = l + (r - l) / 2;
        int s = x / mid;	//用除不用乘就是防止越界，其实会缩小s，即mid  ?   x / mid	
        if(mid < s)		l = mid + 1;	//这一步执行很有可能已经超过最终结果
        else if(mid  > s)	r = mid - 1;	
        else	return mid;
    }
    return (long)l * l > x ? l - 1 : l;		//对边界的判断
}

证明：

如果mid > s / mid，说明mid * mid > s / mid * mid，即mid * mid > s/mid * mid，得不出mid * mid > s

很明显：s > s / mid * mid

mid < x / mid可以得到mid * mid < x / mid * mid < x，这种情况下，左边界最大只能是结果+1

mid = x / mid可以得到mid * mid = x / mid * mid < x，直接返回？

并查集

void connect(int a,int b){
    id[find(a)] = find(b);	//找到a和b的父亲，把a这一脉指向b
}
int find(int p){
    while(p != id[p])	p = id[p];	//只要没找到祖先，所谓祖先就是自身不知向任何
    return p;	
}
boolean isConnected(int p, int q){
    return find(p) == find(q);
}

优化：

void connect(int a,int b){
    int i = find(p);
    int j = find(q);
    if(i != j){
        if(size[i] < size[j]){
            id[i] = j;
            size[j] += size[i];
        }else{
            id[j] = i;
            size[i] += size[j];
        }
    }
}
int find(int p){
    while(p != id[p]){
        id[p] = id[id[p]];	//0 1 2 1 4 3	也就是5-->3-->1	这时候就可以让5-->1
        p = id[p];	//只要没找到祖先，所谓祖先就是自身不指向任何
    }
    return p;	
}

模拟

L621_任务的调度器

题目：输入是字符表示不同任务，指定相同任务出现的最小间隔n，求安排所有任务最短时间

分析：

• 如果有3种任务，最小间隔大于等于3，ABCA间隔是2，ABC-A才行
• 如果有4种任务，最小间隔为3，那么ABCDA…
• 如果一开始种类数就少于等于最小间隔，那么明显只取决于最大数量以及和最大数量相同的数量，比如A3B3C2，间隔为3，那么明显ABC-ABC-AB，注意最后的AB (n+1) * (3-1) + 2 = 10
• 如果一开始种类数大于最小间隔，那么刚开始安排肯定没有空隙，后面安排会有空隙吗？
• 比如A3B3C1D1，间隔为3，ABCDAB–AB，只能是这样安排，(n+1) * (3-1) + 2 = 10
• 比如是A3B3C2D2，间隔为2，ABCDABCDAB (n+1)*(3-1) + 2 = 8，此时应该是10，如果间隔为3，就是10；这种情况特殊在：没有空隙的情况下，所谓周期可能不够排的，比如ABCDEFG都1个，间隔是3，显然用上面公式代入是偏小的
• 结论：只要含有空隙，那么就可以按周期排列；不含空隙，可能可以按周期排列，但也可能排不下

public int leastInterval(char[] tasks, int n) {
    int[] buckets = new int[26];
    for(char bucket : tasks)	buckets[bucket - 'A']++;
    Arrays.sort(buckets);
    int maxTimes = buckets[25];
    int maxCount = 1;
    for(int i = 25; i >= 1; i--){
        if(buckets[i] == buckets[i - 1])	maxCount++;
        else	break;
    }
    int res = (maxTimes - 1) * (n + 1) + maxCount;
    return Math.max(res, tasks.length);
}

• 另外，可以真实模拟整个排列过程，步骤是：
  • 判断当前可选任务种类是否大于n，如果大于，就按数量大小，对前n+1大元素依次减1；如果小于，size()个元素减1，来到下一轮
  • 重复第一轮，直到整个size()为0

14.数学找规律