算法题学习_leetcode经典100题

递归

1. 爬楼梯 （70）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 
示例 1：
 
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
 
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
 
    public int climbStairs(int n) {
        // 终止条件
        if (n == 1) return 1;
        if (n == 2) return 2;
        // 过滤重复路径
        if (map.get(n) != null) {
            return map.get(n);
        } else {
            int result = climbStairs(n - 1) + climbStairs(n - 2);
            map.put(n, result);
            return result;
        }
    }
}

数组

2. 两数之和（1）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 
和为目标值 target 的那 两个 整数，并返回它们的数组下标。
 
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 
你可以按任意顺序返回答案。
 
示例 1：
 
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        // 利用hashmap，key:needNum, value:i
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int another = target - nums[i];
            // 不为空，则说明有匹配的数字对
            if (map.get(another) != null) {
                result[0] = map.get(another);
                result[1] = i;
                return result;
            } else {
                map.put(nums[i], i);
            }
        }
 
        return result;
    }
}

3. 合并两个有序数组（88）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，
分别表示 nums1 和 nums2 中的元素数目。
 
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 
示例 1：
 
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

思路：两个指针，一个作用在nums1当前位置，一个执行num2当前位置，依次比较

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int ni = 0;
        int nj = 0;
        int[] temp = new int[m + n];
        for (int i = 0; i < m + n; i++) {
            if (ni >= m) {
                temp[i] = nums2[nj++];
                continue;
            }
            if (nj >= n) {
                temp[i] = nums1[ni++];
                continue;
            }
            int numi = nums1[ni];
            int numj = nums2[nj];
            if (numi <= numj) {
                temp[i] = nums1[ni++];
            } else {
                temp[i] = nums2[nj++];
            }
        }
 
        for (int i = 0; i < m + n; i++) {
            nums1[i] = temp[i];
        }
    }
}

4. 移动零（283）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 
示例 1:
 
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

思路：一个指针用于遍历，另一个指针用户记录非0的个数，也是遍历指针需要移动数字的位置

class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
            }
        }
 
        for (int k = j; k < nums.length; k++) {
            nums[k] = 0;
        }
    }
}

5. 找到数组中消失的数字（448）

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
 
示例 1：
 
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

思路：由于数字是1-n，是与数组长度相匹配，所以将出现的数字，对应到数组位置的数字做特殊标记，最后循环一遍，没有特殊标记的就是消失的数字

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 特殊处理是将对应位置上的数字取负，绝对值处理是拿到原来的数
            int num = Math.abs(nums[i]);
            int nextNum = Math.abs(nums[num - 1]);
            // 将对应位置上的数字取负
            nums[num - 1] = -nextNum;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        return result;
    }
}

链表

6. 合并两个有序列表（21）

将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode result = new ListNode(0);
        ListNode p = result;
        while(list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if (list1 != null) {
            p.next = list1;
        }
        if (list2 != null) {
            p.next = list2;
        }
        return result.next;
    }
}

7. 删除链表中的重复数字（83）

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。
返回 已排序的链表 。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode node = head;
        while (node.next != null) {
            if (node.val == node.next.val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
 
        return head;
    }
}

8. 环形链表（141）

给你一个链表的头节点 head ，判断链表中是否有环。
 
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：快慢指针，环形追击，一定会出现相遇情况

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

9. 环形链表2（142）

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

思路：在上题的基础上，将慢指针移回到head，然后快慢指针每次同时每次移动一步，则相同点为入环点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        boolean flag = false;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                flag = true;
                break;
            }
        }
        if (flag) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        return null;
    }
}

10. 相交链表（160）

给你两个单链表的头节点 headA 和 headB ，
请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

思路：两个指针分别指向A、B，当A走完，则让A指向B，如果B走完，则让B指向A。相等时就是最早的一个交叉点，三段长度：headA到相交点 + 相交点到终点 + headB到相交点

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

11. 反转链表（206）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：两个指针，curNode与preNode，curNode指向preNode，同时要保证curNode和preNode，每次也往后移动

temp = curNode;

curNode = curNode.next;

temp.next = preNode;

preNode = temp;

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curNode = head;
        ListNode preNode = null;
        while (curNode != null) {
            ListNode temp = curNode;
            curNode = curNode.next;
            temp.next = preNode;
            preNode = temp;
        }
 
        return preNode;
    }
}

12. 回文列表（234）

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

思路：快慢指针，当快指针走完后，慢指针在中间的位置，这时候需要按奇偶调整下slow指针的初始位置，让快指针指向head，将slow指针反转，然后快慢指针每次同时移动一步，如果一直相等则返回true，否则返回false

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        fast = head;
        // 反转slow
        slow = reverse(slow);
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
 
    /**
     * 
     * 反转列表
     * @param slow
     * @return
     */
    private ListNode reverse(ListNode slow) {
        ListNode preNode = null;
        ListNode curNode = slow;
        while (curNode != null) {
            ListNode temp = curNode;
            curNode = curNode.next;
            temp.next = preNode;
            preNode = temp;
        }
        return preNode;
    }
}

13. 链表的中间节点（876）

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
 
如果有两个中间结点，则返回第二个中间结点。

思路：快慢指针，主要是看慢指针的边界条件

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

栈与队列

14. 用栈实现队列（232）

思路：用两个栈，一个作为输出栈，一个为输出栈。当push时，把输出栈全压入输入栈。反之，将输入栈全压入输出栈

import java.util.Stack;
 
//leetcode submit region begin(Prohibit modification and deletion)
class MyQueue {
 
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;
 
    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
 
    // 入栈，前需要将outStack重新放回inStack
    public void push(int x) {
        out2In();
        inStack.push(x);
    }
 
    public int pop() {
        in2Out();
        return outStack.pop();
    }
 
    public int peek() {
        in2Out();
        return outStack.peek();
    }
 
    public boolean empty() {
        if (inStack.empty() && outStack.empty()) {
            return true;
        }
        return false;
    }
 
    private void in2Out() {
        if (inStack.empty()) {
            return;
        }
        while (!inStack.empty()) {
            Integer in = inStack.pop();
            outStack.push(in);
        }
    }
 
    private void out2In() {
        if (outStack.empty()) {
            return;
        }
        while (!outStack.empty()) {
            Integer out = outStack.pop();
            inStack.push(out);
        }
    }
}

15. 字符串解码（394）

给定一个经过编码的字符串，返回它解码后的字符串。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

思路：利用栈，识别[和]做不用处理

树

16. 二叉树的中序遍历（94）

递归

思路：中序是左根右，核心思想：每一个根都会做这么一件事：看左面还有没有根，没有了我就是输出的根了，输出完再看我右面有没有根。所以呢，遇到有左的，就再往下看，没有了就可以add了，然后再往右边看

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
        buildRes(root, result);
 
        return result;
    }
 
    private void buildRes(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        buildRes(root.left, result);
        result.add(root.val);
        buildRes(root.right, result);
    }
}

非递归

思路：道理一样，只不过把递归栈，换成了自己实现栈

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
        buildRes(root, result);
 
        return result;
    }
 
    private void buildRes(TreeNode root, List<Integer> result) {
        // 借助栈，来存储节点，使节点可以按照要求的顺序输出
        Stack<TreeNode> stack = new Stack<TreeNode>();
        // 说明输出完了
        while (root != null || !stack.empty()) {
            // 压入当前节点，如果有左子树继续压，保证左子树先输出
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 按照 左 中 右的顺序
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
    }
}

