LeetCode-Learn

Easy

01TwoSum

• 方法一：
  • 暴力求解
• 方法二：
  • 哈希表
  • 因为暴力解法的时间复杂度是 O(N^2)，所以要追求时间复杂度小一点，而哈希表找的时间复杂度是 O(1)
  • 把nums的值作为hashmap的key
• “最佳”答案：

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (hashMap.containsKey(target - nums[i])){
            return new int[]{hashMap.get(target - nums[i]), i};
        }
        hashMap.put(nums[i], i);
    }
    return new int[0];
}

07ReverseInteger

• 方法：
  • 取余取整
• 要考虑的是溢出的问题
• 以下取自 LeetCode评论区
• 
• 

public int reverse(int x) {

    int last, num = 0;

    while (x != 0){
        last = x % 10;

        if (num > Integer.MAX_VALUE / 10 || (num == Integer.MAX_VALUE / 10) && last > 7)
            return 0;
        if (num < Integer.MIN_VALUE / 10 || (num == Integer.MIN_VALUE / 10) && last < -8)
            return 0;

        num *= 10;


        num += last;

        x /= 10;
    }

    return num;
}

09PalindromeNumber

• 方法1
  • 转数组，从头遍历和从后遍历，判断
• 方法2
  • 直接数学取余取整，判断
• 方法3
  • 把数后半部分反转，和前半部分比较

public boolean isPalindrome(int x) {
    //方法1
    /*if (x < 0)
            return false;
        String s = String.valueOf(x);
        int length = s.length();
        int middle = length / 2;


        char[] chars = s.toCharArray();
        //System.out.println(s);


        for (int a = 0, b = length - 1; a < middle && b >= middle; a++, b--){
            if (chars[a] != chars[b]){
                return false;
            }
        }

        return true;*/

    //方法2
    if (x < 0) return false;
    // 除数
    int div = 1;
    while (x / div >= 10){
        div *= 10;
    }
    while (x > 0){
        // 拿到高位低位
        int high = x / div;
        int low = x % 10;
        if (high != low) return false;
        // 截掉高位低位
        x = (x % div) / 10;
        div /= 100;
    }
    return true;


    //方法3
    /*if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;*/
}

13RomanToInteger

要理解题意，并不是两两结合来算，而是直接看前一个是不是比后一个小，小就减，大就加

这里数据量太少，用 hashMap 体现不出，直接用 switch-case

public int romanToInt(String s) {
    //I             1
    //V             5
    //X             10
    //L             50
    //C             100
    //D             500
    //M             1000
    HashMap<Character, Integer> hashMap = new HashMap<>();
    hashMap.put('I', 1);
    hashMap.put('V', 5);
    hashMap.put('X', 10);
    hashMap.put('L', 50);
    hashMap.put('C', 100);
    hashMap.put('D', 500);
    hashMap.put('M', 1000);

    int sum = 0;
    int pre = hashMap.get(s.charAt(0));
    for (int i = 1; i < s.length(); i++) {
        if (pre < hashMap.get(s.charAt(i))){
            sum -= pre;
        }else {
            sum += pre;
        }
        pre = hashMap.get(s.charAt(i));
    }
    sum += pre;
    return sum;
}

14LongestCommonPrefix

做的时候想的是：设置一个n，代表最后的相同字符的index，然后从0开始，循环数组，每次取每个字符串第n个字符，看相不相等。

public String longestCommonPrefix(String[] strs) {
    String res = "";
    if (strs == null || strs.length == 0){
        return res;
    }
    if (strs.length == 1){
        return strs[0];
    }
    // 代表最后的相同字符的index
    int n = 0;
    while (true){
        int i;
        for (i = 1; i < strs.length; i++) {
            if (strs[i - 1].isEmpty() || strs[i].isEmpty()){
                return res;
            }
            if (strs[i - 1].length() > n && strs[i].length() > n){
                if (strs[i - 1].charAt(n) != strs[i].charAt(n))
                    break;
            }else {
                break;
            }
        }
        if (i == strs.length){
            n++;
        }else {
            break;
        }
    }
    res += strs[0].substring(0, n);
    return res;
}

答案是用分治，分左半部分和右半部分：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    } else {
        return longestCommonPrefix(strs, 0, strs.length - 1);
    }
}

public String longestCommonPrefix(String[] strs, int start, int end) {
    if (start == end) {
        return strs[start];
    } else {
        // 分治开始
        int mid = (end - start) / 2 + start;
        // 左半
        String lcpLeft = longestCommonPrefix(strs, start, mid);
        // 右半
        String lcpRight = longestCommonPrefix(strs, mid + 1, end);
        // 小问题解决
        return commonPrefix(lcpLeft, lcpRight);
    }
}
// 小问题解决
public String commonPrefix(String lcpLeft, String lcpRight) {
    int minLength = Math.min(lcpLeft.length(), lcpRight.length());
    for (int i = 0; i < minLength; i++) {
        if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
            return lcpLeft.substring(0, i);
        }
    }
    return lcpLeft.substring(0, minLength);
}

20ValidParentheses

看答案了。。。

后遇到的要先闭合

所以用栈来存储左半部分，一遇到右半部分的字符，就检查最晚入栈的栈顶字符是不是对应的前半部分的字符

如果是，就出栈，然后继续检查下一个…

public boolean isValid(String s) {

    int length = s.length();
    if (length % 2 != 0)
        return false;

    Stack<Character> stack = new Stack<>();

    HashMap<Character, Character> hashMap = new HashMap<>();
    hashMap.put(')', '(');
    hashMap.put(']', '[');
    hashMap.put('}', '{');

    // 从头一个一个找
    for (int i = 0; i < length; i++) {
        char c = s.charAt(i);
        
        if (!hashMap.containsKey(c)){ // 如果不是后半部分（即是前半部分），就入栈
            stack.push(c);
        }else if (stack.isEmpty() || stack.peek() != hashMap.get(c)){
            // 如果是后半部分
            // 栈里已经没元素了，说明 无法匹配
            // 栈顶元素和后半部分 不匹配
            return false;
        }else{
            // 栈顶元素和后半部分 匹配，出栈，下一个
            stack.pop();
        }
    }
    // 都匹配一定是 空栈
    if (!stack.isEmpty())
        return false;
    return true;
}

21MergeTwoSortedLists

用递归，先看两个链表头节点哪个小，先“吃掉”一个，然后继续让剩下的节点比较。

• LeetCode的解释

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null)
        return l2;
    else if (l2 == null)
        return l1;
    else if (l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

26RemoveDuplicatesFromSortedArray

直接用双指针i、j，i决定无重复数组最后一个元素的索引，j来遍历数组

如果i元素与j元素相等，即重复，就继续往后遍历

如果不等，即不重复，i、j均往后移一位

public int removeDuplicates(int[] nums) {
    int length = nums.length;
    int i, j;
    for (i = 0, j = 1; i < length && j < length;) {
        if (nums[j] == nums[i]){
            j++;
        }else {
            nums[i + 1] = nums[j];
            i++;
            j++;
        }
    }

    return i + 1;
}

27RemoveElement

拷贝覆盖

设置一个i，代表不一样的元素下标。直接遍历，遇到不一样的就把nums[i]替换成当前num： nums[i] = num，然后 i++

public int removeElement(int[] nums, int val) {

    int i = 0;
    for (int num : nums) {
        if (num != val){
            nums[i] = num;
            i++;
        }
    }
    return i;
}

Stack

20ValidParentheses(E)

155MinStack(E)

我的方法是在插入和弹出时就计算最小值

class MinStack {

    private LinkedList<Integer> stack;
    private int min = Integer.MAX_VALUE;
   
    public MinStack() {
        stack = new LinkedList<>();
    }

    public void push(int x) {
        stack.push(x);
        if (x < min)
            min = x;
    }

    public void pop() {
        if (top() == min){
            stack.pop();
            int big_min = Integer.MAX_VALUE;
            for (Integer integer : stack) {
                if (integer < big_min)
                    big_min = integer;
            }
            min = big_min;
        }else {
            stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

而官方是使用辅助栈，和主栈同步，储存每个元素作为栈顶时的最小值

因为只要栈顶元素不变，其他元素就不变，当前的最小值就不变

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

71SimplifyPath(M)

我起初是打算一个一个判断，搞个栈，遇到非 / 、 .. 和 . 就跳过……但是 .. 就不好判断了。想了半天。然后就想到一个api split ，我直接就mlgb了，我tm直接我tm。接着看了答案，确实可以这样

直接 split("/") 把各个部分组成一个数组

因为两个 / 中间只存在 . 或者 .. ， . 、 .. 才有效。所以

遇到 .. ，且栈不为空，就弹出

遇到不是 . 的，且不是空串，就push

最后balabala输出

public String simplifyPath(String path) {
    String[] paths = path.split("/");
    LinkedList<String> stack = new LinkedList<>();

    for (String p : paths) {
        if ("..".equals(p)) {
            if (!stack.isEmpty())
                stack.pop();
        } else if (!".".equals(p) && !p.isEmpty()) {
            stack.push(p);
        }
    }
    if (stack.isEmpty())
        return "/";
    StringBuilder res = new StringBuilder();
    while (!stack.isEmpty()){
        res.insert(0, stack.pop());
        res.insert(0, "/");
    }
    return res.toString();
}

94BinaryTreeInorderTraversal(M)

中序遍历，就是根节点放中间。

我就是直接递归：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {


        List<Integer> all = new LinkedList<>();
        if (root == null)
            return all;

        if (root.left != null){
            List<Integer> left = inorderTraversal(root.left);
            all.addAll(left);
        }
        all.add(root.val);
        if (root.right != null){
            List<Integer> right = inorderTraversal(root.right);
            all.addAll(right);
        }
        return all;
    }
}

但是时间和空间都很难看。。我想原因应该是每个递归都new了一个List。

然后实参为引用，改进：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();

        myInorderTraversal(root, res);

        return res;
    }

    private void myInorderTraversal(TreeNode root, List<Integer> res){
        if (root == null)
            return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left != null)
            myInorderTraversal(left, res);
        res.add(root.val);
        if (right != null)
            myInorderTraversal(right, res);
    }
}

