42. 接雨水

單調(diào)遞減棧蒿囤。對于出棧的元素括尸，棧頂元素是左邊第一個比它高的赤拒，待入棧的元素是右邊第一個比它高的敌蜂。這樣的話以左右兩個柱子之間的長度為長捌木，以左右兩個柱子較矮者減去出棧的柱子的高度為寬庸论，這個長方體的面積接到的雨水量就可以確定了。

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int cur = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int h = Math.min(height[stack.peek()], height[i]) - height[cur];
                int w = i - stack.peek() - 1;
                res += h * w;
            }
            stack.push(i);
        }
        return res;
    }
}

4. 尋找兩個正序數(shù)組的中位數(shù)

時間復(fù)雜度O(m+n)厌均，空間復(fù)雜度O(m+n)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        int[] nums = new int[len];
        int i = 0, j = 0, pos = 0;
        while (i < nums1.length && j < nums2.length) {
            nums[pos++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
        while (i < nums1.length) {
            nums[pos++] = nums1[i++];
        }
        while (j < nums2.length) {
            nums[pos++] = nums2[j++];
        }
        return (nums[len / 2] + nums[(len - 1) / 2]) / 2.0;
    }
}

二分，時間復(fù)雜度Olog(m+n)
我們分別找第 (m+n+1) / 2 個告唆，和 (m+n+2) / 2 個數(shù)棺弊，然后求其平均值，就是中位數(shù)擒悬。
這里我們需要定義一個函數(shù)來在兩個有序數(shù)組中找到第K個元素模她，下面重點來看如何實現(xiàn)找到第K個元素。首先懂牧，為了避免產(chǎn)生新的數(shù)組從而增加時間復(fù)雜度侈净，我們使用兩個變量i和j分別來標(biāo)記數(shù)組nums1和nums2的起始位置。然后來處理一些邊界問題僧凤，比如當(dāng)某一個數(shù)組的起始位置大于等于其數(shù)組長度時畜侦，說明其所有數(shù)字均已經(jīng)被淘汰了，相當(dāng)于一個空數(shù)組了躯保，那么實際上就變成了在另一個數(shù)組中找數(shù)字旋膳，直接就可以找出來了。還有就是如果K=1的話途事，那么我們只要比較nums1和nums2的起始位置i和j上的數(shù)字就可以了验懊。難點就在于一般的情況怎么處理？因為我們需要在兩個有序數(shù)組中找到第K個元素尸变，為了加快搜索的速度义图，我們要使用二分法，對K二分召烂，意思是我們需要分別在nums1和nums2中查找第K/2個元素碱工，注意這里由于兩個數(shù)組的長度不定，所以有可能某個數(shù)組沒有第K/2個數(shù)字骑晶，所以我們需要先檢查一下痛垛，數(shù)組中到底存不存在第K/2個數(shù)字，如果存在就取出來桶蛔，否則就賦值上一個整型最大值匙头。如果某個數(shù)組沒有第K/2個數(shù)字，那么我們就淘汰另一個數(shù)字的前K/2個數(shù)字即可仔雷。有沒有可能兩個數(shù)組都不存在第K/2個數(shù)字呢蹂析，這道題里是不可能的舔示，因為我們的K不是任意給的，而是給的m+n的中間值电抚，所以必定至少會有一個數(shù)組是存在第K/2個數(shù)字的惕稻。最后就是二分法的核心啦，比較這兩個數(shù)組的第K/2小的數(shù)字midVal1和midVal2的大小蝙叛，如果第一個數(shù)組的第K/2個數(shù)字小的話俺祠，那么說明我們要找的數(shù)字肯定不在nums1中的前K/2個數(shù)字，所以我們可以將其淘汰借帘，將nums1的起始位置向后移動K/2個蜘渣，并且此時的K也自減去K/2，調(diào)用遞歸肺然。反之蔫缸，我們淘汰nums2中的前K/2個數(shù)字，并將nums2的起始位置向后移動K/2個际起，并且此時的K也自減去K/2拾碌，調(diào)用遞歸即可。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    private double findKth(int[] nums1, int begin1, int[] nums2, int begin2, int k) {
        if (begin1 >= nums1.length) {
            return nums2[begin2 + k - 1];
        }
        if (begin2 >= nums2.length) {
            return nums1[begin1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[begin1], nums2[begin2]);
        }
        int mid1 = begin1 + k / 2 - 1 < nums1.length ? nums1[begin1 + k / 2 - 1] : Integer.MAX_VALUE;
        int mid2 = begin2 + k / 2 - 1 < nums2.length ? nums2[begin2 + k / 2 - 1] : Integer.MAX_VALUE;
        if (mid1 < mid2) {
            return findKth(nums1, begin1 + k / 2, nums2, begin2, k - k / 2);
        } else {
            return findKth(nums1, begin1, nums2, begin2 + k / 2, k - k / 2);
        }
    }
}

25. K 個一組翻轉(zhuǎn)鏈表

先找到每一個組的開頭和結(jié)尾街望，然后記錄上一組的結(jié)尾和下一組的開頭校翔，把這個組翻轉(zhuǎn)之后，再將頭尾結(jié)點和上一組和下一組連好它匕。

class Solution {
    private ListNode reverse(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        for (int i = 0; i < k; i++) {
            ListNode temp = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = temp;
        }
        return dummy.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while (head != null) {
            ListNode tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null) {
                    return dummy.next;
                }
            }
            ListNode nextGroupHead = tail.next;
            tail = head;
            head = reverse(head, k);
            pre.next = head;
            tail.next = nextGroupHead;
            head = nextGroupHead;
            pre = tail;
        }
        return dummy.next;
    }
}

23. 合并K個升序鏈表

使用最小堆展融，每次將最小的結(jié)點彈出，如果這個結(jié)點后面還有鏈表豫柬，將后面的部分繼續(xù)入隊告希，直到隊空為止。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            cur.next = node;
            if (node.next != null) {
                pq.offer(node.next);
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

124. 二叉樹中的最大路徑和

dfs(root)代表以root結(jié)點出發(fā)烧给，到達(dá)某個結(jié)點為止最大路徑和燕偶。
root結(jié)點左側(cè)貢獻(xiàn)的最大路徑和為dfs(root.left)與0的較大值，右側(cè)同理础嫡。
后序遍歷每一個結(jié)點指么，當(dāng)遍歷到根結(jié)點時，左子樹和右子樹的最大路徑和已經(jīng)求出來了榴鼎。找到某個結(jié)點左側(cè)貢獻(xiàn)的最大值+右側(cè)貢獻(xiàn)的最大值+這個結(jié)點的值的最大值即為答案伯诬。

class Solution {
    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        int sum = left + right + root.val;
        res = Math.max(sum, res);
        return root.val + Math.max(left, right);
    }
}

72. 編輯距離