17. 二叉树的前序遍历（144）

递归

思路：前序是左根右，核心思想：每一个根都会做这么一件事：我先输出，然后看我左面有没有，然后再看右边有没有

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
 
        this.buildRes(root, result);
        return result;
    }
 
    private void buildRes(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        buildRes(root.left, result);
        buildRes(root.right, result);
    }
}

非递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
 
        this.buildRes(root, result);
        return result;
    }
 
    private void buildRes(TreeNode root, List<Integer> result) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                // 先输出自己
                result.add(root.val);
                stack.push(root);
                // 再看指向自己的左侧
                root = root.left;
            }
            // 左侧没有了看右侧
            root = stack.pop();
            root = root.right;
        }
    }
}

18. 二叉树的后序遍历（145）

递归

思路：前序是左根右，核心思想：每一个根都会做这么一件事：我先看我左侧有没有，再看右侧有没有，如果都没有了我输出

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
 
        this.buildRes(root, result);
        return result;
    }
 
    private void buildRes(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        buildRes(root.left, result);
        buildRes(root.right, result);
        result.add(root.val);
    }
}

非递归

待学习

19.对称二叉树（101）

给你一个二叉树的根节点 root ， 检查它是否轴对称。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
 
        return check(root.left, root.right);
    }
 
    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

20.二叉树的最大深度（104）

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

21.平衡二叉树（110）

给定一个二叉树，判断它是否是 平衡二叉树

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

思路：利用递归回溯过程，从叶子结点开始，判定是否高度超过1，如果超过1，则不是平衡二叉树。直接返回false，如果不是逐层向上

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
 
        return doIsBalanced(root) != -1;
    }
 
    private Integer doIsBalanced(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 递归向下
        int left = doIsBalanced(root.left);
        int right = doIsBalanced(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
 
        return Math.max(left, right) + 1;
    }
}

22. 翻转二叉树（226）

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

思路：递归回溯交换left与right

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        invertTree(root.left);
        invertTree(root.right);
        // 进行翻转
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
 
        return root;
    }
}

23. 字符串搜索（String search）

24. 二分查找（704）

class Solution {
    public int search(int[] nums, int target) {
        return this.doSearch(nums, 0, nums.length - 1, target);
    }
    
    private int doSearch(int[] nums, int start, int end, int target) {
        int middle = (start + end) / 2;
        int middleNum = nums[middle];
        if (start <= end) {
            if (target < middleNum) {
                return doSearch(nums, start, middle - 1, target);
            } else if (target > middleNum) {
                return doSearch(nums, middle + 1, end, target);
            } else {
                return middle;
            }
        } else {
            return -1;
        }
    }
}

位运算

25. 只出现一次的数字（136）

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

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result = result ^ num;
        }
        return result;
    }
}

26. 比特位技计数（338）

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

思路：使用x&(x-1)每次可以消除一个最低位的1，所以nums[i] = nums[i&(i-1)] + 1

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            result[i] = result[i&(i-1)] + 1;
        }
        return result;
    }
}

27. 汉明距离（461）

思路：^异或可以将不同位变成1，相同位变成0；使用x&(x-1)每次可以消除一个最低位的1，最终消除到0停止

class Solution {
    public int hammingDistance(int x, int y) {
        int result = 0;
        for (int i = x ^ y; i != 0; i &= (i - 1)) {
            result++;
        }
        return result;
    }
}

28. 有效括号（20）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || c != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

29. 字符串相加（415）

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder stringBuilder = new StringBuilder();
        int carry = 0;
        for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--){
            int x = i < 0 ? 0 : num1.charAt(i) - '0';
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            int res = (x + y + carry) % 10;
            stringBuilder.append(res);
            carry = (x + y + carry) / 10;
        }
        return stringBuilder.reverse().toString();
    }
}

30. 字符串匹配BM算法

31. 两数之和（1）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

思路：使用map解决

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 使用hashmap
        Map<Integer, Integer> maps = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (maps.containsKey(target - nums[i])) {
                return new int[]{maps.get(target - nums[i]), i};
            }
            maps.put(nums[i], i);
        }
        return null;
    }
}

32. 两数相加（2）

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry == 1) {
            cur.next = new ListNode(1);
        }
 
        return pre.next;
    }
}

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

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

示例 1:

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

示例 2:

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

示例 3:

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

思路：前后指针，前指针从头移动，利用map存储出现过的字符，如果出现相同字符，将后指针移动到当前字符上，从而实现跳步

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        Map<Character, Integer> maps = new HashMap<>();
        char[] chars = s.toCharArray();
        int res = 0;
        // 后方指针
        int i = -1;
        // 前进指针
        for (int j = 0; j < chars.length; j++) {
            if (maps.containsKey(chars[j])) {
                i = Math.max(i, maps.get(chars[j]));
            }
            maps.put(chars[j], j);
            res = Math.max(res, j - i);
        }
        return res;
    }
}

34. 最长回文子串（5）

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

思路：动态规划题目，找到状态转移方程

i和j是头尾指针

子串串可以有 i+1,j-1转移来，如果一个串是回文串，那么i+1 j-1一定也是回文串

class Solution {
    public String longestPalindrome(String s) {
        if (s == null) {
            return null;
        }
        // 动态规划字符数组
        char[] chars = s.toCharArray();
        int len = chars.length;
        int resultLen = 1;
        int resultI = 0;
        // 动态规划结果集
        boolean[][] result = new boolean[len][len];
        // 初始化
        for (int i = 0; i < len; i++) {
            result[i][i] = true;
        }
        // 开始动态规划
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i] != chars[j]) {
                    result[i][j] = false;
                } else {
                    if (j - i < 2) {
                        result[i][j] = true;
                    } else {
                        result[i][j] = result[i + 1][j - 1];
                    }
                    if (result[i][j] && resultLen < j - i + 1) {
                        resultLen = j - i + 1;
                        resultI = i;
                    }
                }
            }
        }
 
        return s.substring(resultI, resultLen + resultI);
    }
}

35. 盛最多水的容器（11）

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：左右两个指针，哪边矮移动哪边