然后看答案，还有栈的解法，用迭代表示递归。看得懂，但我写不出来。。。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    Deque<TreeNode> stk = new LinkedList<TreeNode>();
    while (root != null || !stk.isEmpty()) {
        while (root != null) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.add(root.val);
        root = root.right;
    }
    return res;
}

103BinaryTreeZigzagLevelOrderTraversal(M)

我也不知道为啥官方为啥归到Stack里面。答案也没用栈

蛇形输出二叉树

我的思路是双端队列，然后每层弹出和插入都变一个方向，插入时收集数据放入list

比如二叉树是1 23 4567 89

第一趟遍历1，从first弹出，即弹出1，从last插入1的右左(32)，此时queue为32

第二趟遍历32，从last弹出，即先弹2再3，从first依次插入2的左右(45)和3的左右(67)，此时queue为7654

第三趟遍历7654，从first弹出，即先弹7再654，从last依次插入98，此时queue为98

第四趟遍历98，从last弹出，即先弹8再9，从first依次…没了

写的时候乱得厉害，一下first一下last，一下左右一下右左

事实证明我想复杂了…

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();

    List<List<Integer>> res = new ArrayList<>();


    boolean flag = true;
    if (root != null) {
        queue.addLast(root);
        //System.out.print(root.val);
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.val);
        res.add(list);
    }
    while (!queue.isEmpty()) {
        ArrayList<Integer> list = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            if (flag) {
                TreeNode first = queue.pollFirst();
                TreeNode right = first.right;
                if (right != null) {
                    queue.addLast(right);
                    //System.out.print(first.right.val);
                    list.add(right.val);
                }
                TreeNode left = first.left;
                if (left != null) {
                    queue.addLast(left);
                    //System.out.print(first.left.val);
                    list.add(left.val);
                }
            } else {
                TreeNode last = queue.pollLast();
                if (last.left != null) {
                    TreeNode left = last.left;
                    queue.addFirst(left);
                    //System.out.print(last.left.val);
                    list.add(left.val);
                }
                if (last.right != null) {
                    TreeNode right = last.right;
                    queue.addFirst(right);
                    //System.out.print(right.val);
                    list.add(right.val);
                }
            }
        }
        flag = !flag;
        if (!list.isEmpty())
            res.add(list);
    }
    return res;
}

---

答案比我简洁多了，通过一个null来分隔每一层，遇到null就把得到的level_list存进res

维护一个顺序标志is_order_left，过一层就变，决定元素插入level_list是头插还是尾插

元素	level_list	queue	is_order_left	res
1	1	null,2,3	true
null		2,3,null	false	1
2	2(addFirst)	3,null,4,5	false	1
3	3,2(addFirst)	null,4,5,6,7	false	1
null		4,5,6,7,null	true	1,32
4	4(addLast)	5,6,7,null,8	true	1,32
5	4,5(addLast)	5,6,7,null,8,9	true	1,32
…

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<List<Integer>>();
    }

    List<List<Integer>> results = new ArrayList<List<Integer>>();

    // add the root element with a delimiter to kick off the BFS loop
    LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
    node_queue.addLast(root);
    node_queue.addLast(null);

    LinkedList<Integer> level_list = new LinkedList<Integer>();
    boolean is_order_left = true;

    while (node_queue.size() > 0) {
        TreeNode curr_node = node_queue.pollFirst();
        if (curr_node != null) {
            if (is_order_left)
                level_list.addLast(curr_node.val);
            else
                level_list.addFirst(curr_node.val);

            if (curr_node.left != null)
                node_queue.addLast(curr_node.left);
            if (curr_node.right != null)
                node_queue.addLast(curr_node.right);

        } else {
            // we finish the scan of one level
            results.add(level_list);
            level_list = new LinkedList<Integer>();
            // prepare for the next level
            if (node_queue.size() > 0)
                node_queue.addLast(null);
            is_order_left = !is_order_left;
        }
    }
    return results;
}

144BinaryTreePreorderTraversal(M)

用迭代，前序遍历

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stk = new LinkedList<>();
    while (root != null || !stk.isEmpty()) {
        while (root != null) {
            stk.push(root);
            res.add(root.val);
            root = root.left;
        }
        root = stk.pop();
        //res.add(root.val);
        root = root.right;
    }
    return res;
}

★145BinaryTreePostorderTraversal(M)

用迭代，后序遍历

这里要用一个变量来判断这个节点的右子节点是否已经入res

为什么只存一个? 因为子节点存完下一个就到它自己了，只需要存之前的那个

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();

    if (root == null)
        return res;
    Deque<TreeNode> stack = new LinkedList<>();

    TreeNode prev = null;

    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        //if (root.right != null) {
        //    stack.push(root);
        //    root = root.right;
        //} else {
        //    res.add(root.val);
        //} 这是错的
        
        // 如果这个节点的右子节点为空或不为空但已经入res
        // 为什么只存一个? 因为子节点存完下一个就到它自己了，只需要存之前的那个
        if (root.right == null || root.right == prev) {
            res.add(root.val);
            prev = root;
            root = null;
        } else { // 如果这个节点的右子节点不为空且没入res
            stack.push(root);
            root = root.right;
        }
    }
    return res;
}

150EvaluateReversePolishNotation(M)

逆波兰表示式

就那样，用栈实现

public int evalRPN(String[] tokens) {

    Deque<Integer> stack = new LinkedList<>();


    for (String token : tokens) {
        // +, -, *, /
        if (token.isEmpty())
            continue;
        Integer first, sec;
        switch (token){
            case "+":
                first = stack.pop();
                sec = stack.pop();
                stack.push(sec + first);
                break;
            case "-":
                first = stack.pop();
                sec = stack.pop();
                stack.push(sec - first);
                break;
            case "*":
                first = stack.pop();
                sec = stack.pop();
                stack.push(sec * first);
                break;
            case "/":
                first = stack.pop();
                sec = stack.pop();
                stack.push(sec / first);
                break;
            default:
			   stack.push(Integer.valueof(token));
        }
    }

    return stack.poll();
}

看了评论，也可以用数组实现栈，快一点

public int evalRPN(String[] tokens) {

    //Deque<Integer> stack = new LinkedList<>();

    int[] stack = new int[tokens.length];
    int index = -1;

    for (String token : tokens) {
        // +, -, *, /
        if (token.isEmpty())
            continue;
        int first, sec;
        switch (token){
            case "+":
                first = stack[index];
                sec = stack[index - 1];
                index--;
                stack[index] = sec + first;
                break;
            case "-":
                first = stack[index];
                sec = stack[index - 1];
                index--;
                stack[index] = sec - first;
                break;
            case "*":
                first = stack[index];
                sec = stack[index - 1];
                index--;
                stack[index] = sec * first;
                break;
            case "/":
                first = stack[index];
                sec = stack[index - 1];
                index--;
                stack[index] = sec / first;
                break;
            default:
                index++;
                stack[index] = Integer.parseInt(token);
        }
    }

    return stack[0];
}

173BinarySearchTreeIterator(M)

二叉搜索树迭代器

因为二叉搜索树是左小右大的，直接中序遍历生成的序列就是从小到大的

class BSTIterator {

    ArrayList<Integer> res;
    int i = 0;

    public BSTIterator(TreeNode root) {
        res = new ArrayList<>();
        myInorderTraversal(root, res);
    }

    public int next() {
        return res.get(i++);
    }

    public boolean hasNext() {
        if (i < res.size())
            return true;
        return false;
    }

    private void myInorderTraversal(TreeNode root, List<Integer> res){
        if (root == null)
            return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left != null)
            myInorderTraversal(left, res);
        res.add(root.val);
        if (right != null)
            myInorderTraversal(right, res);
    }
}

227BasicCalculatorIi(M)

基本计算器（没有括号）

想到之前的逆波兰表示，整蒙圈了

看了评论

用一个char来存储一个数之前的符号，等拿到这个数(如果当前字符是非数字，那就是这个数已经拿到)，就能根据这个char来判断

如果是加减，就直接入栈

如果是乘除，就把栈顶弹出，和已经拿到的这个数做运算