dp[i][j]代表word1的前i個字符與word2的前j個字符的編輯距離。
邊界：一個空字符串到另一個字符串的編輯距離就是另一個字符串的長度巫财。
dp[i][0] = i , dp[0][j] = j
轉(zhuǎn)移方程：
對于word1的第i個字符與word2的第j個字符盗似，如果相等，那么dp[i][j] = dp[i-1][j-1]平项。
如果不相等：
1.可以把word1加一個字符之后與word2相等赫舒，加的這個字符就是word2的第j個字符 dp[i][j] = dp[i][j-1] + 1
2.可以把word1刪一個字符之后與word2相等悍及，刪第i個字符
dp[i][j] = dp[i-1][j] + 1
3.可以把word1修改一個字符之后與word2相等，修改第i個字符
dp[i][j] = dp[i-1][j-1] + 1
dp[i][j]取以上三者最小值接癌。

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

440. 字典序的第K小數(shù)字

類比成一個樹心赶，第一行從1到9，1的子樹為11到19缺猛。
先計算1這棵樹一共有多少個結(jié)點curNum缨叫，如果小于k，說明肯定不在1這棵樹上枯夜。從2開始找第k-curNum小的數(shù)弯汰。如果大于等于k，那么在1這棵樹上湖雹，從11開始找第k-1小的數(shù)。

class Solution {
    public int findKthNumber(int n, int k) {
        int res = 1;
        while (k > 1) {
            long curNum = 0;
            long first = res;
            long next = res + 1;
            while (first <= n) {
                curNum += Math.min(next, (long) (n + 1)) - first;
                next *= 10;
                first *= 10;
            }
            if (curNum < k) {
                //不在當(dāng)前子樹
                res++;
                k -= curNum;
            } else {
                res *= 10;
                k--;
            }

        }
        return res;
    }
}

32. 最長有效括號

dp[i]代表到i位置的最長有效括號曙搬。
邊界：dp[0] = 0
轉(zhuǎn)移方程：
如果s[i] = '(' ,dp[i] = 0
如果s[i] = ')',如果s[i-1] = '('摔吏，那么dp[i] = dp[i-2] + 2
如果s[i-1] = ')' ，那么第i-1位置的')'的最長有效括號長度是dp[i-1]纵装，index = i-dp[i-1]-1是與第i個位置的')'對應(yīng)的括號征讲，如果這個括號是')'，那么d[[i] = 0橡娄。如果這個括號是'('诗箍，那么dp[i] = dp[i-1] + 2 + dp[index-1]

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '(') {
                continue;
            }
            if (s.charAt(i - 1) == '(') {
                dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                res = Math.max(res, dp[i]);
                continue;
            }
            int index = i - dp[i - 1] - 1;
            if (index < 0) {
                continue;
            }
            if (s.charAt(index) == '(') {
                dp[i] = dp[i - 1] + (index - 1 >= 0 ? dp[index - 1] : 0) + 2;
            }
            res = Math.max(res, dp[i]);

        }
        return res;
    }
}

精簡：

class Solution {
    public int longestValidParentheses(String s) {
        int res = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                } else {
                    int index = i - dp[i - 1] - 1;
                    if (index >= 0 && s.charAt(index) == '(') {
                        dp[i] = dp[i - 1] + 2 + (index - 1 >= 0 ? dp[index - 1] : 0);
                    }
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

10. 正則表達(dá)式匹配

比較難理解的是p的第j個數(shù)是*的情況
如果s的第i個數(shù)等于p的第j-1個數(shù) 或者 p的第j-1個數(shù)是 .
dp[i][j] = dp[i-1][j] // a* 記為多個a
or dp[i][j] = dp[i-1][j-2] // a* 記為單個a
or dp[i][j] = dp[i][j-2] // a*記為空
否則
dp[i][j] = dp[i][j-2]

class Solution {
    public boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        boolean[][] dp = new boolean[sLen][pLen];
        dp[0][0] = true;
        for (int j = 2; j <= pLen; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[sLen][pLen];
    }
}

135. 分發(fā)糖果

用一個數(shù)組就行，先初始都分配一個糖果挽唉，再從左往右遍歷滤祖，只要右邊的孩子比左邊的孩子評分高，就把右邊的孩子比左邊孩子多分配一個糖果瓶籽。
再從右往左遍歷匠童，只要左邊的孩子評分比右邊的孩子高，那么左邊孩子分配的糖果數(shù)等于以下兩者較大值：之前分配給左邊孩子的糖果樹與右邊孩子的糖果樹+1塑顺。

class Solution {
    public int candy(int[] ratings) {
        int[] res = new int[ratings.length];
        Arrays.fill(res, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                res[i] = res[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                res[i] = Math.max(res[i], res[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int i : res) {
            sum += i;
        }
        return sum;
    }
}

41. 缺失的第一個正數(shù)

把i位置上的數(shù)?nums[i]放到nums[i]-1位置上去汤求，然后遍歷數(shù)組嘲更，找到第一個nums[i] != i+1的數(shù)龄糊，就是缺失的第一個正數(shù)。注意判斷nums[i]-1位置是否在數(shù)組大小內(nèi)赛蔫。

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] - 1 >= 0 && nums[i] - 1 < nums.length && nums[i] - 1 != i && nums[i] != nums[nums[i] - 1]) {
                swap(i, nums[i] - 1, nums);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    public void swap(int a, int b, int[] nums) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

76. 最小覆蓋子串

滑動窗口裤唠，用left,right表示滑動窗口的左邊界和右邊界挤牛，通過改變left,right來擴(kuò)展和收縮滑動窗口。先不斷增加right使滑動窗口增大巧骚，直到窗口包含了t的所有元素
赊颠，再不斷增加left使滑動窗口縮小格二，直到減去一個必須包含的元素，記錄此時滑動窗口沒減去之前的長度竣蹦，并保存最小值顶猜。減去之后滑動窗口肯定不滿足條件了，那么繼續(xù)移動右窗口痘括，直到包含t所有元素长窄，重復(fù)以上步驟。找到最小覆蓋子串纲菌。

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        int[] window = new int[128];
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        String res = "";
        int minLen = Integer.MAX_VALUE;
        int cnt = 0;
        for (int r = 0, l = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            window[c]++;
            if (need[c] > 0 && window[c] <= need[c]) {
                cnt++;
            }
            while (cnt == t.length()) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    res = s.substring(l, r + 1);
                }
                char ch = s.charAt(l);
                l++;
                window[ch]--;
                if (need[ch] > 0 && window[ch] < need[ch]) {
                    cnt--;
                }
            }
        }
        return res;
    }
}

84. 柱狀圖中最大的矩形

單調(diào)遞增棧挠日。對于出棧的元素cur，當(dāng)前待入棧的元素i是右邊第一個比它矮的柱子翰舌，棧頂元素peek是左邊第一個比它矮的柱子嚣潜，對于高為heights[cur]的最大矩形面積已可以計算，寬等于 i - stack.peek() - 1椅贱。
采用哨兵機制可以減少椂悖空的判斷。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = newHeights[heights.length + 1] = 0;
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        heights = newHeights;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int cur = stack.pop();
                int h = heights[cur];
                int w = i - stack.peek() - 1;
                res = Math.max(res, h * w);
            }
            stack.push(i);
        }
        return res;
    }
}