class Solution {
    public int maxArea(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int result = 0;
        // 谁小谁去动
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int temp = h * (right - left);
            if (result < temp) {
                result = temp;
            }
            // 进行移动
            if (height[left] > height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return result;
    }
}

36. 整数转罗马数字（12）

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

思路：枚举所有的基础数字与基础字母，减去目前可以减去最大的的基础的数

class Solution {
    public String intToRoman(int num) {
        StringBuilder stringBuilder = new StringBuilder();
        String[] rows = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        for (int i = 0; i < 13; i++) {
            while(num >= nums[i]) {
                num -= nums[i];
                stringBuilder.append(rows[i]);
            }
        }
        return stringBuilder.toString();
    }
}

37. 罗马数字转整数（13）

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

class Solution {
    public int romanToInt(String s) {
        // 可以根据规则找到规律，正常情况左侧一定比右侧大，但有特殊出现左比右小时，那么就是加上一个负数。例如IV=4  -1+5=4
        char[] chars = s.toCharArray();
        int sum = 0;
        int preNum = this.getNum(chars[0]);
        for (int i = 1; i < chars.length; i++) {
            int num = this.getNum(chars[i]);
            if (preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        // 最后以为肯定是正数，需要加上
        sum += preNum;
        return sum;
    }
 
    private int getNum(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
}

38. 最长公共前缀（14）

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        // 第一个传作为基础串
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            ans = ans.substring(0, j);
            if (ans.equals("")) {
                return ans;
            }
        }
        return ans;
    }
}

39. 三数之和（15）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。

请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路：先排序，使用三指针，k为基础指针，从头遍历，i/j为头与尾指针，看是否与k相加等于0

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 先排序
        // 然后使用三指针，k为基础指针，从头遍历，i/j为头与尾指针，看是否与k相加等于0。
        // 最后防止出现重复记录，当遇到重复数字时做相应的i++ j--
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int k = 0; k < nums.length - 2; k++) {
            // 说明相加只能为正数
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1;
            int j = nums.length - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    while (i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while (i < j && nums[j] == nums[--j]);
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while (i < j && nums[i] == nums[++i]);
                    while (i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}

40. 电话号码的字母组合（17）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

思路：暴力递归

class Solution {
    private String[] strMap = {
            " ",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
    };
 
    private List<String> result = new ArrayList<>();
 
    public List<String> letterCombinations(String digits) {
        // 递归解决
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        this.cal(digits, 0, "");
        return result;
    }
 
    private void cal(String digits, int index, String res) {
        if (index == digits.length()) {
            result.add(res);
            return;
        }
        char c = digits.charAt(index);
        String letter = strMap[c - '0'];
        for (int i = 0; i < letter.length(); i++) {
            this.cal(digits, index + 1, res + letter.charAt(i));
        }
    }
}

41. 删除链表倒数第几个结点（19）

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

思路：让前面的指针先移动 n 步，之后前后指针共同移动直到前面的指针到尾部为止。 slow.next = slow.next.next;

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode fast = pre;
        ListNode slow = pre;
        // 快指针先移动n次
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        if (n > 0) {
            return null;
        }
        // 开始快慢一起移动，指导fast到头，且要记录pre指针
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return pre.next;
    }
}

42. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

思路：递归，规律：当前串，左括号>=有括号，如果不满足则break

递归终止条件：1.右括号数量>左括号  2.左=右=n

递归条件： 1.左<n  2.左>右

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        back(n,result,0,0,"");
        return result;
    }
    private void back(int n,List<String> result,int left,int right,String str){
        if(right>left){
            return;
        }
        if(left==n&&right==n){
            result.add(str);
            return;
        }
        if(left<n){
            back(n,result,left+1,right,str+"(");
        }
        if(left>right){
            back(n,result,left,right+1,str+")");
        }
    }
}

43. 合并k个升序链表（23）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

思路：使用优先级队列（堆）。依次将多个队列的头结点放入队列中，取出小顶堆的堆顶，然后再放入后面的节点

class Solution {
    // 使用优先级队列（底层是堆）
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;
        Status(int val, ListNode ptr) {
            this.ptr = ptr;
            this.val = val;
        }
        public int compareTo(Status status) {
            return this.val - status.val;
        }
    }
    PriorityQueue<Status> queue = new PriorityQueue<>();
 
    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode listNode : lists) {
            if (listNode != null) {
                queue.offer(new Status(listNode.val, listNode));
            }
        }
 
        ListNode head = new ListNode(0);
        ListNode tail = head;
        // 获取最小值
        while (!queue.isEmpty()) {
            Status status = queue.poll();
            tail.next = status.ptr;
            tail = tail.next;
            if (status.ptr.next != null) {
                queue.offer(new Status(status.ptr.next.val, status.ptr.next));
            }
        }
        return head.next;
    }
}

44.下一个排列（31）

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

思路：找下一个排列，最低level是12345...升序，最高level是54321...降序，所以，找下一个排列，是找当前排列第一个不满足逆序的顺序，如果不满足就将它与后面比他大的数字交换，最后reverse

例如 1 2 3 （2不满足，3和2交换）  -> 1 3 2

但是如果是 5 3 4 2 1  交换后是 5 4 3 2 1 并不是后一个排序的数字，这个时候需要将i=2以及后面的数字进行翻转（为什么需要翻转，我们在第一遍找左小右大时，最后遍历过的没有停的都满足左大右小，所以翻转后，整体为左小右大）

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 从右往前，找到第一个正序的数
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // 找到后，再从右找到第一个大于他的数，并交换
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        // 最后进行reverse
        this.reverse(nums, i + 1);
    }
 
    private void swap(int nums[], int i , int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
 
    private void reverse(int[] nums, int start) {
        int left = start;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

45. 最长有效括号（32）

给你一个只有'（' 和'）' 的字符串，找出最长有效（格式正确且连续）括号子串的长度

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

class Solution {
    public int longestValidParentheses(String s) {
        int maxResult = 0;
        Stack<Integer> stack = new Stack<>();
        // 入栈一个-1用于计算，和防止为空
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    int len = i - stack.peek();
                    maxResult = maxResult < len ? len : maxResult;
                }
            }
        }
        return maxResult;
    }
}

46. 搜索旋转排序数组（33）

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

class Solution {
    public int search(int[] nums, int target) {
        int result = -1;
        if (nums.length == 0) {
            return result;
        }
        // 头指针，向右移动，且仅当右侧数大于自身时移动
        int start = 0;
        // 尾指针，向左移动，且仅当左侧数小于自身时移动
        int end = nums.length - 1;
        while (nums[start] < target && start + 1 < nums.length) {
            start++;
        }
        while (nums[end] > target && end - 1 > 0) {
            end--;
        }
        if (nums[start] == target) {
            result = start;
        }
        if (nums[end] == target) {
            result = end;
        }
        return result;
    }
}

47. 排序数组中查找第一个和最后一个位置（34）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 双指针
        int []result = new int[2];
        result[0] = -1;
        result[1] = -1;
        if (nums.length == 0) {
            return result;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start < nums.length - 1 && nums[start] < target) {
            start++;
        }
        while (end > 0 && nums[end] > target) {
            end--;
        }
        if (nums[start] == nums[end] && nums[start] == target) {
            result[0] = start;
            result[1] = end;
        }
        return result;
    }
}

48. 组合总和1（39 ）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

思路：递归遍历所有可能性，这里需要注意不可以重复，采用的剪枝策略是：先将数组排序，遍历左右可能性时，将当前遍历的数字i传入，只能往大的数遍历

class Solution {
 
    private List<List<Integer>> result = new ArrayList<>();
 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 递归
        if (candidates.length == 0) {
            return null;
        }
        Arrays.sort(candidates);
        this.doResult(candidates, target, 0, new ArrayList<Integer>(), 0);
        return result;
    }
 
    private void doResult(int[] candidates, int target, int tempSum, List<Integer> tempResult, int k) {
        if (tempSum > target) {
            return;
        }
        if (tempSum == target) {
            List<Integer> res = new ArrayList<>();
            res.addAll(tempResult);
            result.add(res);
            return;
        }
        for (int i = k; i < candidates.length; i++) {
            if (target - tempSum < candidates[i]) {
                break;
            }
            tempResult.add(candidates[i]);
            doResult(candidates, target, tempSum + candidates[i], tempResult, i);
            tempResult.remove(tempResult.size() - 1);
        }
    }
}

49. 组合总和2（40）

与上题一样，不过一个数只能用一次