public int calculate(String s) {
    Deque<Integer> stack = new LinkedList<>();

    char[] nums = (s).toCharArray();

    int num = 0;
    char oprt = '+';

    for (int i = 0; i < nums.length; i++) {
        // 如果是数字，就拿数
        if (Character.isDigit(nums[i])) {
            num = num * 10 + (nums[i] - '0');
        }
        // 如果不是数字，也不是空格，或者这时候已经是最后一个字符了，就要操作了
        if (!Character.isDigit(nums[i]) && nums[i] != ' ' || i == nums.length - 1) {
            // 乘除的时候弹出的栈顶
            int pre;
            // 这个数num之前的符号
            switch (oprt){
                case '+':
                    // 如果是加减，就直接入栈
                    stack.push(num);
                    break;
                case '-':
                    stack.push(-num);
                    break;
                case '*':
                    // 乘除就拿栈顶来运算
                    pre = stack.pop();
                    stack.push(num * pre);
                    break;
                case '/':
                    pre = stack.pop();
                    stack.push(pre / num);
                    break;
            }
            // 记得把操作变为当前字符
            oprt = nums[i];
            // 重新拿数字
            num = 0;
        }

    }


    // 直接连加
    int sum = 0;
    while (!stack.isEmpty()){
        sum += stack.pop();
    }
    return sum;
}

232ImplementQueueUsingStacks(E)

栈实现队列

就这样

class MyQueue {

    Deque<Integer> left_stack;
    Deque<Integer> right_stack;


    public MyQueue() {
        left_stack = new LinkedList<>();
        right_stack = new LinkedList<>();
    }


    public void push(int x) {
        left_stack.push(x);
    }


    public int pop() {
        moveToRight();
        Integer pop = right_stack.pop();
        moveToLeft();
        return pop;
    }


    public int peek() {
        moveToRight();
        Integer peek = right_stack.peek();
        moveToLeft();
        return peek;
    }


    public boolean empty() {
        return left_stack.isEmpty();
    }

    private void moveToRight(){
        while (!left_stack.isEmpty()){
            right_stack.push(left_stack.pop());
        }
    }
    private void moveToLeft(){
        while (!right_stack.isEmpty()){
            left_stack.push(right_stack.pop());
        }
    }
}

316RemoveDuplicateLetters(M)

去除重复元素，并保持字典序

第一次字典序理解错了，完全瞎做

第二次还是理解不到位，忘了一个条件

• 当当前元素小于栈底元素，但字符串后面已经没有栈底这个元素了，就不能移除

第三个是参考答案

public String removeDuplicateLetters(String s) {

    // first
    //StringBuilder builder = new StringBuilder("");
    //
    //LinkedHashSet<Character> hashSet = new LinkedHashSet<>();
    //
    //
    //char min = 'z';
    //
    //char[] chars = s.toCharArray();
    //for (char c : chars) {
    //    if (c - min < 0) {
    //        min = c;
    //    }
    //    hashSet.add(c);
    //}
    //builder.append(min);
    //for (Character character : hashSet) {
    //    if (min != character)
    //        builder.append(character);
    //}
    //
    //return builder.toString();

    /*==================*/

    // second
    //StringBuilder builder = new StringBuilder("");
    //
    //Deque<Character> list = new LinkedList<>();
    //
    //for (int i = 0; i < s.length(); i++) {
    //    char now = s.charAt(i);
    //    if (list.isEmpty()){
    //        list.addLast(now);
    //    }else if (!list.contains(now) && list.getFirst() > now){
    //        while (!list.isEmpty() && list.getFirst() > now){
    //            list.removeFirst();
    //        }
    //        list.addFirst(now);
    //    }else if (!list.contains(now)){
    //        list.addLast(now);
    //    }
    //}
    //
    //while (!list.isEmpty()){
    //    builder.append(list.pop());
    //}
    //return builder.toString();

    // third

    Stack<Character> stack = new Stack<>();

    // this lets us keep track of what's in our solution in O(1) time
    HashSet<Character> seen = new HashSet<>();

    // this will let us know if there are any more instances of s[i] left in s
    HashMap<Character, Integer> last_occurrence = new HashMap<>();

    for (int i = 0; i < s.length(); i++)
        last_occurrence.put(s.charAt(i), i);

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // we can only try to add c if it's not already in our solution
        // this is to maintain only one of each character
        if (!seen.contains(c)) {
            // if the last letter in our solution:
            //     1. exists
            //     2. is greater than c so removing it will make the string smaller
            //     3. it's not the last occurrence
            // we remove it from the solution to keep the solution optimal
            while (!stack.isEmpty() && c < stack.peek() && last_occurrence.get(stack.peek()) > i) {
                seen.remove(stack.pop());
            }
            seen.add(c);
            stack.push(c);
        }
    }
    StringBuilder sb = new StringBuilder(stack.size());
    for (Character c : stack) sb.append(c.charValue());
    return sb.toString();
}

331VerifyPreorderSerializationOfABinaryTree(M)

验证二叉树的前序序列化

不会。。。

答案真简单，但想想也应该是这样：

我们可以定义一个概念，叫做槽位，二叉树中任意一个节点或者空孩子节点都要占据一个槽位。二叉树的建立也伴随着槽位数量的变化。开始时只有一个槽位，如果根节点是空节点，就只消耗掉一个槽位，如果根节点不是空节点，除了消耗一个槽位，还要为孩子节点增加两个新的槽位。之后的节点也是同理。

有了上面的讨论，方法就很简单了。依次遍历前序序列化，根据节点是否为空，按照规则消耗/增加槽位。如果最后可以将所有的槽位消耗完，那么这个前序序列化就是合法的。

• 开始时只有一个可用槽位。

• 空节点和非空节点都消耗一个槽位。

• 空节点不增加槽位，非空节点增加两个槽位。

public boolean isValidSerialization(String preorder) {


    int slots = 1;

    for (String node : preorder.split(",")) {
        --slots;

        if (slots < 0)
            return false;

        if (!node.equals("#"))
            slots += 2;
    }

    return slots == 0;
}

341FlattenNestedListIterator(M)

扁平化嵌套列表迭代器

直接初始化就递归

// This is the interface that allows for creating nested lists.
// You should not implement it, or speculate about its implementation
public interface NestedInteger {

    // @return true if this NestedInteger holds a single integer, rather than a nested list.
    public boolean isInteger();

    // @return the single integer that this NestedInteger holds, if it holds a single integer
    // Return null if this NestedInteger holds a nested list
    public Integer getInteger();

    // @return the nested list that this NestedInteger holds, if it holds a nested list
    // Return null if this NestedInteger holds a single integer
    public List<NestedInteger> getList();
}



public class NestedIterator implements Iterator<Integer> {

    private Deque<Integer> list;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = new LinkedList<>();
        listPush(nestedList);
    }

    private void listPush(List<NestedInteger> nestedList){
        for (NestedInteger nestedInteger : nestedList) {
            if (nestedInteger.isInteger())
                list.push(nestedInteger.getInteger());
            else {
                listPush(nestedInteger.getList());
            }
        }
    }

    @Override
    public Integer next() {
        return list.pollLast();
    }

    @Override
    public boolean hasNext() {
        return !list.isEmpty();
    }
}

从头开始

2AddTwoNumbers(M)

两数相加

我是用递归的，因为试着直接循环链表感觉太乱了，变量太多，脑子转不过来

因为每位都是个位十进制，只要处理好进位就行

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
/* ==================================== */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 根节点
    ListNode res = new ListNode();
    // 先算出第一位的和，包括进位
    if (l1 != null)
        res.val += l1.val;
    if (l2 != null)
        res.val += l2.val;
    // 拿到进位
    int more = res.val / 10;
    // 拿到个位数
    res.val %= 10;
    // 拿到下一个节点
    res.next = myAddTwoNumbers(l1 == null ? null : l1.next, l2 == null ? null : l2.next, more);

    return res;
}

public ListNode myAddTwoNumbers(ListNode l1, ListNode l2, int more) {
    // 递归结束
    if (l1 == null && l2 == null){
        // 如果还有进位，就再加一个节点，结束
        if (more != 0){
            return new ListNode(more);
        }
        return null;
    }
    // 构建新节点
    ListNode res = new ListNode();
    // 拿和
    if (l1 != null)
        res.val += l1.val;
    if (l2 != null)
        res.val += l2.val;
    // 加上前一位的进位
    res.val += more;
    // 拿到这次的进位
    more = res.val / 10;
    // 拿到个位
    res.val %= 10;
    // 拿到下一位
    res.next = myAddTwoNumbers(l1 == null ? null : l1.next, l2 == null ? null : l2.next, more);

    return res;
}

3LongestSubstringWithoutRepeatingCharacters(M)

无重复字符的最长子串

我的解法就是那样，但做了重复的判断，因为不知道map怎么删掉前i个元素

public int lengthOfLongestSubstring(String s) {
    int length = s.length();
    if (length == 0)
        return 0;
    if (length == 1)
        return 1;

    HashMap<Character, Integer> map = new HashMap<>();

    int count = 0, max = 0;

    for (int i = 0; i < length; i++) {
        char now = s.charAt(i);
        if (map.get(now) == null){
            map.put(now, i);
            count++;
            if (count > max)
                max = count;
        }else {
            i = map.get(now);
            count = 0;
            map.clear();
        }
    }

    return max;
}

