合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/?favorite=2cktkvj

要注意链表需要构造一个节点指针来遍历，，，

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 class mergeTwoLists {
    class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode myListHead = new ListNode(0);
            ListNode myList = myListHead;
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    myList.next = list1;
                    myList = myList.next;
                    list1 = list1.next;
                } else {
                    myList.next = list2;
                    myList = myList.next;
                    list2 = list2.next;
                }
            }
            myList.next = list1 == null ? list2 : list1;
            return myListHead.next;
        }
    }
}

爬楼梯

https://leetcode.cn/problems/climbing-stairs/?favorite=2cktkvj

由于总方案数=最后走一步的方案数+最后走两步的方案数。

$f(x)=f(x-1)+f(x-2)$

所以这题就是个求斐波那契数列第n项的值，使用滚动数组。0 0 1 1 2 3 5 8

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
}

二叉树的中序遍历

基础递归，就这还写了半天，重开吧。

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) {
        TreeNode treeNode = root;
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        traversal(list,treeNode);
        return list;
    }

    public void traversal(List<Integer> list, TreeNode treeNode) {
        if (treeNode.left != null) {
            traversal(list, treeNode.left);
        }
        list.add(treeNode.val);
        if (treeNode.right != null) {
            traversal(list, treeNode.right);
        }
    }
}

还可以用栈迭代，，，不会

对称二叉树

不会，，多写多练多看吧，，

需要复习一下有关null的各种知识了，如何比较，空指针异常之类的，，

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return treeSymmetric(root, root);
    }

    public boolean treeSymmetric(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && treeSymmetric(p.left, q.right) && treeSymmetric(p.right, q.left);
    }
}

二叉树的直径

https://leetcode.cn/problems/diameter-of-binary-tree/

递归+DFS

这里的depth求的是每个节点子树的最大深度。

class Solution {
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }

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

合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/

也是递归+DFS

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode treeNode = new TreeNode(root1.val + root2.val);
        treeNode.left = mergeTrees(root1.left, root2.left);
        treeNode.right = mergeTrees(root1.right, root2.right);
        return treeNode;
    }
}

二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

很简单，我都会

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

买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

暴力解法，直接被巨量数据狂暴轰入，宕机了，不行。

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

其实只需要找到最小价格，再用之后每一天的价格减去最小价格，找到最大利润即可。

class Solution1 {
    public int maxProfit1(int[] prices) {
        int maxProfit = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            if (prices[i] - min > maxProfit) {
                maxProfit = prices[i] - min;
            }
        }
        return maxProfit;
    }
}

只出现一次的数字

https://leetcode.cn/problems/single-number/?favorite=2cktkvj

很简单，我都会

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        hashSet.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                hashSet.remove(nums[i]);
            } else {
                hashSet.add(nums[i]);
            }
        }
        Iterator<Integer> iterator = hashSet.iterator();
        return iterator.next();
    }
}