思路：上一题加两个处理就可以 1.每次做累加时，要不算当前的数字，做i+1  2.当考虑当前数字是否加入时，要看这个数是否已经出现过

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
 
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 递归
        if (candidates.length == 0) {
            return null;
        }
        Arrays.sort(candidates);
        this.doResult(candidates, target, 0, new ArrayList<Integer>(), 0);
        return result;
    }
 
    private void doResult(int[] candidates, int target, int tempSum, List<Integer> tempResult, int k) {
        if (tempSum > target) {
            return;
        }
        if (tempSum == target) {
            List<Integer> res = new ArrayList<>();
            res.addAll(tempResult);
            result.add(res);
            return;
        }
        for (int i = k; i < candidates.length; i++) {
            if (i > k && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (target - tempSum < candidates[i]) {
                break;
            }
            tempResult.add(candidates[i]);
            doResult(candidates, target, tempSum + candidates[i], tempResult, i + 1);
            tempResult.remove(tempResult.size() - 1);
        }
    }
}

50. 接雨水（42）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        // 双指针算法，谁小谁动，等于时右动
        int leftMax = height[0];
        int rightMax = height[height.length - 1];
        int left = 0;
        int right = height.length - 1;
        int result = 0;
        while (right > left) {
            if (height[left] >= height[right]) {
                rightMax = rightMax < height[right] ? height[right] : rightMax;
                result += rightMax - height[right];
                right--;
            } else {
                leftMax = leftMax < height[left] ? height[left] : leftMax;
                result += leftMax - height[left];
                left++;
            }
        }
        return result;
    }
}

51. 跳跃游戏（45）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

思路：贪心算法，每次跳，在可选范围内选择最远的。有一个特殊边界，当最后一个节点恰好是边界时，就会被多算一次，所以不要看最后一个节点即可

class Solution {
    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, nums[i] + i);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

52. 全排序（46）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution {
 
    private List<List<Integer>> result = new ArrayList<>();
 
    public List<List<Integer>> permute(int[] nums) {
        // 递归，核心是添加标记数组
        int[] book = new int[nums.length];
        this.dfs(new ArrayList<>(), book, 0, nums);
        return result;
    }
 
    private void dfs(List<Integer> res, int[] book, int count, int[] nums) {
        if (count == nums.length) {
            result.add(new ArrayList<>(res));
        }
        for (int i = 0; i < nums.length; i++) {
            if (book[i] == 0) {
                book[i] = 1;
                res.add(nums[i]);
                dfs(res, book, count + 1, nums);
                book[i] = 0;
                res.remove(res.size() - 1);
            }
        }
    }
}

53. 矩阵转换（48）

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

class Solution {
    public void rotate(int[][] matrix) {
        // 先对角换，再中心换
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i + 1; j < matrix.length; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 再按中心交换
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][matrix.length - j - 1];
                matrix[i][matrix.length - j - 1] = temp;
            }
        }
    }
}

54. 字母异位词分组（49）

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

思路：使用hashmap，用拆词与重新组词的方式，将相同字母的不同次，组成相同key

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 使用hash，将词拆分，映射到数组中，再按照一个顺序重组key
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] temp = new int[26];
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                int num = c - 'a';
                temp[num]++;
            }
            StringBuilder strTemp = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                if (temp[j] != 0) {
                    strTemp.append('a' + j);
                    strTemp.append(temp[j]);
                }
            }
            String key = strTemp.toString();
            if (!map.containsKey(key)) {
                map.put(key ,new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

55. 最大子序和（53）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 

思路：使用加入该节点的前缀和 - 未加入时的最小前缀和 = 子串最大数特性计算

class Solution {
    public int maxSubArray(int[] nums) {
       // 加入当前节点 - 未加入当前节点的最小前缀和 = 最大子串和，找出最大数
        int preSum = 0;
        int minPreSum = 0;
        int result = Integer.MIN_VALUE;
        for (int num : nums) {
            preSum += num;
            result = Math.max(result, preSum - minPreSum);
            minPreSum = Math.min(minPreSum, preSum);
        }
        return result;
    }
}

56. 跳跃游戏（55）

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length && i <= max; i++) {
            max = Math.max(max, nums[i] + i);
            if (max >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

57. 区间合并（56）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路：先将数组排序，按照每行第一列小排序，然后对每一行做比较，当前行第一列数字要是大于上一行第二列数据，则需要新增一条数据

class Solution {
    public int[][] merge(int[][] intervals) {
        // 结果
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        int[][] res = new int[intervals.length][2];
        int resI = -1;
        for (int[] interval : intervals) {
            // 查看当前，如果当前数的start > 上一个数的end， 则新增一条数据。 否则合并
            if (resI == -1 || interval[0] > res[resI][1]) {
                res[++resI] = interval;
            } else {
                res[resI][1] = Math.max(res[resI][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, resI + 1);
    }
}

58.不同路径 dp（62）

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j] = dp[i-1][j] + dp[i][j-1];
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

59. 最小路径和（64）

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

class Solution {
    public int minPathSum(int[][] grid) {
        // dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        int[][] dp = new int[grid.length][grid[0].length];
        int temp = 0;
        for (int i = 0; i < grid.length; i++) {
            dp[i][0] = temp + grid[i][0];
            temp = dp[i][0];
        }
        temp = 0;
        for (int j = 0; j < grid[0].length; j++) {
            dp[0][j] = temp + grid[0][j];
            temp = dp[0][j];
        }
        // 开始dp
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

60. 编辑距离（72）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        // 初始化
        for (int i = 0; i < word1.length() + 1; i++) {
            dp[i][0] =i;
        }
        for (int j = 0; j < word2.length() + 1; j++) {
            dp[0][j] =j;
        }
        // 状态方程
        // word1变成word2
        // 新增：dp[i][j - 1] + 1
        // 删除：dp[i - 1][j] + 1
        // 更改：dp[i - 1][j - 1] + 1，看哪个小
        // 还有个条件，如果当前word[i - 1] == word[j - 1]
        // 那么还需要对比dp[i][j]和dp[i-1][j-1]哪个小
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

61. 颜色分类（75）

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

双指针方法

class Solution {
    public void sortColors(int[] nums) {
        // 双指针
        int start = 0;
        int end = nums.length - 1;
        // 遍历，找到0与start换，找到2与end换
        for (int i = 0; i < end; i++) {
            if (nums[i] == 0) {
                int temp = nums[start];
                nums[start] = nums[i];
                nums[i] = temp;
                start++;
            }
            if (nums[i] == 2) {
                int temp = nums[end];
                nums[end] = nums[i];
                nums[i] = temp;
                i--;
                end--;
            }
        }
    }
}

选择排序

    public void sortColors(int[] nums) {
        // 选择排序，每次选择一个最小值，与前面的值交换
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            int minValue = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < minValue) {
                    minIndex = j;
                    minValue = nums[j];
                }
            }
            int temp = nums[i];
            nums[i] = minValue;
            nums[minIndex] = temp;
        }
    }

冒泡排序

    public void sortColors(int[] nums) {
        // 冒泡排序，临近的交换
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

插入排序

    public void sortColors(int[] nums) {
        // 插入排序，当前数字找到之前的数字合适的位置插入
        for (int i = 1; i < nums.length; i++) {
            int k = i - 1;
            // 找合适的位置
            while (k >= 0 && nums[k] >= nums[i]) {
                k--;
            }
            int temp = nums[i];
            // 向后移动一位
            for (int j = i; j > k + 1; j--) {
                nums[j] = nums[j - 1];
            }
            nums[k + 1] = temp;
        }
    }

快速排序

 public void sortColors(int[] nums) {
        // 快速排序
        this.quickSort(nums, 0, nums.length - 1);
    }
 
    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = this.partition(nums, left, right);
        this.quickSort(nums, left, mid - 1);
        this.quickSort(nums, mid + 1, right);
    }
 
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int start = left;
        int end = right;
        while (true) {
            while (start < end && nums[end] >= pivot) {
                end--;
            }
            while (start < end && nums[start] <= pivot) {
                start++;
            }
            if (start >= end) {
                break;
            }
            // 交换
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
        }
        // 最后处理将pivot交换到合适到中间位置
        nums[left] = nums[start];
        nums[start] = pivot;
        return start;
    }

62. 最小覆盖串（76）滑动窗口难，只看了思路和代码

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

思路:
维护窗口使得len == n.当新加入窗口的字符存在于t中并且窗口里该字符的频率小于t中该字符的频率,则len++。窗口的左边界一定是t中的字符并且该字符的频率等于t中的频率找到len==n后,比较结果,再让左指针右移使len = n - 1,找新的窗口

class Solution {
    public String minWindow(String s, String t) {
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        int m = cs.length, n = ct.length;
        int l = 0, p = 0, q = 0, min = m + 1, len = 0;
        int[] mark = new int[128];
        int[] root = new int[128];
        for (char c : ct) {
            root[c]++;
        } 
        
        for (int i = 0; i < m; i++) {
            mark[cs[i]]++;
            if (root[cs[i]] >= mark[cs[i]]) {
                len++;
            }
            if (len == n) { //找左边界
                while (root[cs[l]] == 0 || mark[cs[l]] >  root[cs[l]]) {
                    mark[cs[l]]--;
                    l++;
                }
                if (i - l + 1 < min) {
                    p = l;
                    q = i;
                    min = i - l + 1;
                }
                while (len == n) { //左指针右移
                    if (mark[cs[l]] == root[cs[l]]) len--;
                    mark[cs[l]]--;
                    l++;
                }
            }
        }
        return min == m + 1 ? "" : s.substring(p, q + 1);
    }
}

63. 子集（78）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

class Solution {
 
    private List<List<Integer>> result = new ArrayList<>();
 
    public List<List<Integer>> subsets(int[] nums) {
        this.dfs(nums, 0, new ArrayList<>());
        return result;
    }
 
    private void dfs(int[] nums, int index, List<Integer> res) {
        result.add(new ArrayList<>(res));
        // 处理
        for (int i = index; i < nums.length; i++) {
            res.add(nums[i]);
            this.dfs(nums, i + 1, res);
            res.remove(res.size() -1);
        }
    }
}

64. 单词搜索（79）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

搜索过程如下：

• 1、在二维字符网格中枚举每个单词的起点。
• 2、从该起点出发向四周搜索单词word，并记录此时枚举到单词word的第u个位置 ( u从0开始)。
• 3、如果当前搜索的位置(x,y)的元素board[x][y] == word[u],则继续向四周搜索。
• 4、直到枚举到单词word的最后一个字母返回ture，否则返回false。

递归边界：

• 1、当搜索过程出现当前位置board[x][y] != word[u] ，说明当前路径不合法，返回false。
• 2、u == word.size() - 1,成功搜索到单词末尾，返回true。

实现细节：

• 1、从搜索过的位置继续搜索下一层时，需要对当前位置进行标识，表示已经搜索
• 2、可以使用偏移数组来简化代码。

class Solution {
    public boolean exist(char[][] board, String word) {
        // 深度优先搜索，遍历每一个当起始点，然后进行四个方向走
        // 这里要注意重复路径的问题，当前搜索，要做特殊的标记，代表已走过
        // 递归方法 dfs(board, word, u, i, j)
        // 四个坐标点。上（-1，0）下（1，0） 左（0，-1） 右（0，1）
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(board, word, 0, i,j)) {
                    return true;
                }
            }
        }
        return false;
    }
    int x[] = new int[]{-1, 1, 0 ,0};
    int y[] = new int[]{0, 0, -1, 1};
    private boolean dfs(char[][] board, String word, int index, int i, int j) {
        if (board[i][j] != word.charAt(index)) {
            return false;
        }
        if (index == word.length() - 1) {
            return true;
        }
        // 开始做dfs
        // 四个方向
        char temp = board[i][j];
        board[i][j] = '.';
        for (int k = 0; k < 4; k++) {
            int a = i + x[k];
            int b = j + y[k];
            // 不出范围，且该点没有走过
            if (a >= 0 && a <= board.length - 1 && b >=0 && b <= board[i].length - 1 && board[a][b] != '.') {
                if (dfs(board, word, index+1, a, b)) {
                    return true;
                }
            }
        }
        // 还原
        board[i][j] = temp;
        // 最终走完长度不够
        return false;
    }
}