答案：

依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的

假设我们选择字符串中的第 kk 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r_k 。那么当我们选择第 k+1个字符作为起始位置时，首先从 k+1 到 r_k 的字符显然是不重复的，并且由于少了原本的第 k 个字符，我们可以尝试继续增大 r_k，直到右侧出现了重复字符为止

public int lengthOfLongestSubstring(String s) {
    Set<Character> occ = new HashSet<>();
    int n = s.length();

    int rk = -1, ans = 0;
    // i 是指子串的第一个下标
    for (int i = 0; i < n; ++i) {
        if (i != 0) {
            // 每过一个子串，就从set中移除前一个子串的头字符
            occ.remove(s.charAt(i - 1));
        }
        // 从这个rk开始，继续往后走，这里避免了重复判断
        while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
}

5LongestPalindromicSubstring

最长回文子串

不会，看了答案，用动态规划，因为回文串首尾去掉还是回文串，所以有状态转移，即求出边界(一个字符、两个字符)，就能往上推

public String longestPalindrome(String s) {

    int l = s.length();
    boolean[][] dp = new boolean[l][l];

    String res = "";

    // 从子串长度为 1 开始
    for (int subLength = 0; subLength < l; subLength++){
        for (int left = 0; left + subLength < l; left++){
            // 拿到左右索引
            int right = left + subLength;
            // 当只有一个元素时，边界①
            if (subLength == 0){
                dp[left][right] = true;
            }else if (subLength == 1){ // 当有两个元素时，边界②
                if (s.charAt(left) == s.charAt(right)){
                    dp[left][right] = true;
                }
            }else { // 从下往上
                dp[left][right] = dp[left + 1][right - 1] && (s.charAt(left) == s.charAt(right));
            }

            if (dp[left][right] && subLength + 1 > res.length()){
                // 拿到子串，注意 subLength 要 + 1
                res = s.substring(left, left + 1 + subLength);
            }
        }
    }

    return res;
}

6ZigzagConversion

Z 字形变换

直接暴力

构造一个 numRows 个字符串的数组，然后一个一个字符遍历s，用 r 来控制加到哪一行，用一个 flag 来控制行的遍历顺序，遇到边界就反转 flag

public String convert(String s, int numRows) {
    if (s == null)
        return "";
    int length;
    if ((length = s.length()) == 0)
        return "";
    if (length <= numRows || numRows == 1)
        return s;


    //String[] res = new String[numRows];
    // 改成 StringBuilder 也没啥卵用
    StringBuilder[] res = new StringBuilder[numRows];

    boolean flag = true;
    for (int i = 0, r = 0; i < length; i++) {
        String c = s.substring(i, i + 1);
        //res[r] = (res[r] == null) ? c : (res[r] + c);
        if (res[r] == null)
            res[r] = new StringBuilder(c);
        else
            res[r].append(c);
        if (flag)
            r++;
        else
            r--;
        if (r == numRows - 1 || r == 0)
            flag = !flag;
    }

    StringBuilder builder = new StringBuilder();
    //for (String row : res) {
    //    builder.append(row);
    //}
    for (StringBuilder row : res) {
        builder.append(row);
    }
    return builder.toString();
}

然后看了答案，乖乖，跟我一样的思维。。。。不贴出来了

每日一题

217ContainsDuplicate(E)

存在重复元素

public boolean containsDuplicate(int[] nums) {

    // 我是直接存hash表，然后判断是否存在
    //HashSet<Integer> hashSet = new HashSet<>();
    //
    //for (int num : nums) {
    //    if (hashSet.contains(num)){
    //        return true;
    //    }else {
    //        hashSet.add(num);
    //    }
    //}
    //return false;


    // 答案。。。add直接判断
    //HashSet<Integer> hashSet = new HashSet<>();
    //
    //for (int num : nums) {
    //    if (!hashSet.add(num)){
    //        return true;
    //    }
    //}
    //return false;

    // 也可先排序，排完序相同的一定在相邻
    Arrays.sort(nums);
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

49GroupAnagrams

字母异位词分组

利用哈希表的特性

public List<List<String>> groupAnagrams(String[] strs) {

    // map 存放有相同”公共串“的 List
    HashMap<String, List<String>> hashMap = new HashMap<>();

    for (String str : strs) {
        // 先排序，拿到“公共串”
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String s = String.valueOf(chars);

        List<String> list;
        // 如果 map 没有，就 new 一个放进去
        if ((list = hashMap.get(s)) == null){
            list = new LinkedList<>();
        }
        list.add(str);
        hashMap.put(s, list);
    }

    return new LinkedList<>(hashMap.values());
}

遍历，顺便把字符串的字符排个序，看看 HashMap 里有没有，要没有就 new 一个 List ，把没排序的 add 进 List，再把 List 放回去

看了答案，居然有 api:

public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

还有一种方法，用质数：

用质数表示26个字母，把字符串的各个字母相乘，这样可保证字母异位词的乘积必定是相等的

738MonotoneIncreasingDigits

cnm，集合类用多了，惯性就用了集合，即使方法对了，也是慢

只要下一位比之前的首位大，就要把之前的都变成 9，记得记录此时的索引，免得下一次再算一次

我的：

public int monotoneIncreasingDigits(int N) {

    LinkedList<Integer> list = new LinkedList<>();

    int point = 0;

    while (N != 0) {
        int low = N % 10;

        if (list.isEmpty())
            list.addLast(low);
        else if (low > list.getLast()) {
            int size = list.size();
            for (int i = size - 1; i >= point; i--)
                list.set(i, 9);
            list.addLast(low - 1);
            point = size;
        }else {
            list.addLast(low);
        }
        N /= 10;
    }

    int mult = 1, sum = 0;
    Iterator<Integer> itr = list.iterator();
    while (itr.hasNext()) {
        Integer next = itr.next();
        sum += next * mult;
        mult *= 10;
    }

    return sum;
}

官方的：

public int monotoneIncreasingDigits(int N) {
    char[] strN = Integer.toString(N).toCharArray();
    int i = 1;
    while (i < strN.length && strN[i - 1] <= strN[i]) {
        i += 1;
    }
    if (i < strN.length) {
        while (i > 0 && strN[i - 1] > strN[i]) {
            strN[i - 1] -= 1;
            i -= 1;
        }
        for (i += 1; i < strN.length; ++i) {
            strN[i] = '9';
        }
    }
    return Integer.parseInt(new String(strN));
}

先看看有几位是递增的，就不用重复判断了

290WordPattern

一位一位同时遍历，组成键值对插入 HashMap

如果 key 不存在，且不存在相同的 value，就插入

key 存在，value 也相同，跳过

其他情况都 false

public boolean wordPattern(String pattern, String s) {
    String[] two = s.split(" ");

    if (pattern.length() != two.length)
        return false;

    HashMap<Character, String> map = new HashMap<>();


    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        if (map.containsKey(c)) {
            if (!map.get(c).equals(two[i])) // key 相同，value 又不同
                return false;
        }else if (map.containsValue(two[i])){ // key 不同，value 又相同
            return false;
        }else
            map.put(c, two[i]);
    }
    return true;
}

714BestTimeToBuyAndSellStockWithTransactionFee

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

很明显是 DP

找状态，从第 n 天开始

设 为第 i 天交易结束后，dp[i][0] 表示手上没有股票的收益，dp[i][1] 为有股票的收益，price( i ) 表示第 i 天的股价，fee 表示手续费

dp[i][0] 代表：

• 前一天，有两种情况： dp[i - 1][0] 和 dp[i - 1][1]，则有
  • dp[i][0] = dp[i - 1][0]
  • dp[i][0] = dp[i - 1][1] + price( i ) + fee
  • 有状态转移：dp[i][0] = max( dp[i - 1][0], dp[i - 1][1] + price( i ) + fee )

dp[i][1] 代表：

• 前一天，有两种情况： dp[i - 1][1] 和 dp[i - 1][0]，则有
  • dp[i][1] = dp[i - 1][1]
  • dp[i][1] = dp[i - 1][0] - price( i )
  • 有状态转移：dp[i][1] = max( dp[i - 1][1], dp[i - 1][0] - price( i ) )

而假设 i 是最后一天，dp[i][0] 肯定比 dp[i][1] 大

最后返回 dp[i][0] 就好了

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

// 简化
// 都是从前往后，只保留两个变量即可
public int maxProfit(int[] prices, int fee) {
    int n = prices.length;
    int sell = 0, buy = -prices[0];
    for (int i = 1; i < n; ++i) {
        sell = Math.max(sell, buy + prices[i] - fee);
        buy = Math.max(buy, sell - prices[i]);
    }
    return sell;
}

48RotateImage

旋转图像

n * n 图像顺时针旋转 90°

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 水平翻转
    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < n; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - i - 1][j];
            matrix[n - i - 1][j] = temp;
        }
    }
    // 主对角线翻转
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

746MinCostClimbingStairs

使用最小花费爬楼梯

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

假设数组 cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n-1，楼层顶部对应下标 n，问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。

创建长度为 n + 1 的数组 dp，其中 dp[i] 表示达到下标 i 的最小花费。