128. 最長連續(xù)序列

哈希表庇麦，先將所有數(shù)加入到HashSet中计技，再遍歷每個數(shù)，只要set中不存在num-1山橄，那么就有可能是連續(xù)序列的起始位置垮媒。然后不斷判斷num往上加1之后，set中是否存在航棱，直到找到最長的序列睡雇。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        int res = 0;
        for (int i : nums) {
            if (!set.contains(i - 1)) {
                int count = 1;
                while (set.contains(i + 1)) {
                    count++;
                    i++;
                }
                res = Math.max(res, count);
            }
        }
        return res;
    }
}

并查集：

class Solution {
    int[] father;
    int[] size;
    int res = 1;

    private void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    private int findFather(int x) {
        while (father[x] != x) {
            x = father[x];
        }
        return x;
    }

    private void union(int a, int b) {
        int fA = findFather(a);
        int fB = findFather(b);
        if (fA != fB) {
            father[fA] = fB;
            size[fB] += size[fA];
            res = Math.max(res, size[fB]);
        }
    }

    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        father = new int[nums.length];
        size = new int[nums.length];
        init();
        for (int i : nums) {
            if (map.containsKey(i + 1)) {
                union(map.get(i), map.get(i + 1));
            }
        }
        return res;
    }
}

45. 跳躍游戲 II

curPos不斷右移，達(dá)到end位置時丧诺，需要進(jìn)行下一跳入桂，res+1。
注意當(dāng)curPos走到最后一個位置時驳阎，不管是否等于end抗愁，都不需要跳了。所以遍歷條件寫while(curPos < nums.length - 1)即可呵晚。

class Solution {
    public int jump(int[] nums) {
        int curPos = 0;//當(dāng)前位置
        int maxPos = 0;//最遠(yuǎn)可到達(dá)的位置
        int end = 0;//當(dāng)前要到達(dá)的位置
        int res = 0;
        while (curPos < nums.length - 1) {
            maxPos = Math.max(maxPos, curPos + nums[curPos]);
            if (curPos == end) {
                res++;
                end = maxPos;
            }
            curPos++;
        }
        return res;
    }
}

85. 最大矩形

轉(zhuǎn)化成第84題蜘腌。
把圖形的每一排開始看做一個柱狀圖，就是求多個柱狀圖中的最大矩形饵隙。

class Solution {
    private int cal(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = newHeights[heights.length + 1] = 0;
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        heights = newHeights;
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int cur = stack.pop();
                int h = heights[cur];
                int w = i - stack.peek() - 1;
                res = Math.max(res, h * w);
            }
            stack.push(i);
        }
        return res;
    }

    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '0') {
                    heights[j] = 0;
                } else {
                    heights[j]++;
                }
            }
            res = Math.max(res, cal(heights));
        }
        return res;
    }
}

51. N 皇后

轉(zhuǎn)化成全排列問題撮珠，對于所有的全排列情況，i,arr[i]代表皇后在第i行第arr[i]列金矛。這樣一定在不同行不同列芯急，然后只需判斷所有的皇后是否不在斜線上就行了勺届。

class Solution {
    List<List<String>> res = new ArrayList<>();
    int[] arr;
    boolean[] isVisited;

    private boolean judge(int n) {
        boolean flag = true;
        label:
        for (int i = 1; i <= n; i++) {//第i行的皇后和后面所有行的皇后判斷是否在對角線上
            for (int j = i + 1; j <= n; j++) {
                if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) {
                    flag = false;
                    break label;
                }
            }
        }
        return flag;

    }

    private void dfs(int begin, int n) {
        if (begin == n + 1) {
            if (judge(n) == true) {
                List<String> list = new ArrayList<>();
                for (int i = 1; i <= n; i++) {
                    StringBuilder sb = new StringBuilder();
                    for (int j = 1; j <= n; j++) {
                        if (j == arr[i]) {
                            sb.append('Q');
                        } else {
                            sb.append('.');
                        }
                    }
                    list.add(sb.toString());
                }
                res.add(list);
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisited[i] == false) {
                arr[begin] = i;
                isVisited[i] = true;
                dfs(begin + 1, n);
                isVisited[i] = false;
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        arr = new int[n + 1];
        isVisited = new boolean[n + 1];
        dfs(1, n);
        return res;
    }
}

329. 矩陣中的最長遞增路徑

記憶化dfs:
由于同一個單元格對應(yīng)的最長遞增路徑的長度是固定不變的，因此可以使用記憶化的方法進(jìn)行優(yōu)化娶耍。用矩陣memo作為緩存矩陣免姿，已經(jīng)計算過的單元格的結(jié)果存儲到緩存矩陣中。

class Solution {
    int[][] memo;
    int[] dirX = {1, -1, 0, 0};
    int[] dirY = {0, 0, 1, -1};

    private int dfs(int i, int j, int[][] matrix) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        memo[i][j]++;
        for (int k = 0; k < 4; k++) {
            int newI = i + dirX[k];
            int newJ = j + dirY[k];
            if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length && matrix[newI][newJ] > matrix[i][j]) {
                memo[i][j] = Math.max(memo[i][j], dfs(newI, newJ, matrix) + 1);
            }
        }
        return memo[i][j];
    }

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        memo = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dfs(i, j, matrix));
            }
        }
        return res;
    }
}

297. 二叉樹的序列化與反序列化

序列化的時候榕酒，如果根結(jié)點為null胚膊，直接返回"null"。如果根結(jié)點不為null想鹰，使用層次遍歷紊婉，注意稍微有一點區(qū)別，就是某個結(jié)點的左右子樹不管是否為空辑舷，都加入到隊列中喻犁。出隊的時候判斷結(jié)點是否為空，如果為空何缓，結(jié)果集中加入"null"株汉，然后進(jìn)行下一次出隊。如果不為空歌殃，那么結(jié)果集加入這個結(jié)點的值，然后把這個結(jié)點的左右子樹都入隊蝙云。
反序列化的時候氓皱，如果就等于"null"，直接返回null勃刨。否則按照“ , ” 分割數(shù)組波材，先把根結(jié)點創(chuàng)建出來，值等于split[0]身隐。 根結(jié)點入隊廷区。然后遍歷分割后的數(shù)組，每一次出隊的結(jié)點贾铝，去建立它的左右子樹隙轻。最后返回根結(jié)點。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "null";
        }
        StringBuilder res = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode front = q.poll();
                if (front == null) {
                    res.append("null,");
                    continue;
                } else {
                    res.append(front.val + ",");
                    q.offer(front.left);
                    q.offer(front.right);
                }
            }
        }
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if ("null".equals(data)) {
            return null;
        }
        String[] splits = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(splits[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        for (int i = 1; i < splits.length; i++) {
            TreeNode front = q.poll();
            if (!"null".equals(splits[i])) {
                front.left = new TreeNode(Integer.parseInt(splits[i]));
                q.offer(front.left);
            }
            i++;
            if (!"null".equals(splits[i])) {
                front.right = new TreeNode(Integer.parseInt(splits[i]));
                q.offer(front.right);
            }
        }
        return root;
    }
}