65. 柱状图中最大的矩形（84）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 单调栈
        // 核心是找到比栈顶节点小的点
        // 这样的让栈顶依次出站，知道找到比当前节点小的，停止
        // (用 i - peek - 1) * 最后一个出栈的
        // 最后将当前节点进展，作为新的边界
        // 最后处理剩余内容，
        Stack<Integer> stack = new Stack<>();
        // 作为垫底计算边界
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                int hight = heights[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                maxArea = Math.max(maxArea, hight * (i - left - 1));
            }
            stack.push(i);
        }
        // 处理剩余的
        while (!stack.isEmpty()) {
            int hight = heights[stack.pop()];
            int left = stack.empty() ? -1 : stack.peek();
            maxArea = Math.max(maxArea, hight * (heights.length - left- 1));
        }
        return maxArea;
    }

66. 最大矩形（85）

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

思路：仍然看做单调栈问题，跟上一题相比变成了多次计算问题

class Solution {
 
    private int result = 0;
 
    public int maximalRectangle(char[][] matrix) {
        // 上一题的升级版
        // 二维转一维，每一位分别带入到单调栈算法中计算
        // 高度数组
        int[] hights = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '0') {
                    hights[j] = 0;
                } else {
                    hights[j]++;
                }
            }
            this.cal(hights);
        }
        return result;
    }
 
    private void cal(int[] hights) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < hights.length; i++) {
            while (!stack.isEmpty() && hights[i] < hights[stack.peek()]) {
                int hight = hights[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                result = result < hight * (i - left - 1) ? hight * (i - left - 1) : result;
            }
            stack.push(i);
        }
        // 处理剩余的
        while (!stack.isEmpty()) {
            int hight = hights[stack.pop()];
            int left = stack.isEmpty() ? -1 : stack.peek();
            result = result < hight * (hights.length - left - 1) ? hight * (hights.length - left - 1) : result;
        }
    }
}

67. 二叉树的中序遍历（94）

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
//        this.dfs(root, result);
//        return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            result.add(node.val);
            node = node.right;
        }
        return result;
    }
 
//    private void dfs(TreeNode node, List<Integer> result) {
//        if (node == null) {
//            return;
//        }
//        dfs(node.left, result);
//        result.add(node.val);
//        dfs(node.right, result);
//    }
}

68. 不同的二叉搜索树（96）

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

class Solution {
 
    Map<Integer, Integer> map = new HashMap<>();
    public int numTrees(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int leftNum = numTrees(i - 1);
            int rightNum = numTrees(n - i);
            count += leftNum * rightNum;
        }
        map.put(n, count);
        return count;
    }
}

69. 对称二叉树（101）

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root.left, root.right);
    }
 
    private boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }
}

70.二叉数的层序遍历（102）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