由于可以选择下标 0 或 1 作为初始阶梯，因此有 dp[0] = dp[1] = 0

387FirstUniqueCharacterInAString( E )

字符串中的第一个唯一字符

public int firstUniqChar(String s) {

        //HashMap<Character, Integer> times = new HashMap<>();
        //for (int i = 0; i < s.length(); i++) {
        //    char now = s.charAt(i);
        //    times.put(now, times.getOrDefault(now, 0) + 1);
        //}
        //for (int i = 0; i < s.length(); i++) {
        //    if (times.get(s.charAt(i)) == 1){
        //        return i;
        //    }
        //}
        //return -1;

        HashMap<Character, Integer> first = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char now = s.charAt(i);
            if (first.containsKey(now)){
                first.put(now, -1);
            }else {
                first.put(now, i);
            }
        }
        int minIndex = Integer.MAX_VALUE;
        for (Map.Entry<Character, Integer> entry : first.entrySet()) {
            Integer index = entry.getValue();
            if (index != -1 && index < minIndex)
                minIndex = index;
        }

        if (minIndex == Integer.MAX_VALUE)
            return -1;
        return minIndex;
    }

455AssignCookies( E )

先排个序，然后就那样，没啥说的。。

贪心

public int findContentChildren(int[] g, int[] s) {
    
    Arrays.sort(g);
    Arrays.sort(s);
    int res = 0, i = 0, j = 0;

    while (i < g.length && j < s.length){
        if (g[i] <= s[j]){
            i++; j++; res++;
        }else {
            j++;
        }
    }

    return res;
}

85MaximalRectangle( H )

看了 答案，艰难地敲了出来，暴力解法

public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0)
        return 0;

    int row = matrix.length;
    int col = matrix[0].length;

    int[][] length = new int[row][col];

    for (int i = 0; i < row; i++) {
        length[i][0] = Character.getNumericValue(matrix[i][0]);
        for (int j = 1; j < col; j++) {
            if (matrix[i][j] == '1'){
                length[i][j] = length[i][j - 1] + 1;
            }
        }
    }

    int max = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (length[i][j] == '0')
                continue;
            int width = length[i][j];
            max = Math.max(max, length[i][j]);
            for (int k = i - 1; k >= 0; k--){
                width = Math.min(width, length[k][j]);
                max = Math.max(max, width * (i - k + 1));
            }
        }
    }

    return max;
}

单调栈，类比 84LargestRectangleInHistogram

public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }

84LargestRectangleInHistogram

CV 答案

遍历高，采用单调栈，拿到左右边界

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] left = new int[n];
    int[] right = new int[n];

    Stack<Integer> mono_stack = new Stack<Integer>();
    for (int i = 0; i < n; ++i) {
        while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
            mono_stack.pop();
        }
        left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
        mono_stack.push(i);
    }

    mono_stack.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
            mono_stack.pop();
        }
        right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
        mono_stack.push(i);
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
    }
    return ans;
}

188BestTimeToBuyAndSellStockIv( H )

买卖股票的最佳时机 IV

淦，做了 中等的买卖股票，没有限制买卖次数，这道题有限制买卖次数，还是做不出来呜呜呜。。。

！！！注意

buy 数组是进行恰好 j 笔交易，并且当前手上持有一支股票，这种情况下的最大利润

sell 表示恰好进行 j 笔交易，并且当前手上不持有股票，这种情况下的最大利润

public int maxProfit(int k, int[] prices) {
    if (prices.length == 0) {
        return 0;
    }

    int n = prices.length;
    k = Math.min(k, n / 2);
    int[][] buy = new int[n][k + 1];
    int[][] sell = new int[n][k + 1];

    buy[0][0] = -prices[0];
    sell[0][0] = 0;
    for (int i = 1; i <= k; ++i) {
        buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
    }

    for (int i = 1; i < n; ++i) {
        buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
        for (int j = 1; j <= k; ++j) {
            buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
            sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
        }
    }

    return Arrays.stream(sell[n - 1]).max().getAsInt();
}

简化：

public int maxProfit(int k, int[] prices) {
    if (prices.length == 0) {
        return 0;
    }

    int n = prices.length;
    k = Math.min(k, n / 2);
    int[] buy = new int[k + 1];
    int[] sell = new int[k + 1];

    buy[0] = -prices[0];
    sell[0] = 0;
    for (int i = 1; i <= k; ++i) {
        buy[i] = sell[i] = Integer.MIN_VALUE / 2;
    }

    for (int i = 1; i < n; ++i) {
        buy[0] = Math.max(buy[0], sell[0] - prices[i]);
        for (int j = 1; j <= k; ++j) {
            buy[j] = Math.max(buy[j], sell[j] - prices[i]);
            sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);   
        }
    }

    return Arrays.stream(sell).max().getAsInt();
}

121BestTimeToBuyAndSellStock( E )

每次看看这个价格是不是最低值，如果是那就替换，如果不是那就和把自己当成卖出的价格，看看利润有没有最大利润大

public int maxProfit(int[] prices) {
    int maxGot = 0, min = Integer.MAX_VALUE;
    for (int i = 0; i < prices.length; i++) {
        int now = prices[i];
        if (now < min)
            min = now;
        else if (now - min > maxGot)
            maxGot = now - min;
    }
    return maxGot;
}

330PatchingArray( H )

按要求补齐数组

不会。。。

对于任意 1 ≤ y < x，y 已经被覆盖，x 在数组中，因此 y + x 也被覆盖，区间 [x + 1,2x - 1]（即区间 [1,x - 1][1,x − 1] 内的每个数字加上 x 之后得到的区间）内的所有数字也被覆盖，由此可得区间 [1,2x - 1] 内的所有数字都被覆盖

每次找到未被数组 nums 覆盖的最小的整数 x，在数组中补充 x，然后寻找下一个未被覆盖的最小的整数，重复上述步骤直到区间 [1,n] 中的所有数字都被覆盖

public int minPatches(int[] nums, int n) {
    int res = 0;
    long x = 1;
    int length = nums.length, index = 0;
    while (x <= n) {
        if (index < length && nums[index] <= x) {
            x += nums[index];
            index++;
        } else {
            x *= 2;
            res++;
        }
    }
    return res;
}

239SlidingWindowMaximum( H )

滑动窗口最大值

我的做法是最大堆，但是超时了。。。

官方 第一个题解也是最大堆，还有其他更“高级”的解法

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
        public int compare(int[] pair1, int[] pair2) {
            return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
        }
    });
    for (int i = 0; i < k; ++i) {
        pq.offer(new int[]{nums[i], i});
    }
    int[] ans = new int[n - k + 1];
    ans[0] = pq.peek()[0];
    for (int i = k; i < n; ++i) {
        pq.offer(new int[]{nums[i], i});
        while (pq.peek()[1] <= i - k) {
            pq.poll();
        }
        ans[i - k + 1] = pq.peek()[0];
    }
    return ans;
    
    // 我的最大堆超时了
    //PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    //
    //int[] res = new int[nums.length - k + 1];
    //
    //for (int i = 0; i < k; i++) {
    //    maxHeap.add(nums[i]);
    //}
    //res[0] = maxHeap.peek();
    //
    //for (int i = k, j = 1; i < nums.length; i++, j++) {
    //    maxHeap.remove(nums[j - 1]);
    //    maxHeap.add(nums[i]);
    //    res[j] = maxHeap.peek();
    //}
    //
    //return res;
}

509FibonacciNumber( E )

斐波那契数

直接动态规划

1202SmallestStringWithSwaps( M )

交换字符串中的元素

并查集！！！

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        if (pairs.size() == 0) {
            return s;
        }

        // 第 1 步：将任意交换的结点对输入并查集
        int len = s.length();
        UnionFind unionFind = new UnionFind(len);
        for (List<Integer> pair : pairs) {
            int index1 = pair.get(0);
            int index2 = pair.get(1);
            unionFind.union(index1, index2);
        }

        // 第 2 步：构建映射关系
        char[] charArray = s.toCharArray();
        // key：连通分量的代表元，value：同一个连通分量的字符集合（保存在一个优先队列中）
        Map<Integer, PriorityQueue<Character>> hashMap = new HashMap<>(len);
        for (int i = 0; i < len; i++) {
            int root = unionFind.find(i);
            //            if (hashMap.containsKey(root)) {
            //                hashMap.get(root).offer(charArray[i]);
            //            } else {
            //                PriorityQueue<Character> minHeap = new PriorityQueue<>();
            //                minHeap.offer(charArray[i]);
            //                hashMap.put(root, minHeap);
            //            }
            // 上面六行代码等价于下面一行代码，JDK 1.8 以及以后支持下面的写法
            hashMap.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(charArray[i]);
        }

        // 第 3 步：重组字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            int root = unionFind.find(i);
            stringBuilder.append(hashMap.get(root).poll());
        }
        return stringBuilder.toString();
    }

    private class UnionFind {

        private int[] parent;
        /**
             * 以 i 为根结点的子树的高度（引入了路径压缩以后该定义并不准确）
             */
        private int[] rank;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            if (rank[rootX] == rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度仅加了 1
                rank[rootY]++;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度不变
            } else {
                // 同理，此时以 rootX 为根结点的树的高度不变
                parent[rootY] = rootX;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}

523ContinuousSubarraySum

动归超时，数组过大

我的：

public boolean checkSubarraySum(int[] nums, int k) {
    int[] cav = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        cav[i] = nums[i];
    }
    for (int count = 2; count <= nums.length; count++) {
        for (int i = 0; i + count - 1 < nums.length; i++) {
            cav[i] += nums[i + count - 1];
            if (cav[i] % k == 0)
                return true;
        }
    }
    return false;
}

