输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

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

限制：

0 <= 链表长度 <= 10000

递归

class Solution {
    int[] arr;
    public int[] reversePrint(ListNode head) {
        recursion(head,0);
        return arr;
    }

    private void recursion(ListNode node, int n) {
        if (node==null) {
            arr = new int[n];
            return;
        }
        recursion(node.next,n+1);
        arr[arr.length-n-1] = node.val;
    }
}

给你一个产品数组 products 和一个字符串 searchWord ，products  数组中每个产品都是一个字符串。

请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。

请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

示例 1：

输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]

示例 2：

输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3：

输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4：

输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]

提示：

• 1 <= products.length <= 1000
• 1 <= Σ products[i].length <= 2 * 10^4
• products[i] 中所有的字符都是小写英文字母。
• 1 <= searchWord.length <= 1000
• searchWord 中所有字符都是小写英文字母。

字典树基本模板基本应用

字典树基本模板先写出来，然后稍微改下就可以了

1. 对String[] products遍历 构建字典树
2. Node节点上保存对应的字符串，遍历到的时候直接把字符串塞过来，只保留3个，且按照字典序排序，这里借用到TreeSet结构的特性
3. search的时候没遍历到一个节点就把对应Node上的字符串存下来
4. 最终返回

class Solution {
    List<List<String>> res;
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie trie = new Trie();
        for (String product : products) {
            trie.insert(product);
        }
        return trie.search(searchWord);
    }

    class Trie{

        Node root;

        public Trie(){
            root = new Node();
        }

        public void insert(String word){
            int idx = -1;
            Node cur = root;
            while (++idx < word.length()){
                int i = word.charAt(idx) - 'a';
                if (cur.children[i] == null){
                    cur.children[i] = new Node();
                }
                cur = cur.children[i];
                cur.addWord(word);
            }
            cur.flag = true;
        }

        public List<List<String>> search(String word){
            List<List<String>> res = new ArrayList<>();
            int idx = -1;
            Node cur = root;
            while (++idx < word.length()){
                List<String> list = new ArrayList<>();
                int i = word.charAt(idx)-'a';
                if (cur!=null){
                    cur = cur.children[i];
                    list = cur==null?new ArrayList<>():new ArrayList<>(cur.treeSet);
                }
                res.add(list);
            }
            return res;
        }

        class Node{
            boolean flag;
            Node[] children;
            TreeSet<String> treeSet;

            public Node(){
                flag = false;
                children = new Node[26];
                treeSet = new TreeSet<>();
            }

            public void addWord(String word){
                treeSet.add(word);
                if (treeSet.size()>3){
                    treeSet.pollLast();
                }
            }
        }
    }
}

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]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

字典树基本模板操作

class Trie {

    Node root = new Node();

    public Trie() {

    }
    
    public void insert(String word) {
        int idx = -1;
        Node cur = root;
        while (++idx < word.length()){
            if (cur.children[word.charAt(idx)-'a'] == null){
                cur.children[word.charAt(idx)-'a'] = new Node();
            }
            cur = cur.children[word.charAt(idx)-'a'];
        }
        cur.flag = true;
    }
    
    public boolean search(String word) {
        int idx = -1;
        Node cur = root;
        while (++idx < word.length()){
            if (cur.children[word.charAt(idx)-'a'] != null){
                cur = cur.children[word.charAt(idx)-'a'];
            }else{
                return false;
            }
        }
        return cur.flag;
    }
    
    public boolean startsWith(String prefix) {
        int idx = -1;
        Node cur = root;
        while (++idx < prefix.length()){
            if (cur.children[prefix.charAt(idx)-'a'] != null){
                cur = cur.children[prefix.charAt(idx)-'a'];
            }else{
                return false;
            }
        }
        return true;
    }


    class Node{
        boolean flag = false;
        Node[] children = new Node[26];
        public Node(){}
    }
}

给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。

一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。

整个树 的坡度就是其所有节点的坡度之和。

示例 1：

输入：root = [1,2,3]
输出：1
解释：
节点 2 的坡度：|0-0| = 0（没有子节点）
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
坡度总和：0 + 0 + 1 = 1