思路：bfs需要借助数据结构，最优是队列

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        // bfs需要借助其他数据结构，队列，数组，栈（数组和栈需要两个，因为要保证顺序）
        Queue<TreeNode> queue = new ArrayDeque();
        List<List<Integer>> result = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                size--;
            }
            result.add(list);
        }
        return result;
    }
}

71. 二叉树的最大深度（104）

class Solution {
 
    public int maxDepth(TreeNode root) {
        // dfs
        return this.dfs(root);
    }
 
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(dfs(root.left), dfs(root.right)) + 1;
    }
}

72. 从前序与中序遍历序列，构建二叉树（105）

思路：切割数组，切割出左右子树。

当前根是前序的第一个数字

在中序序列中找出相等值的坐标

左子树的两个数组是

preTree (1,i)

inTree (0,i-1)

右子树的两个数组是

preTree (i+1,prelength-1)

inTree (i+1,inlength-1)

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 递归
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        TreeNode newNode = new TreeNode(preorder[0]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                newNode.left = buildTree(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
                newNode.right = buildTree(Arrays.copyOfRange(preorder, i + 1, preorder.length), Arrays.copyOfRange(inorder, i + 1, inorder.length));
            }
        }
        return newNode;
    }
}

73. 买卖股票最佳时间（121）

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

class Solution {
    public int maxProfit(int[] prices) {
        // 贪心法
        int max = 0;
        int cur = prices[0];
        for (int p : prices) {
            if (p < cur) {
                cur = p;
                continue;
            }
            if (p > cur) {
                max = Math.max(max, p - cur);
            }
        }
        return max;
    }
}

74. 二叉树中的最大路径和（124）

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

class Solution {
 
    private int sum = Integer.MIN_VALUE;
 
    public int maxPathSum(TreeNode root) {
        // 从根节点看，我有四种情况去看最大和
        // 1.独立自己 2.我+左子树  3.我+右子树 4.我+左+右
        // 递归解决
        this.dfs(root);
        return sum;
    }
 
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        int res = Math.max(root.val, Math.max(root.val + left, root.val + right));
        sum = Math.max(sum, Math.max(res, root.val + left + right));
        return res;
    }
}

75. 最长连续序列（128）

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int maxLength = 0;
        // 需要去找当前数 n-1是否存在，如果存在则说明该数字不是开始的数
        for (int i = 0; i < nums.length; i++) {
            int tempLength = 1;
            if (!set.contains(nums[i] - 1)) {
                int temp = nums[i];
                while (set.contains(temp + 1)) {
                    tempLength++;
                    temp++;
                }
            }
            maxLength = Math.max(maxLength, tempLength);
        }
 
        return maxLength;
    }
}

76.只出现一次的数字（136）

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

77. 单词拆分（139）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i >= wordLength && s.substring(i - wordLength, i).equals(word)) {
                    dp[i] = dp[i] || dp[i - wordLength];
                }
            }
        }
        return dp[len];
    }
}

78. 单词拆分|| （140）

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]

思路：上一题的升级，需要注意的是上一题有一些区别，因为需要打印所有的路径，所有要把所有的记录都存下来

上一题中，两层遍历是，第一层当前背包是i，第二层每件物品，且物品可以无限使用，所以是背包问题，且是完全背包

本题需要记录下所有路径，所以两层循环变成，第一层开始位置，第二层为结束位置，所以dp[i][j]=true代表该i到j是有单词的，所以直接再向下递归就行

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        // 动态规划+递归暴搜
        boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
        // 把wordList转为set
        Set<String> set = new HashSet<>();
        for (String word : wordDict) {
            set.add(word);
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i; j <= s.length(); j++) {
                String tmpStr = s.substring(i - 1, j);
                if (set.contains(tmpStr)) {
                    dp[i][j] = true;
                }
            }
        }
        this.dfs(dp, 0, new StringBuilder(), s.length(), s);
        return result;
    }
 
    private void dfs(boolean[][] dp, int index, StringBuilder sb, int length, String s) {
        if (index == length) {
            result.add(sb.toString());
        }
        for (int i = index; i < length; i++) {
            // 如果为true，说明从index到i是有字符串的，开始找
            if (dp[index + 1][i + 1]) {
                String str = s.substring(index, i + 1);
                if (sb.length() == 0) {
                    sb.append(str);
                    // 向下递归
                    dfs(dp, i + 1, sb, length, s);
                    // 回溯还原
                    sb = new StringBuilder();
                } else {
                    sb.append(" ").append(str);
                    dfs(dp, i + 1, sb, length, s);
                    sb.delete(sb.length() - str.length() - 1, sb.length());
                }
            }
        }
    }
}

79. 环形链表（141、142）

思路：快慢指针，快慢指针相交，就证明有环。有环后，将慢指针退回head，快慢一起每次移动一步，交点为环相交点

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean isTrue = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                isTrue = true;
                break;
            }
        }
        if (!isTrue) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

80. 乘积最大子数组（152）

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

class Solution {
    public int maxProduct(int[] nums) {
        // 动态规划
        // 记录三个值  imax imin max  imax和imin是指，当第i个节点加入后最大和最小值
        int max = Integer.MIN_VALUE;
        int imax = 1;
        int imin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);
            max = Math.max(imax, max);
        }
        return max;
    }
}

81. 最小栈（155）

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

class MinStack {
    // 使用java自带的栈，实现min栈
    // 两个栈，一个正常存储数据，另一个存遇到的小的数
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
 
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            if (minStack.peek() >= val) {
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        int top = stack.pop();
        if (top == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

82. 相交链表（160）

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

83. 多数元素（169）

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

class Solution {
    public int majorityElement(int[] nums) {
        // 由于题目设定一定有存在多数元素，用摩尔选举法
        // 抵消法
        int result = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                result = nums[i];
            }
            count += nums[i] == result ? 1 : -1;
        }
        return result;
    }
}

84. 打家劫舍（198）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

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

class Solution {
    public int rob(int[] nums) {
        // 动态规划，转移方程 dp[i] = Math.max(dp[i - 1], dp[i - 2] + num);
        // dp[0] = nums[0], dp[1] = Math.max(nums[0], nums[1]);
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2]);
    }
}

85. 岛屿数量（200）

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