354. 俄羅斯套娃信封問題

相當(dāng)于二維的最長遞增子序列問題垢揩。先把信封按第一維寬度從小到大排列玖绿。
然后對第二維求最長遞增子序列，稍微有點區(qū)別的地方就是在求dp的時候叁巨，要保證第一個維度也要嚴(yán)格小于斑匪。

class Solution {
    private int lis(int[][] envelopes) {
        int[] dp = new int[envelopes.length];
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < envelopes.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (envelopes[j][1] < envelopes[i][1] && envelopes[j][0] < envelopes[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) {
            return 0;
        }
        Arrays.sort(envelopes, (o1, o2) -> o1[0] - o2[0]);
        return lis(envelopes);
    }
}

劍指 Offer 51. 數(shù)組中的逆序?qū)?/a>

    public void mergeSort(int[] arr, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(arr, lo, mid);
        mergeSort(arr, mid + 1, hi);
        int[] temp = new int[hi - lo + 1];
        int i = lo, j = mid + 1, pos = 0;
        while (i <= mid && j <= hi) {
            temp[pos++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[pos++] = arr[i++];
        }
        while (j <= hi) {
            temp[pos++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, lo, pos);
    }

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] arr, int lo, int hi) {
        if (lo >= hi) {
            return 0;
        }
        int mid = lo + (hi - lo) / 2;
        int res = mergeSort(arr, lo, mid) + mergeSort(arr, mid + 1, hi);
        int[] temp = new int[hi - lo + 1];
        int i = lo, j = mid + 1, pos = 0;
        while (i <= mid && j <= hi) {
            res += arr[i] <= arr[j] ? 0 : mid + 1 - i;//arr[j]小垫释，從i到mid的所有數(shù)與j構(gòu)成逆序?qū)
            temp[pos++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[pos++] = arr[i++];
        }
        while (j <= hi) {
            temp[pos++] = arr[j++];//此時arr[j]比左邊的所有數(shù)都大了丝格，不可能構(gòu)成逆序?qū)?        }
        System.arraycopy(temp, 0, arr, lo, pos);
        return res;
    }
}

460. LFU 緩存

使用平衡二叉樹來記錄順序關(guān)系。
使用map緩存某個key是否在樹中棵譬。

class LFUCache {
    Map<Integer, Node> cache;
    TreeSet<Node> treeSet;
    int timestamp;
    int capacity;

    class Node implements Comparable<Node> {
        int key;
        int value;
        int time;
        int count;

        public Node(int key, int value, int time, int count) {
            this.key = key;
            this.value = value;
            this.time = time;
            this.count = 0;
        }

        @Override
        public int compareTo(Node o) {
            return count != o.count ? count - o.count : time - o.time;
        }
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.timestamp = 0;
        this.cache = new HashMap<>();
        this.treeSet = new TreeSet<>();
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        } else {
            treeSet.remove(node);
            node.count++;
            node.time = ++timestamp;
            treeSet.add(node);
            return node.value;
        }
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node node = cache.get(key);
        if (node == null) {
            node = new Node(key, value, ++timestamp, 1);
            if (treeSet.size() == capacity) {
                cache.remove(treeSet.first().key);
                treeSet.remove(treeSet.first());
            }
            cache.put(key, node);
            treeSet.add(node);
        } else {
            treeSet.remove(node);
            node.value = value;
            node.count++;
            node.time = ++timestamp;
            treeSet.add(node);
        }
    }
}

239. 滑動窗口最大值

單調(diào)隊列显蝌，從隊頭到隊尾單調(diào)遞減，隊頭存儲的永遠(yuǎn)是窗口中最大的值订咸。
對于一個要進(jìn)隊的數(shù)來說曼尊，如果隊尾的數(shù)比它小，那么這個隊尾的數(shù)不可能是窗口的最大值脏嚷，直接把隊尾的數(shù)出隊骆撇，再把這個數(shù)進(jìn)隊。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> q = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
                q.pollLast();
            }
            q.addLast(i);
            if (q.peekFirst() <= i - k) {
                q.pollFirst();
            }
            if (i - k + 1 >= 0) {
                res[i - k + 1] = nums[q.peekFirst()];
            }
        }
        return res;
    }
}

726. 原子的數(shù)量

44. 通配符匹配

如果p.charAt(j - 1) == '*'
*匹配空字符串,dp[i][j] = dp[i][j-1]
*匹配多個字符,dp[i][j] = dp[i-1][j]

class Solution {
    public boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        dp[0][0] = true;
        for (int j = 1; j <= pLen; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        return dp[sLen][pLen];
    }
}

123. 買賣股票的最佳時機 III

dp[i][j][k]代表第i天結(jié)束時父叙，已經(jīng)進(jìn)行了j次交易神郊，手中還有k份股票的最大收益。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[][][] dp = new int[prices.length][3][2];
        for (int j = 1; j <= 2; j++) {
            dp[0][j][1] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j <= 2; j++) {
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
            }
        }
        return dp[prices.length - 1][2][0];
    }
}

97. 交錯字符串

dp[i][j]代表s1的前i個字符與s2的前j個字符是否可以交錯組成s3的前i+j個字符
邊界：
dp[0][0] = true ,若 s1的前i個字符等于s3的前i個字符dp[i][0] = true , 若s2的前j個字符等于s3的前j個字符dp[0][j] = true趾唱。
轉(zhuǎn)移方程：
若s1的第i個字符等于s3的第i+j個字符涌乳，且dp[i-1][j] = true， 那么dp[i][j] = true
若s2的第j個字符等于s3的第i+j個字符甜癞，且dp[i][j-1] = true夕晓，那么dp[i][j] = true

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        for (int j = 1; j <= n; j++) {
            if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) {
                    dp[i][j] = true;
                } else if (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[m][n];
    }
}

887. 雞蛋掉落

public class Solution {