答案：同余定理 。。。

public boolean checkSubarraySum(int[] nums, int k) {
    int m = nums.length;
    if (m < 2) {
        return false;
    }
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    map.put(0, -1);
    int remainder = 0;
    for (int i = 0; i < m; i++) {
        remainder = (remainder + nums[i]) % k;
        if (map.containsKey(remainder)) {
            int prevIndex = map.get(remainder);
            if (i - prevIndex >= 2) {
                return true;
            }
        } else {
            map.put(remainder, i);
        }
    }
    return false;
}

没想到，暴力还更快：

public boolean checkSubarraySum(int[] nums, int k) {
    // 当出现两个连续的0时，直接返回true，因为 0 % k = 0
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == 0 && nums[i + 1] == 0) {
            return true;
        }
    }

    // 其中i为左端点，j为右端点，遍历每种情况
    for (int i = 0; i < nums.length; i++) {
        int sum = nums[i];
        for (int j = i + 1; j < nums.length; j++) {
            sum += nums[j];
            if (sum % k == 0) {
                return true;
            }
        }
        // 加到一起之后发现都没k大，后面的也不会再比k大了，跳过
        if (sum < k) {
            break;
        }
    }
    return false;
}

剑指 Offer

15二进制中1的个数

public int hammingWeight(int n) {
    int res = 0;
    while (n != 0){
        res += (n & 1);
        n >>>= 1;
    }

    return res;
}

17打印从1到最大的n位数

考虑大数，用 String 存放

递归生成

具体解释：LeetCode 评论

StringBuilder res;
int nine = 0, count = 0, start, n;
char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public String printNumbers(int n) {
    this.n = n;
    res = new StringBuilder();
    num = new char[n];
    start = n - 1;
    dfs(0);
    res.deleteCharAt(res.length() - 1);
    return res.toString();
}
void dfs(int x) {
    if(x == n) {
        String s = String.valueOf(num).substring(start);
        if(!s.equals("0")) res.append(s + ",");
        if(n - start == nine) start--;
        return;
    }
    for(char i : loop) {
        if(i == '9') nine++;
        num[x] = i;
        dfs(x + 1);
    }
    nine--;
}

21调整数组顺序使奇数位于偶数前面

我用了三种方法，觉得最后一种最装逼，但是时间只击败了 30%，看了评论，可能是数据量少的原因

• 搞个 list，偶数加后面，奇数加前面
• 搞个数组，两个指针，奇数放前面，左指针++，偶数放后面，右指针–
• 两个指针，分别从左右开始，当左偶右奇，交换

public int[] exchange(int[] nums) {

    // first
    //LinkedList<Integer> list = new LinkedList<>();
    //for (int num : nums) {
    //    if (num % 2 == 0)
    //        list.addLast(num);
    //    else
    //        list.addFirst(num);
    //}
    //int[] res = new int[nums.length];
    //for (int i = 0; i < nums.length; i++) {
    //    res[i] = list.removeFirst();
    //}
    //return res;

    // second
    //int length = nums.length;
    //int[] res = new int[length];
    //int left = 0, right = length - 1;
    //
    //for (int i = 0; i < length; i++) {
    //    if (nums[i] % 2 != 0)
    //        res[left++] = nums[i];
    //    else
    //        res[right--] = nums[i];
    //}
    //
    //return res;

    int length = nums.length;
    int left = 0, right = length - 1;
    while (left < right){
        // 左偶右奇
        if (nums[left] % 2 == 0 && nums[right] % 2 != 0){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++; right--;
        }else if (nums[left] % 2 != 0 && nums[right] % 2 == 0){
            // 左奇右偶
            left++;
            right--;
        }else if (nums[left] % 2 != 0){
            // 左奇右奇
            left++;
        }else if (nums[right] % 2 == 0){
            // 左偶右偶
            right--;
        }
    }
    return nums;
}

22链表中倒数第k个节点

先让 temp = head 往后跑 k 个，如果空，就直接返回 head

如果不空，就开始迭代，temp 每往后走一个，head 就往后走一个，直到 temp 为空，这时候 head 就是结果

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
public ListNode getKthFromEnd(ListNode head, int k) {
    int i = k;
    ListNode temp = head;
    ListNode res = head;
    while (i != 0){
        temp = temp.next;
        i--;
    }
    if (temp == null)
        return res;
    while (temp != null){
        temp = temp.next;
        res = res.next;
    }
    return res;
}

24反转链表

指针太多，脑子差点转不过来

• 要记录三个，一个之前的，一个现在的，一个 next
• 从第二个开始遍历，遍历到的是 现在的
• 记录 next，替换 现在的 next 为 之前的，把 现在的 设为 之前的
• 再把 next 赋值给 现在的
• 继续循环
• 只可意会不可言传…

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public ListNode reverseList(ListNode head) {
    if (head == null)
        return null;

    ListNode pre = head;
    head = head.next;
    pre.next = null;
    while (head != null){
        ListNode next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;

}

25合并两个排序的链表

双指针

注意是引用！！！

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class Solution {
    private ListNode root = new ListNode(0);
    private ListNode now = root;

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        while (l1 != null && l2 != null){
            if (l1.val > l2.val){
                now.next = l2;
                l2 = l2.next;
            }else {
                now.next = l1;
                l1 = l1.next;
            }
            now = now.next;

        }
        if (l1 == null)
            now.next = l2;
        if (l2 == null)
            now.next = l1;
        return root.next;
    }
}

27二叉树的镜像

没啥说的，直接递归交换左右

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 递归终点
        if (root == null)
            return null;

        // 交换左右
        TreeNode left = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(left);
        return root;
    }
}

28对称的二叉树

想歪了，想不出来

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

14- I cuttingRope

动态规划

用 dp[i] 表示 i 分成 2 个或以上数的最大乘积

j 表示第一个乘数

当 i ≥ 2 时，假设对正整数 i 拆分出的第一个正整数是 j（1 ≤ j < i），则有以下两种方案：

• 将 i 拆分成 j 和 i − j 的和，且 i − j 不再拆分成多个正整数，此时的乘积是 j × (i − j)
• 将 i 拆分成 j 和 i − j 的和，且 i − j 继续拆分成多个正整数，此时的乘积是 j × dp[i−j]

当到下一个 i 时，就让 j 从 1 开始，比较 j * ( i - j ) 和 j * dp[i - j] 哪个大，再和之前记录的 dp[i] 比较，直到 j 到达 i 的一半( 这里的一半因为：比如5 = 2 + 3，而 j 表示第一个乘数，如果 j 遍历到 3，那就是 3 + 2，重复了 )

public int cuttingRope(int n) {
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i / 2 + 1; j++) {
            dp[i]= Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}

16数值的整数次方

public double myPow(double x, int n) {
    if (x == 0)
        return 0;
    long b = n;
    double res = 1.0;
    if (b < 0) {
        x = 1 / x;
        b = -b;
    }
    while (b > 0) {
        if ((b & 1) == 1)
            res *= x;
        x *= x;
        b >>= 1;
    }
    return res;
}

18删除链表的节点

public ListNode deleteNode(ListNode head, int val) {

    if (head.val == val)
        return head.next;

    ListNode temp = head;
    ListNode pre = head;
    while (temp != null){
        if (temp.val == val){
            pre.next = temp.next;
        }
        pre = temp;
        temp = temp.next;
    }

    return head;
}

26树的子结构

没做出来…

解析 讲的很明白

public boolean isSubStructure(TreeNode A, TreeNode B) {
    return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
    if(B == null) return true;
    if(A == null || A.val != B.val) return false;
    return recur(A.left, B.left) && recur(A.right, B.right);
}

29顺时针打印矩阵

解析

public int[] spiralOrder(int[][] matrix) {
    if (matrix.length == 0)
        return new int[0];
    int 
        left = 0,
    	right = matrix[0].length - 1,
    	top = 0,
    	bottom = matrix.length - 1,
    	res_i = 0;
    
    int[] res = new int[(right + 1) * (bottom + 1)];
    while (true) {
        for (int i = left; i <= right; i++)
            res[res_i++] = matrix[top][i]; // left to right.
        if (++top > bottom)
            break;
        for (int i = top; i <= bottom; i++)
            res[res_i++] = matrix[i][right]; // top to bottom.
        if (left > --right)
            break;
        for (int i = right; i >= left; i--)
            res[res_i++] = matrix[bottom][i]; // right to left.
        if (top > --bottom)
            break;
        for (int i = bottom; i >= top; i--)
            res[res_i++] = matrix[i][left]; // bottom to top.
        if (++left > right)
            break;
    }
    return res;
}

30包含min函数的栈

辅助栈存非严格递减的元素

class MinStack {