class Solution {
    public int numIslands(char[][] grid) {
        // 标记，递归
        // 是陆地为1，海水为0，已经探寻过的记为v，看每一个点，是否为1，如果为1就进行递归探查
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
 
    private void dfs(char[][] grid, int i, int j) {
        grid[i][j] = 'v';
        // 四个方向探测
        // 上
        if (i - 1 >= 0 && grid[i - 1][j] == '1') {
            dfs(grid, i - 1, j);
        }
        // 下
        if (i + 1 <= grid.length - 1 && grid[i + 1][j] == '1') {
            dfs(grid, i + 1, j);
        }
        // 左
        if (j - 1 >= 0 && grid[i][j - 1] == '1') {
            dfs(grid, i, j - 1);
        }
        if (j + 1 <= grid[0].length - 1 && grid[i][j + 1] == '1') {
            dfs(grid, i, j + 1);
        }
    }
}

86. 反转链表（206）

class Solution {
    public ListNode reverseList(ListNode head) {
        // 关键点是要存储pre,遍历是要先记录下cur.next
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

87. 课程表（207）

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 问题转换，判断给定路径是否有环
        // 使用广度优先遍历消除入度，如果总入度不为0，说明有环
        // 存放每一个节点的入度
        int[] deg = new int[numCourses];
        // 存放每一个节点的路径
        List<List<Integer>> path = new ArrayList<>();
        int total = 0;
        // 初始化路径
        for (int i = 0; i < numCourses; i++) {
            path.add(new ArrayList<>());
        }
        // 设置度数组和路径
        for (int[] pa : prerequisites) {
            int ideg = pa[0];
            int ipath = pa[1];
            deg[ideg]++;
            total++;
            path.get(ipath).add(ideg);
        }
        // 进行广度优先搜索
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        // 先将入度为0为节点放入queue，为初始节点
        for (int i = 0; i < numCourses; i++) {
            if (deg[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            for (int a : path.get(queue.pop())) {
                deg[a]--;
                total--;
                // 当前节点入度为0，则可以作为初始节点
                if (deg[a] == 0) {
                    queue.offer(a);
                }
            }
        }
        return total == 0;
    }
}

88. 实现前缀树（208）

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

// 字典树
class TrieNode {
    // 是否为单词
    boolean isWord;
    // 子树，26个字母
    TrieNode[] children;
 
    public TrieNode() {
        isWord = true;
        children = new TrieNode[26];
    }
}
 
class Trie {
    // 根
    private TrieNode root;
 
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode current = root;
        // 遍历每一个字母
        for (int i = 0; i < word.length(); i++) {
            // 26个顺序
            int num = word.charAt(i) - 'a';
            if (current.children[num] == null) {
                TrieNode childen = new TrieNode();
                childen.isWord = false;
                current.children[num] = childen;
            }
            current = current.children[num];
        }
        current.isWord = true;
    }
    
    public boolean search(String word) {
        TrieNode trieNode = this.find(word);
        if (trieNode == null) {
            return false;
        }
        return trieNode.isWord;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode trieNode = this.find(prefix);
        if (trieNode == null) {
            return false;
        }
        return true;
    }
 
    private TrieNode find(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            int num = word.charAt(i) - 'a';
            if (current.children[num] == null) {
                return null;
            }
            current = current.children[num];
        }
        return current;
    }
}

89. 数组中第k个最大元素（215）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 大顶对，初始构建堆
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            buildMaxHeap(nums, i, nums.length);
        }
        // 进行头尾交换，交换次数由k决定
        for (int j = 0; j < k - 1; j++) {
            int temp = nums[0];
            nums[0] = nums[nums.length - j - 1];
            nums[nums.length - j - 1] = temp;
            buildMaxHeap(nums, 0, nums.length - j - 1);
        }
        return nums[0];
    }
 
    private void buildMaxHeap(int[] nums, int index, int headLength) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int mid = index;
        if (left < headLength && nums[left] > nums[mid]) {
            mid = left;
        }
        if (right < headLength && nums[right] > nums[mid]) {
            mid = right;
        }
        // 说明有交换
        if (mid != index) {
            // 进行交换
            int temp = nums[mid];
            nums[mid] = nums[index];
            nums[index] = temp;
            // 主要是有重建阶段，需要继续向下构建，如果是init阶段实际不用
            buildMaxHeap(nums, mid, headLength);
        }
    }
}

90. 最大正方形（221）

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

class Solution {
    public int maximalSquare(char[][] matrix) {
        // 动态规划，我们关注正方形的右下角，dp数组记录该点作为右下角时，边长度
        // 边的长度取决于  左、上、左上角
        // dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
        int[][] dp = new int[matrix.length][matrix[0].length];
        // 初始化
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = 1;
                    max = 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (dp[i][j] == 1) {
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1])) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }
}

91. 翻转二叉树（226）

class Solution {
    public TreeNode invertTree(TreeNode root) {
        TreeNode node = root;
        this.reverse(node);
        return root;
    }
 
    private void reverse(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            return;
        }
        if (node.left != null) {
            reverse(node.left);
        }
        if (node.right != null) {
            reverse(node.right);
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

92. 回文链表（234）

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 快慢指针,链表翻转
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 需要处理奇偶
        if (fast != null) {
            slow = slow.next;
        }
        // 处理翻转
        slow = this.reverse(slow);
        fast = head;
        while (fast != null && slow != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
 
    private ListNode reverse(ListNode node) {
        ListNode pre = null;
        ListNode cur = node;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

93. 二叉树的最近公共祖先（236）

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

class Solution {
 
    private TreeNode result = null;
 
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 回溯阶段处理
        // 公共节点有两种情况
        // 1.左子树和右子树分别包含两个节点 2.其中一个节点是另一个节点的父亲或祖宗
        // (rightRe && leftRe || ((root.val == p.val || root.val == q.val) && (rightRe || leftRe)))
        // 所以判断是否是公共节点，需要两个判断
        dfs(root, p, q);
        return result;
 
    }
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        boolean leftRe = dfs(root.left, p, q);
        boolean rightRe = dfs(root.right, p, q);
        // 回溯
        if (rightRe && leftRe || ((root.val == p.val || root.val == q.val) && (rightRe || leftRe))){
            result = root;
        }
        return rightRe || leftRe || root.val == p.val || root.val == q.val;
    }
}

94. 除自身以外的数组乘积（238）

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 前缀积和后缀积
        int[] front = new int[nums.length];
        int[] back = new int[nums.length];
        // 前缀乘积
        int sum = 1;
        front[0] = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            sum *= nums[i];
            front[i + 1] = sum;
        }
        sum = 1;
        back[nums.length - 1] = 1;
        for (int j = nums.length - 1; j >= 1; j--) {
            sum *= nums[j];
            back[j - 1] = sum;
        }
        for (int i = 0; i < nums.length; i++) {
            front[i] = front[i] * back[i];
        }
        return front;
    }
}

95. 滑动窗口最大值（239难）

难，暂空

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

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

96. 搜索二维矩阵（240）

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

思路：二维查找，不多在原来基础上加了一层循环

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 以行为维度的二分搜索
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            int l = 0;
            int r = n - 1;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (matrix[i][mid] <= target) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            if (target == matrix[i][l]) {
                return true;
            }
        }
        return false;
    }
}

97. 完全平方数（279）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

思路：转成完全背包问题

class Solution {
    public int numSquares(int n) {
        // 完全背包问题
        // n为背包容量
        // 需要确认有几件物品, 且创建背包list
        List<Integer> wupin = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i * i <= n) {
                wupin.add(i * i);
            } else {
                break;
            }
        }
        // 转移方程  f[i] = Math.min(f[i], f[i-wupin[j] + 1]);
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < wupin.size(); j++) {
                if (i >= wupin.get(j)) {
                    dp[i] = Math.min(dp[i], dp[i - wupin.get(j)] + 1);
                }
            }
        }
        return dp[n];
    }
}

98. 移动0（283）

class Solution {
    public void moveZeroes(int[] nums) {
        // 双指针
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[start];
                nums[start++] = temp;
            }
        }
    }
}

99. 二叉树的序列化与反序列化（297难）

100.删除无效括号（301难）

101.最佳买卖股票时机，含冷冻期（309）

列举股票问题（动态规划）

• 121. 买卖股票的最佳时机

买卖一次

贪心法

class Solution {
    public int maxProfit(int[] prices) {
        // 贪心法
        int max = 0;
        int cur = prices[0];
        for (int p : prices) {
            if (p < cur) {
                cur = p;
                continue;
            }
            if (p > cur) {
                max = Math.max(max, p - cur);
            }
        }
        return max;
    }
}

• 122. 买卖股票的最佳时机 II

买卖次数不限

思路：需要记录当前第i天，是否持有状态

dp[i][n] : dp[0~n-1][0~1]   