    public int superEggDrop(int K, int N) {

        // dp[i][j]：一共有 i 層樓梯的情況下，使用 j 個雞蛋的最少實驗的次數(shù)
        // 注意：
        // 1悠咱、i 表示的是樓層的大小蒸辆，不是第幾層的意思，例如樓層區(qū)間 [8, 9, 10] 的大小為 3乔煞，這一點是在狀態(tài)轉(zhuǎn)移的過程中調(diào)整的定義
        // 2吁朦、j 表示可以使用的雞蛋的個數(shù)，它是約束條件渡贾，我個人習(xí)慣放在后面的維度逗宜，表示消除后效性的意思

        // 0 個樓層和 0 個雞蛋的情況都需要算上去，雖然沒有實際的意義，但是作為遞推的起點纺讲，被其它狀態(tài)值所參考
        int[][] dp = new int[N + 1][K + 1];

        // 由于求的是最小值擂仍，因此初始化的時候賦值為一個較大的數(shù)，9999 或者 i 都可以
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], i);
        }

        // 初始化：填寫下標(biāo)為 0熬甚、1 的行和下標(biāo)為 0逢渔、1 的列
        // 第 0 行：樓層為 0 的時候，不管雞蛋個數(shù)多少乡括，都測試不出雞蛋的 F 值肃廓，故全為 0
        for (int j = 0; j <= K; j++) {
            dp[0][j] = 0;
        }

        // 第 1 行：樓層為 1 的時候，0 個雞蛋的時候诲泌，扔 0 次盲赊，1 個以及 1 個雞蛋以上只需要扔 1 次
        dp[1][0] = 0;
        for (int j = 1; j <= K; j++) {
            dp[1][j] = 1;
        }

        // 第 0 列：雞蛋個數(shù)為 0 的時候，不管樓層為多少敷扫，也測試不出雞蛋的 F 值哀蘑，故全為 0
        // 第 1 列：雞蛋個數(shù)為 1 的時候，這是一種極端情況葵第，要試出 F 值绘迁，最少次數(shù)就等于樓層高度（想想復(fù)雜度的定義）
        for (int i = 0; i <= N; i++) {
            dp[i][0] = 0;
            dp[i][1] = i;
        }

        // 從第 2 行，第 2 列開始填表
        for (int i = 2; i <= N; i++) {
            for (int j = 2; j <= K; j++) {
                for (int k = 1; k <= i; k++) {
                    // 碎了卒密，就需要往低層繼續(xù)扔：層數(shù)少 1 缀台，雞蛋也少 1
                    // 不碎，就需要往高層繼續(xù)扔：層數(shù)是當(dāng)前層到最高層的距離差哮奇，雞蛋數(shù)量不少
                    // 兩種情況都做了一次嘗試将硝，所以加 1
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
                }
            }
        }
        return dp[N][K];
    }
}

public class Solution {
    private int cal(int K, int T) {
        if (T == 1 || K == 1) {
            return T + 1;
        }
        return cal(K - 1, T - 1) + cal(K, T - 1);
    }

    public int superEggDrop(int K, int N) {
        int T = 1;
        while (cal(K, T) < N + 1) {
            T++;
        }
        return T;
    }
}

315. 計算右側(cè)小于當(dāng)前元素的個數(shù)

注意這道題只能在i增加的過程中計算逆序?qū)Φ膫€數(shù)，因為i增加時屏镊，從mid+1到j(luò)-1個數(shù)都是右側(cè)小于當(dāng)前元素的個數(shù)。還要使用一個數(shù)組來保存每個數(shù)的初始位置痰腮。

class Solution {
    int[] res;
    int[] index;//當(dāng)前位置的數(shù)對應(yīng)原數(shù)組的第幾個位置

    public List<Integer> countSmaller(int[] nums) {
        res = new int[nums.length];
        index = new int[nums.length];
        for (int i = 0; i < index.length; i++) {
            index[i] = i;
        }
        mergeSort(nums, 0, nums.length - 1);
        return Arrays.stream(res).boxed().collect(Collectors.toList());
    }

    private void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        int[] temp = new int[hi - lo + 1];
        int[] tempindex = new int[hi - lo + 1];
        int i = lo, j = mid + 1, pos = 0;
        while (i <= mid && j <= hi) {
            res[index[i]] += nums[i] <= nums[j] ? j - mid - 1 : 0;
            tempindex[pos] = nums[i] <= nums[j] ? index[i] : index[j];
            temp[pos++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= mid) {
            res[index[i]] += j - mid - 1;
            tempindex[pos] = index[i];
            temp[pos++] = nums[i++];
        }
        while (j <= hi) {
            tempindex[pos] = index[j];
            temp[pos++] = nums[j++];
        }
        System.arraycopy(tempindex, 0, index, lo, pos);
        System.arraycopy(temp, 0, nums, lo, pos);
    }
}

493. 翻轉(zhuǎn)對

在歸并排序的過程中計算翻轉(zhuǎn)對而芥，注意和之前的區(qū)別是要先單獨統(tǒng)計一次，因為題目要統(tǒng)計的條件是nums[i] > 2 * nums[j]膀值，而合并的時候條件只是nums[i]與nums[j]比較棍丐。

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return 0;
        }
        int mid = lo + (hi - lo) / 2;
        int res = 0;
        res += mergeSort(nums, lo, mid) + mergeSort(nums, mid + 1, hi);
        int[] temp = new int[hi - lo + 1];
        int i = lo, j = mid + 1, pos = 0;
        //先單獨統(tǒng)計，因為合并的時候統(tǒng)計不了
        while (i <= mid && j <= hi) {
            if ((long) nums[i] > 2 * (long) nums[j]) {
                res += mid - i + 1;
                j++;
            } else {
                i++;
            }
        }
        i = lo;
        j = mid + 1;
        while (i <= mid && j <= hi) {
            temp[pos++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= mid) {
            temp[pos++] = nums[i++];
        }
        while (j <= hi) {
            temp[pos++] = nums[j++];
        }
        System.arraycopy(temp, 0, nums, lo, pos);
        return res;
    }
}

407. 接雨水 II

對于每一個塊沧踏，去找它四個方向最高的高度中的最小值作為上界歌逢，當(dāng)前塊作為下界。 我們從矩陣的最外圍往里面遍歷翘狱，像一個圈不斷縮小的過程秘案，為了防止重復(fù)遍歷用visited記錄，其次要用小根堆(以高度為判斷基準(zhǔn))來存入所有快的四周(即圈是不斷縮小的，小頂堆存的就是這個圈)
為什么要讓高度較小的塊先出隊阱高？(關(guān)鍵點)

1. 一開始時候就講了基礎(chǔ)做法是：對于每一個塊赚导，去找它四個方向最高的高度中的最小值(二維下則是左右最高的高度取較小的那一個)作為上界，當(dāng)前塊作為下界
2. 而我們現(xiàn)在反過來不是以中心塊為處理單元赤惊，而是以四周作為處理單元
3. 我們?nèi)绻艽_保當(dāng)前出隊的元素對于該中心塊來說是它周圍四個高度中的最小值那么就能確定接雨水的大小
4. 為什么隊頭元素的高度比中心塊要高它就一定是中心塊周圍四個高度中的最小值呢吼旧？
   因為我們的前提就是小頂堆：高度小的塊先出隊，所以對于中心塊來說未舟，先出隊的必然是中心塊四周高度最小的那一個

• 步驟：
  1. 構(gòu)建小頂堆圈暗，初始化為矩陣的最外圍(邊界所有元素)
  2. 不斷出隊，倘若隊頭元素的四周有中心塊比隊頭矮裕膀，即代表能夠接雨水：隊頭元素減去該中心塊即當(dāng)前中心塊能接雨水的值
  3. 但是接完雨水之后中心塊還要存進(jìn)隊列中员串，但這時要存入的中心塊是接完雨水后的中心塊
     */