    /**
     * initialize your data structure here.
     */
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

31栈的压入、弹出序列

public boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stack = new LinkedList<>();
    int i = 0;
    for (int num : pushed) {
        stack.push(num); // num 入栈
        while (!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
            stack.pop();
            i++;
        }
    }
    return stack.isEmpty();
}

32-I从上到下打印二叉树

层序遍历，因为不用按层来存，所以比下面的一题简单

public int[] levelOrder(TreeNode root) {
    if (root == null){
        return new int[0];
    }

    List<TreeNode> order = new ArrayList<>();
    int count = 1;
    order.add(root);

    for (int i = 0; i < order.size(); i++) {
        TreeNode now = order.get(i);
        if (now.left != null){
            order.add(now.left);
            count++;
        }
        if (now.right != null){
            order.add(now.right);
            count++;
        }
    }

    int[] res = new int[count];
    int i = 0;
    for (TreeNode node : order) {
        res[i++] = node.val;
    }
    return res;

}

32-II从上到下打印二叉树 II

要按层来存，即 List<List<Integer>>

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new LinkedList<>();
    if (root == null){
        return res;
    }
    Deque<TreeNode> order = new LinkedList<>();
    order.addLast(root);

    while (!order.isEmpty()){
        LinkedList<Integer> line = new LinkedList<>();
        // 要记录每层的数量
        for (int i = order.size(); i > 0; i--){
            TreeNode now = order.poll();
            if (now.left != null)
                order.addLast(now.left);
            if (now.right != null)
                order.addLast(now.right);
            line.addLast(now.val);
        }
        res.add(line);
    }

    return res;
}

32-III从上到下打印二叉树 III

这题在上面的基础上添加了蛇形打印

只要多一个判断 flag 即可

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new LinkedList<>();
    if (root == null)
        return res;

    Deque<TreeNode> order = new LinkedList<>();
    order.addLast(root);

    // 正向打印
    boolean flag = true;

    while (!order.isEmpty()){
        LinkedList<Integer> line = new LinkedList<>();
        for (int i = order.size(); i > 0; i--){
            TreeNode now = order.poll();
            if (now.left != null){
                order.addLast(now.left);
            }
            if (now.right != null){
                order.addLast(now.right);
            }
            if (flag){
                line.addLast(now.val);
            }else {
                line.addFirst(now.val);
            }
        }
        // 改变方向
        flag = !flag;
        res.add(line);
    }
    return res;
}

33二叉搜索树的后序遍历序列

后序遍历，最后一个是根节点

递归，终点是数组只剩下最多两个数

找到左子树和右子树，继续递归分治

public boolean verifyPostorder(int[] postorder) {
    return myVerifyPostorder(postorder, 0, postorder.length - 1);
}
private boolean myVerifyPostorder(int[] postorder, int start, int end){
    // 任意两个数都可构成后序
    if (start >= end - 1)
        return true;
    int temp = start;
    while(postorder[temp] < postorder[end]) temp++;
    // 找到右子树第一个数
    int middle = temp;
    // 因为右子树都大于根，所以看看根前面一个是不是大于根
    while(postorder[temp] > postorder[end]) temp++;
    // 如果都大于，那就继续，小于意味着这不是合法的二叉搜索树
    return temp == end && myVerifyPostorder(postorder, start, middle - 1) && myVerifyPostorder(postorder, middle, end - 1);
}

34二叉树中和为某一值的路径

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }

    void recur(TreeNode root, int tar) {
        if (root == null) return;
        path.add(root.val);
        tar -= root.val;
        if (tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

35复杂链表的复制

自己做，也是用哈希表，但用的是递归，结果直接栈溢出。。。

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        //复制结点值
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        //复制结点指向
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回复制的链表
        return map.get(head);
    }
}

36二叉搜索树与双向链表

想到了中序遍历，但是没想到怎么转换引用

题解

class Solution {
    Node pre, head;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    void dfs(Node cur) {
        // 终止
        if (cur == null)
            return;
        // 中序遍历，到底就是最左边的 head
        dfs(cur.left);

        if (pre != null)
            pre.right = cur;
        else // 如果 pre 为空，即此节点为 head
            head = cur;
        // 把此节点设为 pre
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

37序列化二叉树

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder res = new StringBuilder("[");

        Deque<TreeNode> list = new LinkedList<>();
        list.addLast(root);
        while (!list.isEmpty()) {
            TreeNode now = list.poll();
            if (now != null){
                list.addLast(now.left);
                list.addLast(now.right);
                res.append(now.val).append(",");
            } else {
                res.append("null,");
            }
        }
        res.deleteCharAt(res.length() - 1).append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("[]")){
            return null;
        }
        String[] myData = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(myData[0]));
        Deque<TreeNode> list = new LinkedList<>();
        list.addLast(root);

        int i = 1;
        while (!list.isEmpty()){
            TreeNode now = list.poll();
            if (!myData[i].equals("null")){
                now.left = new TreeNode(Integer.parseInt(myData[i]));
                list.addLast(now.left);
            }
            i++;
            if (!myData[i].equals("null")){
                now.right = new TreeNode(Integer.parseInt(myData[i]));
                list.addLast(now.right);
            }
            i++;
        }
        return root;
    }
}

38字符串的排列

使用回溯，采用交换

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    void dfs(int x) {
        if (x == c.length - 1) {
            res.add(String.valueOf(c)); // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < c.length; i++) {
            if (set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x); // 交换，将 c[i] 固定在第 x 位
            dfs(x + 1); // 开启固定第 x + 1 位字符
            swap(i, x); // 恢复交换
        }
    }

    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

39数组中出现次数超过一半的数字

public int majorityElement(int[] nums) {
    // HashMap 版本
    //Map<Integer, Integer> map = new HashMap<>();
    //int length = nums.length / 2;
    //for(int num : nums) {
    //    map.put(num, map.getOrDefault(num, 0) + 1);
    //    if(map.get(num) > length) {
    //        return num;
    //    }
    //}
    //return 0;
    // 数组排序版本
    //Arrays.sort(nums);
    //return nums[nums.length / 2];
    //摩尔投票法
    int x = 0, votes = 0;
    for(int num : nums){
        if(votes == 0) x = num;
        votes += num == x ? 1 : -1;
    }
    return x;
}

40最小的k个数(TopK)

class Solution {
    //public int[] getLeastNumbers(int[] arr, int k) {
    //Arrays.sort(arr);
    //int[] res = new int[k];
    //for (int i = 0; i < k; i++) {
    //    res[i] = arr[i];
    //}
    //return res;


    //int[] res = new int[k];
    //PriorityQueue<Integer> stack = new PriorityQueue<>();
    //for (int i : arr) {
    //    stack.add(i);
    //}
    //for (int i = 0; i < k; i++) {
    //    res[i] = stack.poll();
    //}
    //return res;
    //}


    public int[] getLeastNumbers(int[] arr, int k) {
        randomizedSelected(arr, 0, arr.length - 1, k);
        int[] vec = new int[k];
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }

    public void randomizedSelected(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomizedPartition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomizedSelected(arr, l, pos - 1, k);
        } else {
            randomizedSelected(arr, pos + 1, r, k - num);
        }
    }

    // 基于随机的划分
    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

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

41数据流中的中位数

class MedianFinder {
    PriorityQueue<Integer> right;
    PriorityQueue<Integer> left;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        right = new PriorityQueue<>();
        left = new PriorityQueue<>((a, b) -> b - a);
    }

    public void addNum(int num) {
        if (left.size() == right.size()){
            left.add(num);
            right.add(left.poll());
        }else {
            right.add(num);
            left.add(right.poll());
        }
    }

    public double findMedian() {
        return left.size() == right.size() ? (left.peek() + right.peek()) / 2.0 : right.peek();
    }
}

42连续子数组的最大和

public int maxSubArray(int[] nums) {
    //int res = nums[0];
    //for (int i = 1; i < nums.length; i++) {
    //    nums[i] += Math.max(nums[i - 1], 0);
    //    res = Math.max(res, nums[i]);
    //}
    //return res;
    int max = nums[0];
    int former = 0;//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0
    int cur = nums[0];//用于记录dp[i]的值
    for (int num : nums) {
        cur = num;
        if (former > 0) cur += former;
        if (cur > max) max = cur;
        former = cur;
    }
    return max;
}

45把数组排成最小的数

public String minNumber(int[] nums) {
    int length = nums.length;
    String[] strs = new String[length];
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < length; i++) {
        strs[i] = String.valueOf(nums[i]);
    }
    myQuickSort(strs, 0, length - 1);
    for (String str : strs) {
        builder.append(str);
    }
    return builder.toString();
}

public void myQuickSort(String[] strs, int left, int right) {
    if (left >= right)
        return;
    int i = left, j = right;
    String temp = strs[i];
    while (i < j) {
        while ((strs[j] + strs[left]).compareTo(strs[left] + strs[j]) >= 0 && i < j)
            j--;
        while ((strs[i] + strs[left]).compareTo(strs[left] + strs[i]) <= 0 && i < j)
            i++;
        temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }
    strs[i] = strs[left];
    strs[left] = temp;
    myQuickSort(strs, left, i - 1);
    myQuickSort(strs, i + 1, right);
}