dp[i][0] 代表第i天不持有当前最大利润，dp[i][1] 代表第i天持有当前最大利润

初始态 

dp[0][0] = 0,dp[0][1] = -prices[0]

转移方程

// 今日不持有 = 昨天也不持有，昨天持有今日卖了

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);

// 今日持有 = 昨天也不持有今日持有，昨日持有

dp[i][1] = Math.max(dp[i-1][0] - prices[i], dp[i-1][1]);

结束

dp[n-1][0]

简化

dp0 = Math.max(dp0, dp1 + prices[i]);

dp1 = Math.max(dp0-prices[i], dp1);

代码

class Solution {
    public int maxProfit(int[] prices) {
        int dp0 = 0;
        int dp1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp0 = Math.max(dp0, dp1 + prices[i]);
            dp1 = Math.max(dp0 - prices[i], dp1);
        }
        return dp0;
    }
}

• 123. 买卖股票的最佳时机 III

买卖两次

思路：需要记录当前第i天，是否持有状态，还有卖出次数

dp[i][m][n] : dp[i][0~2][0~1]  m卖出次数  n是否持有

初始状态

dp[i][0][0] = 0

dp[i][0][1] = -prices[0]

dp[i][1][1] = Integer.MIN_VALUE

转移方程

dp[i][0][0] = 0;

dp[i][0][1] = Math.max(dp[i-1][0][0]-prices[i], dp[i-1][0][1]);

dp[i][1][0] = Math.max(dp[i-1][0][1]+prices[i], dp[i-1][1][0]);

dp[i][1][1] = Math.max(dp[i-1][1][0]-prices[i], dp[i-1][1][1]);

dp[i][2][0] = Math.max(dp[i-1][1][1]+prices[i], dp[i-1][2][0]);

终态

dp[n-1][2][0]

降维简化

            dp[0][1] = Math.max(dp[0][0]-prices[i], dp[0][1]);
            dp[1][0] = Math.max(dp[0][1]+prices[i], dp[1][0]);
            dp[1][1] = Math.max(dp[1][0]-prices[i], dp[1][1]);
            dp[2][0] = Math.max(dp[1][1]+prices[i], dp[2][0]);

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

• 188. 买卖股票的最佳时机 IV

买卖k次

当前第i天，买卖m次，是否持有

dp[i][m][n] ：dp[0-prices.length-1][0-k][0-1]

初始态

dp[i][0][0] = 0;

dp[i][0][1] = -prices[0];

dp[i][m][0] = dp[i][m][1] = Integer.MIN_VALUE;  m>=1,因为第一天不可能m>=1，所以置为负无穷

转移方程

dp[i][m][0] = Math.max(dp[i-1][m][0], dp[i-1][m-1][1]+prices[i])

dp[i][m][1] = Math.max(dp[i-1][m][0] - prices[i], dp[i-1][m][1]);

终态

dp[n-1][k][0]

代码

class Solution {
    public int maxProfit(int k, int[] prices) {
        int[][] dp = new int[k + 1][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i <= k; i++) {
            dp[i][0] = dp[i][1] = Integer.MIN_VALUE;
        }
        for (int i = 0; i < prices.length; i++) {
            for (int m = 0; m <= k; m++) {
                dp[m][0] = Math.max(dp[m][0], m == 0 ? Integer.MIN_VALUE : dp[m - 1][1] + prices[i]);
                dp[m][1] = Math.max(dp[m][0] - prices[i], dp[m][1]);
            }
        }
        return dp[k][0];
    }
}

• 309. 最佳买卖股票时机含冷冻期

不限买卖次数，含冷冻期一天

转移方程

// 0 持有股票 1.不持有股票且在冷冻期 2.不持有股票且不在冷冻期

dp[i][n] :dp[0-prices.length-1][0-2]

dp[i][0] = Math.max(dp[i-1][2]-prices[i], dp[i-1][0])

dp[i][1] = dp[i-1][0] + prices[i];

dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);

初始态

dp[0][0] = -prices[0];

dp[0][1] = Integer.MIN.VALUE

dp[0][2] = 0;

终态

Math.max(dp[n-1][1], dp[n-1][2]);

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

• 714. 买卖股票的最佳时机含手续费

不限买卖次数，含手续费

同理不限次数

// 今日不持有 = 昨天也不持有，昨天持有今日卖了

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - k);

// 今日持有 = 昨天也不持有今日持有，昨日持有

dp[i][1] = Math.max(dp[i-1][0] - prices[i], dp[i-1][1]);

代码

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

102.戳气球（312）区间dp

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i -
1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

class Solution {
    public int maxCoins(int[] nums) {
        // 区间dp，要思考：i -> j 代表从i到j，i、j之间可以拆成两个区间做动态规划
        // 题中，如果超过数组范围则为1，所以将nums左右各延展一个1个，等价于超出范围取1
        // 转移方程, 我们看最后选择的一个点point[k] * point[i](左区间) * point[j]（右区间）
        // 最后的结果是 point[k] * point[i](左区间) * point[j]（右区间）+ dp[i][k](左区间继续取值) + dp[k][j](左区间继续取值)
        // 最后的结果是dp[0][n-1] 从开始到最后一个节点
        int n = nums.length;
        int[] point = new int[n + 2];
        point[0] = 1;
        point[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            point[i] = nums[i - 1];
        }
        // 创建dp数组
        int[][] dp = new int[n+2][n+2];
        for (int i = n; i >= 0; i--) {
            for (int j = i + 1; j < n + 2; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i][k] + dp[k][j] + point[i] * point[j] * point[k]);
                }
            }
        }
        return dp[0][n + 1];
    }
}

103.零钱兑换（322）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[],表示当前背包容量为i，为i时最少数
        // 转移方程 dp[i] = min(dp[i], dp[i-coin) + 1)
        // dp[i] == 0  dp[i] = dp[i-coin] + 1
        int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }
        for (int coin : coins) {
            for (int i = 1; i <= amount; i++) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

104.打家劫舍III（337）

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

方案一（递归+剪枝）

    private Map<TreeNode, Integer> map = new HashMap<>();
 
    public int rob(TreeNode root) {
        // 方案1， 爷爷选了，儿子不能选，可以选孙子。 爷爷不选，那么儿子能选，孙子不能选
        // 方案1  正常递归是超时的，所以要加剪枝
        if (root == null) {
            return 0;
        }
        if (map.get(root) != null) {
            return map.get(root);
        }
        int money = root.val;
        if (root.left != null) {
            money += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            money += rob(root.right.left) + rob(root.right.right);
        }
        Integer temp = Math.max(money, rob(root.right) + rob(root.left));
        map.put(root, temp);
        return temp;
    }

方案二：动态规划

    public int rob(TreeNode root) {
        // 方案2, 动态规划
        // 对于每一个节点，都有两种选择，选这个节点和不选择这个节点
        // int[] dp = new int[2]; [0]是不选择  [1]是选择
        // 不选择时 = 左节点偷时最大钱数+右节点偷时最大钱数
        // 选择时 = 左节点不偷时最大钱数 + 右节点不偷时最大钱数 + 当前节点的钱数
        int[] result = this.cal(root);
        return Math.max(result[0], result[1]);
    }
 
    public int[] cal(TreeNode root) {
        if (root == null) {
            return new int[2];
        }
        int[] result = new int[2];
        int[] left = cal(root.left);
        int[] right = cal(root.right);
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = root.val + left[0] + right[0];
        return result;
    }