class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap.length == 0) {
            return 0;
        }
        Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        int row = heightMap.length;
        int col = heightMap[0].length;
        boolean[][] isVisited = new boolean[row][col];
        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                    pq.offer(new int[]{i, j, heightMap[i][j]});
                    isVisited[i][j] = true;
                }
            }
        }
        int[] dirX = {1, -1, 0, 0};
        int[] dirY = {0, 0, 1, -1};
        while (!pq.isEmpty()) {
            int[] front = pq.poll();
            for (int i = 0; i < 4; i++) {
                int nx = front[0] + dirX[i];
                int ny = front[1] + dirY[i];
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && isVisited[nx][ny] == false) {
                    if (heightMap[nx][ny] < front[2]) {
                        res += front[2] - heightMap[nx][ny];
                    }
                    pq.offer(new int[]{nx, ny, Math.max(heightMap[nx][ny], front[2])});
                    isVisited[nx][ny] = true;
                }
            }
        }
        return res;
    }
}

295. 數(shù)據(jù)流的中位數(shù)

設(shè)置一個最大堆和一個最小堆。
把數(shù)據(jù)流所有數(shù)按順序分為兩半魂角，左邊的數(shù)全部在最大堆中昵济，堆頂就是左邊最大的數(shù)。右邊的數(shù)全部放在最小堆中野揪，堆頂就是右邊最小的數(shù)访忿。保證最大堆永遠(yuǎn)比最小堆多一個數(shù)或相等。每次先入最大堆斯稳，入完之后把最大堆堆頂出到最小堆中海铆。如果此時最小堆的數(shù)比最大堆還多一個，那就把最小堆的堆頂再出到最大堆中挣惰。
最后答案就是最大堆的堆頂或者兩個堆頂?shù)钠骄怠?/p>

class MedianFinder {

    Queue<Integer> maxHeap;
    Queue<Integer> minHeap;
    int count;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        this.minHeap = new PriorityQueue<>();
        this.maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        this.count = 0;
    }

    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if (count % 2 == 0) {
            maxHeap.add(minHeap.poll());
        }
        count++;
    }

    public double findMedian() {
        if (count % 2 == 0) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

188. 買賣股票的最佳時機 IV

dp[i][j][k]代表第i天結(jié)束時卧斟，已經(jīng)進(jìn)行了j次買入交易，手中持有k份股票的最大收益憎茂。

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[][][] dp = new int[prices.length][k + 1][2];
        for (int j = k; j >= 1; j--) {
            dp[0][j][1] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = k; j >= 1; j--) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[prices.length - 1][k][0];
    }
}

862. 和至少為 K 的最短子數(shù)組

先計算前綴和珍语，preSum[i]代表前i個數(shù)的和。
目標(biāo)找到preSum[y] - preSum[x] >= K且y - x最小竖幔。
暴力法超時：

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int len = A.length;
        long[] preSum = new long[len + 1];
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + (long) A[i];
        }
        int res = len + 1;
        for (int i = len; i >= 1; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (preSum[i] - preSum[j] >= K) {
                    res = Math.min(res, i - j);
                    break;
                }
            }
        }
        return res < len + 1 ? res : -1;
    }
}

單調(diào)隊列板乙，從隊尾到隊頭preSum遞減。遍歷拳氢，待入隊的preSum[i]如果小于等于隊尾募逞，隊尾可以直接出隊。因為如果從隊尾開始的某段子數(shù)組和大于等于K馋评，那么從i位置開始的某段子數(shù)組和也一定大于等于K放接。然后判斷隊頭到i的子數(shù)組是否大于等于K，如果滿足留特，不斷把隊頭出隊纠脾，直到不滿足為止玛瘸。

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int len = A.length;
        long[] preSum = new long[len + 1];
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + (long) A[i];
        }
        int res = len + 1;
        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < len + 1; i++) {
            while (!q.isEmpty() && preSum[i] <= preSum[q.getLast()]) {
                q.removeLast();
            }
            while (!q.isEmpty() && preSum[i] >= preSum[q.getFirst()] + K) {
                res = Math.min(res, i - q.removeFirst());
            }
            q.addLast(i);
        }
        return res < len + 1 ? res : -1;
    }
}

312. 戳氣球

dp[i][j] 表示開區(qū)間 (i,j) 內(nèi)你能拿到的最多金幣，注意是開區(qū)間乳乌，所以dp[i][i]和dp[i][i+1]初始都為0捧韵。
把數(shù)組左右多加一個數(shù)1。這樣最后的答案就是dp[0][len-1]
k是最后戳破的氣球汉操。

class Solution {
    public int maxCoins(int[] nums) {
        int[] newNums = new int[nums.length + 2];
        newNums[0] = newNums[nums.length + 1] = 1;//注意這里是1再来，不是0
        System.arraycopy(nums, 0, newNums, 1, nums.length);
        nums = newNums;
        int[][] dp = new int[nums.length][nums.length];
        for (int L = 3; L <= nums.length; L++) {
            for (int i = 0; i + L - 1 < nums.length; i++) {
                int j = i + L - 1;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
                }
            }
        }
        return dp[0][nums.length - 1];
    }
}

224. 基本計算器

class Solution {
    Map<String, Integer> inPriority, outPriority;

    public Solution() {
        inPriority = new HashMap<>();//棧內(nèi)優(yōu)先級
        outPriority = new HashMap<>();//棧外優(yōu)先級
        inPriority.put("#", 0);
        inPriority.put("(", 1);
        inPriority.put("*", 5);
        inPriority.put("/", 5);
        inPriority.put("+", 3);
        inPriority.put("-", 3);
        inPriority.put(")", 6);
        outPriority.put("#", 0);
        outPriority.put("(", 6);
        outPriority.put("*", 4);
        outPriority.put("/", 4);
        outPriority.put("+", 2);
        outPriority.put("-", 2);
        outPriority.put(")", 1);
    }