46把数字翻译成字符串

DP + 空间优化

解析

public int translateNum(int num) {
    String s = String.valueOf(num);
    // x1 x2 x3...xi
    // dp[i] 表示以xi结尾的翻译数量
    // dp[i] = dp[i - 1] + dp[i - 2], 前两个组合在字母表里
    // dp[i] = dp[i - 1], 前两个组合不在字母表里
    // dp[0] = dp[1] = 1, 即无数字和第一个数组的翻译数量为 1

    // a:dp[i], b:dp[i - 1]
    int a = 1, b = 1;
    for (int i = 2; i <= s.length(); i++) {
        String tmp = s.substring(i - 2, i);
        int c = tmp.compareTo("10") >= 0
            && tmp.compareTo("25") <= 0
            ? a + b : a;
        b = a;
        a = c;
    }
    return a;
}

47礼物的最大价值

DP，有手就行

可把顶边和左边的先算一遍，就减少了 > 0 的判断

public int maxValue(int[][] grid) {
    int row = grid.length; // 行
    int col = grid[0].length; // 列

    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            int up = 0, left = 0;
            if(i > 0){
                up = grid[i - 1][j];
            }
            if(j > 0){
                left = grid[i][j - 1];
            }
            grid[i][j] = Math.max(grid[i][j] + left, grid[i][j] + up);
        }
    }
    return grid[row - 1][col - 1];
}

48最长不含重复字符的子字符串

public int lengthOfLongestSubstring(String s) {
    int r = -1, res = 0;
    HashSet<Character> set = new HashSet<>();
    int length = s.length();
    for (int l = 0; l < length; l++) {
        if (l != 0)
            set.remove(s.charAt(l - 1));

        while (r + 1 < length && !set.contains(s.charAt(r + 1))){
            set.add(s.charAt(r + 1));
            r++;
        }
        res = Math.max(res, r - l + 1);
    }
    return res;
}

50第一个只出现一次的字符

public char firstUniqChar(String s) {
    //Map<Character, Boolean> dic = new LinkedHashMap<>();
    //char[] sc = s.toCharArray();
    //for (char c : sc)
    //    dic.put(c, !dic.containsKey(c));
    //for (Map.Entry<Character, Boolean> d : dic.entrySet()) {
    //    if (d.getValue()) return d.getKey();
    //}
    //return ' ';

    int[] map = new int[26];
    int length = s.length();
    char[] ch = s.toCharArray();
    for (int i = 0; i < length; ++i) {
        map[ch[i] - 'a']++;
    }
    for (int i = 0; i < length; ++i) {
        if (map[ch[i] - 'a'] == 1) return ch[i];
    }
    return ' ';
}

51数组中的逆序对

难。

题解

class Solution {
    public int reversePairs(int[] nums) {
        int length = nums.length;

        // 0 个 1 个的序列不存在逆序对
        if (length < 2)
            return 0;

        // 拷贝数组
        int[] copy = new int[length];
        for (int i = 0; i < length; i++) {
            copy[i] = nums[i];
        }

        // 存放排序元素
        int[] tmp = new int[length];
        return reversePairs(copy, 0, length - 1, tmp);

    }

    /**
     * nums[left..right] 计算逆序对个数并排序
     *
     * @param nums
     * @param left
     * @param right
     * @param tmp
     * @return
     */
    private int reversePairs(int[] nums, int left, int right, int[] tmp) {
        // 只有一个元素的时候，不存在逆序对，返回 0
        if (left == right)
            return 0;

        // 分割点
        int mid = left + (right - left) / 2;

        int leftPairs = reversePairs(nums, left, mid, tmp);
        int rightPairs = reversePairs(nums, mid + 1, right, tmp);

        // 如果两个序列已经有序，直接返回
        if (nums[mid] <= nums[mid + 1])
            return leftPairs + rightPairs;

        int crossPairs = mergeAndCount(nums, left, mid, right, tmp);

        return leftPairs + rightPairs + crossPairs;
    }

    /**
     * nums[left..mid] 有序, nums[mid + 1..right] 有序
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     * @param tmp
     * @return
     */
    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] tmp) {
        for (int i = left; i <= right; i++) {
            tmp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = tmp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = tmp[i];
                i++;
            } else if (tmp[i] <= tmp[j]) {
                nums[k] = tmp[i];
                i++;
            } else {
                nums[k] = tmp[j];
                j++;
                // 计算逆序对个数
                count += (mid - i + 1);
            }
        }
        return count;
    }
}

52两个链表的第一个公共节点

太渣了，暴力解法来着

精选解法太妙了

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //HashSet<ListNode> set = new HashSet<>();
    //while (headA != null){
    //    set.add(headA);
    //    headA = headA.next;
    //}
    //while (headB != null){
    //    if (set.contains(headB))
    //        return headB;
    //    headB = headB.next;
    //}
    //return null;

    ListNode ATmp = headA;
    ListNode BTmp = headB;

    while (ATmp != BTmp){
        ATmp = ATmp != null ? ATmp.next : headB;
        BTmp = BTmp != null ? BTmp.next : headA;
    }
    return ATmp;
}

53-I在排序数组中查找数字 I

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }

    /**
     * @param nums
     * @param tar
     * @return 右边界，开
     */
    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= tar)
                i = m + 1;
            else
                j = m - 1;
        }
        return i;
    }
}

53-II 0～n-1中缺失的数字

public int missingNumber(int[] nums) {
    int i = 0, j = nums.length - 1;
    while (i <= j) {
        int m = (i + j) / 2;
        if (nums[m] == m)
            i = m + 1;
        else
            j = m - 1;
    }
    return i;
}

54二叉搜索树的第k大节点

class Solution {
    int res, k;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        myKthLargest(root);

        return res;
    }

    private void myKthLargest(TreeNode root) {
        if (root == null)
            return;
        myKthLargest(root.right);
        if (k == 0)
            return;
        if (--k == 0)
            res = root.val;
        myKthLargest(root.left);
    }
}

55-I二叉树的深度

//public int maxDepth(TreeNode root) {
//    return myMaxDepth(root, 1);
//}
//private int myMaxDepth(TreeNode root, int depth){
//    if (root == null)
//        return depth - 1;
//    return Math.max(myMaxDepth(root.left, depth + 1), myMaxDepth(root.right, depth + 1));
//}

// 层序遍历
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    List<TreeNode> queue = new LinkedList<>() {{
        add(root);
    }}, tmp;
    int res = 0;
    while (!queue.isEmpty()) {
        tmp = new LinkedList<>();
        for (TreeNode node : queue) {
            if (node.left != null) tmp.add(node.left);
            if (node.right != null) tmp.add(node.right);
        }
        queue = tmp;
        res++;
    }
    return res;
}

56-I数组中数字出现的次数 I

这tm才是位运算。。。

public int[] singleNumbers(int[] nums) {
    int ret = 0;
    for (int n : nums) {
        ret ^= n;
    }
    int div = 1;
    while ((div & ret) == 0) {
        div <<= 1;
    }
    int a = 0, b = 0;
    for (int n : nums) {
        if ((div & n) != 0) {
            a ^= n;
        } else {
            b ^= n;
        }
    }
    return new int[]{a, b};
}

56-II数组中数字出现的次数 II

public int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = ones ^ num & ~twos;
        twos = twos ^ num & ~ones;
    }
    return ones;
}

57 和为s的两个数字

傻了，我就直接遍历 + 二分了，淦

优解：对撞双指针( 排序数组，可先考虑双指针 )

题解

class Solution {
    //public int[] twoSum(int[] nums, int target) {
    //    int length = nums.length;
    //    for (int i = 0; i < length; i++) {
    //        int now = nums[i];
    //        int next = target - now;
    //        if (next < now)
    //            continue;
    //        int next1 = searchNext(nums, i + 1, length - 1, next);
    //        if (next1 != -1)
    //            return new int[]{now, next1};
    //    }
    //
    //    return new int[0];
    //}
    //private int searchNext(int[] nums, int start, int end, int target){
    //    if (nums[start] > target)
    //        return -1;
    //    while (start <= end){
    //        int mid = (start + end) / 2;
    //        if (nums[mid] == target)
    //            return nums[mid];
    //        else if (nums[mid] > target){
    //            end = mid - 1;
    //        }else {
    //            start = mid + 1;
    //        }
    //    }
    //    return -1;
    //}

    // 对撞双指针
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int s = nums[i] + nums[j];
            if (s < target)
                i++;
            else if (s > target)
                j--;
            else
                return new int[]{nums[i], nums[j]};
        }
        return new int[0];
    }
}

57-II 和为s的连续正数序列

还是双指针，但不是对撞了

public int[][] findContinuousSequence(int target) {
    int start = 1, end = 2;
    LinkedList<int[]> res = new LinkedList<>();

    while (start < end){
        int sum = (start + end) * (end - start + 1) / 2;
        if (sum == target){
            int[] sub = new int[end - start + 1];
            for (int i = 0; i < (end - start + 1); i++){
                sub[i] = start + i;
            }
            res.add(sub);
            start++;
        }else if (sum < target){
            end++;
        }else {
            start++;
        }
    }
    return res.toArray(new int[res.size()][]);
}