示例 2：

输入：root = [4,2,9,3,5,null,7]
输出：15
解释：
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 5 的坡度：|0-0| = 0（没有子节点）
节点 7 的坡度：|0-0| = 0（没有子节点）
节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）
节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）
节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）
坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15

示例 3：

输入：root = [21,7,14,1,1,2,2,3,3]
输出：9

提示：

• 树中节点数目的范围在 [0, 104] 内
• -1000 <= Node.val <= 1000

深搜套模板嘞

就原来的基础模板里夹两个东西

1. dfs方法返回 当前节点下所有节点的值的和 = 当前节点的值 + 左子树的和 + 右子树的和
2. dfs过程中 累加一个sum值，等于左右子树与右子树节点和的 差值绝对值

class Solution {
    int sum = 0;

    public int findTilt(TreeNode root) {
        if (null == root){
            return 0;
        }
        dfs(root);
        return sum;

    }

    public int dfs(TreeNode node){
        if (null == node){
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        sum += left > right? left - right : right - left;
        return node.val + left + right;
    }
}

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。  

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例 1：

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

示例 2：

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

提示：

• n == numbers.length
• 1 <= n <= 5000
• -5000 <= numbers[i] <= 5000
• numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

java 二分

public int minArray(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        while ( l < r){
            int mid = l + ( (r-l) >> 1 );
            if (nums[mid] < nums[r]){
                r = mid;
            }else if (nums[mid] > nums[r]){
                l = mid+1;
            }else{
                r--;
            }


        }

        return nums[l];

    }

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

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

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/

动态规划，简单理解DP数组的意义和转移方程来源

class Solution {

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = nums[0];
        dp[0] = nums[0];
        int idx = 0;
        while (++idx < nums.length){
            dp[idx] = Math.max(nums[idx],dp[idx-1]+nums[idx]);
            max = Math.max(max,dp[idx]);
        }
        return max;
    }
}

直接看代码说话，动态规划需要明白的最重要的就是你的dp[]数组表达的意义是什么？

这里我们的int[] dp 需要表达的意义是

以原 int[] nums 数组中的每一位结尾的子序列能组成的最大子序列合

这很重要，当求dp[i]的时候，我们有两种情况

1. 和前一位置的数字结尾的子序列组成新的子序列
2. 单独自己为一个序列

这两个来源对应的值分别是 dp[i-1] 和 nums[i]

要求子序列合最大，那么我们就可以得到以下转移方程

dp[i] = MAX ( nums[i] , dp[i-1]+nums[i] )

或者也可以这样

dp[i] = MAX ( 0 , dp[i-1] ) + nums[i]

都一样的，代码就是上面那样了，当然也可以再简化的用一个变量代替下dp[]数组来操作

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int pre = nums[0];
        int idx = 0;
        while (++idx < nums.length){
            pre = Math.max(0 ,pre) + nums[idx];
            max = Math.max(max,pre);
        }
        return max;
    }
}

emmm，测试用例的问题么？单个变量的内存消耗甚至比数组大

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

• 0 < grid.length <= 200
• 0 < grid[0].length <= 200

动态规划简单题，再压缩到一维dp[]数组

1. 当前格子可以由上面一格 或者 左边一格 过来，取较大的一个
2. 再加上当前格子的价值，就是当前格子能得到的最大价值
3. 转移方程
   dp[i][j] = MAX( dp[i][j-1], dp[i-1][j]) + grid[i][j]

在直接压缩到一维dp[]数组如下

class Solution {
    public int maxValue(int[][] grid) {
        int[] dp = new int[grid[0].length];
        dp[0] = grid[0][0];
        for (int i = 1; i < grid[0].length; i++) {
            dp[i] = dp[i-1] + grid[0][i];
        }
        int idx = 0;
        while (++idx < grid.length){
            dp[0] += grid[idx][0];
            for (int i = 1; i < grid[0].length; i++) {
                dp[i] = Math.max(dp[i-1],dp[i]) + grid[idx][i];
            }
        }
        return dp[dp.length-1];
    }
}