    public int calculate(String s) {
        List<String> infix = new ArrayList<>();//中綴表達(dá)式
        boolean flag = false;
        int num = 0;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                continue;
            } else if (Character.isDigit(c)) {
                flag = true;
                num = num * 10 + (c - '0');
            } else {
                if (flag == true) {
                    infix.add(String.valueOf(num));
                    flag = false;
                    num = 0;
                }
                infix.add(String.valueOf(c));
            }
        }
        if (flag == true) {
            infix.add(String.valueOf(num));
        }
        List<String> rpn = getRpn(infix);
        return (int) cal(rpn);
    }

    //中綴表達(dá)式轉(zhuǎn)后綴
    public List<String> getRpn(List<String> infix) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("#");
        List<String> rpn = new ArrayList<>();
        for (String str : infix) {
            if ("(".equals(str) || ")".equals(str) || "+".equals(str) || "-".equals(str) ||
                    "*".equals(str) || "/".equals(str)) {
                if (comparePriority(stack.peek(), str) == 1) {
                    stack.push(str);
                } else if (comparePriority(stack.peek(), str) == 0) {
                    stack.pop();
                } else {
                    while (comparePriority(stack.peek(), str) == -1) {
                        String z = stack.pop();
                        rpn.add(z);
                    }
                    if (")".equals(str)) {
                        stack.pop();
                    } else {
                        stack.push(str);
                    }
                }
            } else {
                rpn.add(str);
            }
        }
        while (!stack.isEmpty()) {
            rpn.add(stack.pop());
        }
        rpn.remove(rpn.size() - 1);
        return rpn;
    }

    private int comparePriority(String in, String out) {
        if (outPriority.get(out) > inPriority.get(in)) {
            return 1;
        } else if (outPriority.get(out) == inPriority.get(in)) {
            return 0;
        } else {
            return -1;
        }
    }

    //后綴表達(dá)式求值
    public double cal(List<String> s) {
        Deque<Double> stack = new ArrayDeque<>();
        for (int i = 0; i < s.size(); i++) {
            double a, b;
            if (s.get(i).equals("+")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a + b);
                continue;
            } else if (s.get(i).equals("-")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a - b);
                continue;
            } else if (s.get(i).equals("*")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a * b);
                continue;
            } else if (s.get(i).equals("/")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a / b);
                continue;
            } else {
                stack.push(Double.valueOf(s.get(i)));
            }
        }
        return stack.peek();
    }
}

403. 青蛙過河

dp[i]代表可以以大小為step的一跳跳到第i個位置的集合。
邊界：
dp[0]的集合只有一個元素0磷瘤，只需要0跳就可以到達(dá)第一個位置芒篷。
轉(zhuǎn)移方程：
遍歷集合，那么下一跳可以跳的步數(shù)為step-1 ~ step+1采缚，判斷可以到達(dá)的位置是否有石塊针炉，如果有，就把那個石塊對應(yīng)的集合增加這一跳的步數(shù)扳抽。
最后判斷最后一個石頭的集合是否為空即可篡帕。如果不為空，說明可以跳到這里來贸呢。

class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < stones.length; i++) {
            map.put(stones[i], i);
        }
        Set<Integer>[] dp = new HashSet[stones.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new HashSet<>();
        }
        dp[0].add(0);
        for (int i = 0; i < stones.length; i++) {
            for (int j : dp[i]) {
                for (int step = j - 1; step <= j + 1; step++) {
                    if (step > 0 && map.containsKey(stones[i] + step)) {
                        dp[map.get(stones[i] + step)].add(step);
                    }
                }
            }
        }
        return dp[stones.length - 1].size() > 0;
    }
}

679. 24 點游戲

回溯镰烧，遍歷所有情況，只要有一種情況滿足24點楞陷，返回true怔鳖。
注意作除法時，分母如果等于0固蛾，直接continue结执。
1e-6是浮點型誤差，只要結(jié)果與24之差在這個范圍內(nèi)就可以看成等于24艾凯。

class Solution {
    private boolean dfs(List<Double> list) {
        if (list.size() == 1) {
            return Math.abs(list.get(0) - 24) < 1e-6;
        }
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.size(); j++) {
                if (i == j) {
                    continue;
                }
                List<Double> newList = new ArrayList<>();
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) {
                        newList.add(list.get(k));
                    }
                }
                for (int k = 0; k < 4; k++) {
                    double a = list.get(i);
                    double b = list.get(j);
                    if (k == 0) {
                        newList.add(a + b);
                    } else if (k == 1) {
                        newList.add(a - b);
                    } else if (k == 2) {
                        newList.add(a * b);
                    } else if (k == 3) {
                        if (b == 0) {
                            continue;
                        } else {
                            newList.add(a / b);
                        }
                    }
                    if (dfs(newList)) {
                        return true;
                    } else {
                        newList.remove(newList.size() - 1);
                    }
                }
            }
        }
        return false;
    }

    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<>();
        for (int i : nums) {
            list.add((double) i);
        }
        return dfs(list);
    }
}

1044. 最長重復(fù)子串

class Solution {
    long mod = (long)Math.pow(2, 37) - 1;
    long a = 26;
    int nums[];
    int n;
    public String longestDupSubstring(String S) {
        nums = new int [S.length()];
        for (int i = 0; i < S.length(); i ++) {
            nums[i] = S.charAt(i) - 'a';
        }
        this.n = S.length();
        int left = 1;
        int right = n;
        while (left != right) {
            int mid = left + (right - left) / 2;
            if (search(mid) != -1) left = mid + 1;
            else right = mid;
        }
        int begin = search(left - 1);
        if (begin != -1) return S.substring(begin, begin + left - 1);
        return "";
    }

    public int search(int length) {
        long cur = 0;
        for (int i = 0; i < length; i ++) {
            cur = (cur * a + nums[i]) % mod;
        }
        long aL = 1;
        for (int i = 0; i < length; i++) {
            aL = (aL * a ) % mod;
        }
        HashSet<Long> hs = new HashSet<>();
        hs.add(cur);

        for (int i = 1; i <= n - length; i ++) {
            cur = (cur * a - aL * nums[i - 1] % mod + mod) % mod;
            cur = (cur + nums[i + length - 1]) % mod;
            if (hs.contains(cur)) return i;
            hs.add(cur);
        }
        return -1;
    }
}

410. 分割數(shù)組的最大值

dp[i][j]代表數(shù)組的前i個數(shù)分成m個子數(shù)組献幔，和的最大值最小。
邊界：
dp[0][0] = 0
轉(zhuǎn)移方程：

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        int[] preSum = new int[n + 1];
        for (int i = 0; i < preSum.length - 1; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, m); j++) {
                for (int k = 0; k < i; k++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], preSum[i] - preSum[k]));
                }
            }
        }
        return dp[n][m];
    }
}

60. 排列序列

class Solution {
    boolean[] isVisited;
    StringBuilder temp = new StringBuilder();
    String res = null;
    int count = 0;

    private void dfs(int n, int k) {
        if (temp.length() == n) {
            count++;
            if (count == k) {
                res = temp.toString();
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisited[i] == false) {
                isVisited[i] = true;
                temp.append(i);
                dfs(n, k);
                if (res != null) {
                    return;
                }
                isVisited[i] = false;
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }

    public String getPermutation(int n, int k) {
        isVisited = new boolean[n + 1];
        dfs(n, k);
        return res;
    }
}

37. 解數(shù)獨

class Solution {
    private boolean dfs(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (check(i, j, c, board)) {
                            board[i][j] = c;
                            if (dfs(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean check(int row, int col, char c, char[][] board) {
        int blockRow = 3 * (row / 3);
        int blockCol = 3 * (col / 3);
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == c) {
                return false;
            }
            if (board[row][i] == c) {
                return false;
            }
            if (board[blockRow + i / 3][blockCol + i % 3] == c) {
                return false;
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board) {
        dfs(board);
    }
}

30. 串聯(lián)所有單詞的子串

暴力法趾诗，先計算所有子串的長度斜姥，然后不斷截取這個長度的字符串，判斷是否和words匹配沧竟。

class Solution {
    Map<String, Integer> map = new HashMap<>();

    private boolean judge(String s, String[] words) {
        Map<String, Integer> temp = new HashMap<>();
        int wordLen = words[0].length();
        for (int i = 0; i < words.length; i++) {
            String sub = s.substring(i * wordLen, i * wordLen + wordLen);
            temp.put(sub, temp.getOrDefault(sub, 0) + 1);
        }
        for (String key : temp.keySet()) {
            if (!temp.get(key).equals(map.get(key))) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if ("".equals(s)) {
            return res;
        }
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int len = words.length * words[0].length();
        for (int i = 0; i + len - 1 < s.length(); i++) {
            if (judge(s.substring(i, i + len), words)) {
                res.add(i);
            }
        }
        return res;
    }
}

132. 分割回文串 II

dp[i]代表以位置i結(jié)尾的字符串的最少分割次數(shù)。
邊界：
dp[i] = i
轉(zhuǎn)移方程：
遍歷字符串缚忧，如果以位置i為結(jié)尾的字符串就是回文串悟泵，直接令dp[i] = 0，然后繼續(xù)遍歷闪水。如果不是糕非，那么遍歷j從0到i-1，只要從j到i的子串是回文串，那么dp[i] = dp[j] +1朽肥，在遍歷j的過程中取dp[i]的最小值禁筏。

class Solution {
    private boolean isPar(String s) {
        int lo = 0, hi = s.length() - 1;
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) {
                return false;
            }
        }
        return true;
    }

    public int minCut(String s) {
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i] = i;
        }
        for (int i = 1; i < s.length(); i++) {
            if (isPar(s.substring(0, i + 1))) {
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (isPar(s.substring(j + 1, i + 1))) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[s.length() - 1];
    }
}

57. 插入?yún)^(qū)間

判斷兩個區(qū)間是否相交的方法：
左端點的最大值小于等于右端點的最小值，則相交衡招。
遍歷原有區(qū)間篱昔，只要與新插入?yún)^(qū)間相交，則更新插入的區(qū)間始腾，左端點更新為兩個區(qū)間左端點的較小值州刽，右端點更新為兩個區(qū)間右端點的較大值，不加到結(jié)果集浪箭。
如果不相交穗椅，則可以加到結(jié)果集中。
最后將新區(qū)間加到結(jié)果集中奶栖，然后按照左端點從小到大排序匹表。

class Solution {
    //判斷兩個區(qū)間是否相交
    private boolean check(int[] a, int[] b) {
        return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        for (int[] interval : intervals) {
            if (check(interval, newInterval)) {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            } else {
                res.add(interval);
            }
        }
        res.add(newInterval);
        Collections.sort(res, (o1, o2) -> o1[0] - o2[0]);
        return res.toArray(new int[res.size()][]);
    }
}

301. 刪除無效的括號

看到最少數(shù)量，優(yōu)先想到使用bfs求解宣鄙。
先判斷整個字符串是否合法袍镀， 如果合法的話就將其加入到結(jié)果中。否則的話框冀，進(jìn)行下一步流椒。
只刪掉 1 個括號，考慮所有的刪除情況明也，然后判斷剩下的字符串是否合法宣虾，如果合法的話就將其加入到結(jié)果中。否則的話温数，進(jìn)行下一步绣硝。
只刪掉 2 個括號，考慮所有的刪除情況撑刺，然后判斷剩下的字符串是否合法鹉胖，如果合法的話就將其加入到結(jié)果中。否則的話够傍，進(jìn)行下一步...
因為我們考慮刪除最少的括號數(shù)甫菠，如果上邊某一步出現(xiàn)了合法情況，后邊的步驟就不用進(jìn)行了冕屯。
要解決重復(fù)的問題寂诱，除了解法一在最后返回前用 set 去重。這里我們也可以在過程中使用一個 set 安聘，在加入隊列之前判斷一下是否重復(fù)痰洒。

class Solution {
    private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        Queue<String> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        q.offer(s);
        while (true) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String front = q.poll();
                if (isValid(front)) {
                    res.add(front);
                } else if (res.size() == 0) {
                    for (int j = 0; j < front.length(); j++) {
                        if (s.charAt(j) == '(' || s.charAt(j) == ')') {
                            String sub = front.substring(0, j) + front.substring(j + 1);
                            if (!set.contains(sub)) {
                                q.offer(sub);
                                set.add(sub);
                            }
                        }
                    }
                }
            }
            if (res.size() > 0) {
                break;
            }
        }
        return res;
    }
}

1153. 字符串轉(zhuǎn)化

當(dāng)str1 == str2時可以轉(zhuǎn)化
如果str2包含所有的26個字母瓢棒，則沒有了操作空間，因此不能轉(zhuǎn)化
如果str1某兩個下標(biāo)i, j對應(yīng)的字符相同丘喻，則必須要求str2中的相同下標(biāo)也必須相同
如果判斷以上情況后沒有問題脯宿，則可以轉(zhuǎn)化成功

class Solution {
    private boolean check(String s) {
        int count = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (!map.containsKey(c)) {
                count++;
                map.put(c, 1);
            }
        }
        return count < 26;
    }

    public boolean canConvert(String str1, String str2) {
        if (str1.equals(str2)) {
            return true;
        }
        if (!check(str2)) {
            return false;
        }
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < str1.length(); i++) {
            if (!map.containsKey(str1.charAt(i))) {
                map.put(str1.charAt(i), new ArrayList<>());
            }
            map.get(str1.charAt(i)).add(i);
        }
        for (List<Integer> list : map.values()) {
            char c = str2.charAt(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                if (c != str2.charAt(list.get(i))) {
                    return false;
                }
            }
        }
        return true;
    }
}

212. 單詞搜索 II

class Solution {
    int[] X = {0, 0, 1, -1}, Y = {1, -1, 0, 0};
    boolean[][] isVisit;

    private boolean helper(char[][] board, int i, int j, int num, String word) {
        if (num == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisit[i][j] == true) {
            return false;
        }
        if (board[i][j] == word.charAt(num)) {
            isVisit[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int newI = i + X[k], newJ = j + Y[k];
                if (helper(board, newI, newJ, num + 1, word) == true) {
                    return true;
                }
            }
            isVisit[i][j] = false;
            return false;
        } else {
            return false;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        isVisit = new boolean[board.length][board[0].length];
        Set<String> set = new HashSet<>();
        for (String word : words) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    for (int k = 0; k < board.length; k++) {
                        Arrays.fill(isVisit[k], false);
                    }
                    if (helper(board, i, j, 0, word)) {
                        set.add(word);
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }
}

1235. 規(guī)劃兼職工作