百题通关(中)[废弃]

73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

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

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean[] row = new boolean[m];
    boolean[] col = new boolean[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                row[i] = col[j] = true;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

// 两次二分查找
public boolean searchMatrix(int[][] matrix, int target) {
    int l = 0;
    int r = matrix.length - 1;
    int res = -1;
    while (l <= r) {
        int m = l + ((r - l) >> 1);
        if (matrix[m][0] <= target) {
            res = m;
            l = m + 1;
        } else if (matrix[m][0] > target) {
            r = m - 1;
        }
    }
    if(res < 0){
        return false;
    }
    l = 0;
    r = matrix[0].length - 1;
    while (l <= r) {
        int m = l + ((r - l) >> 1);
        if (matrix[res][m] == target) {
            return true;
        } else if (matrix[res][m] > target) {
            r = m - 1;
        } else if (matrix[res][m] < target) {
            l = m + 1;
        }
    }
    return false;
}

76. 最小覆盖子串

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

注意：

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

示例 1：

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

public String minWindow(String s, String t) {
    int[] count = new int[256];
    int[] target = count(t);

    int l = 0;
    int r = -1;

    int maxL = 0;
    int maxR = Integer.MAX_VALUE;

    while (l < s.length()) {
        if (has(count, target)) {
            if (r - l < maxR - maxL) {
                // 如果当前已经可以覆盖，那就说明窗口可以缩小
                maxR = r;
                maxL = l;
            }
            count[s.charAt(l++)]--;
        } else {
            if (r == s.length() - 1) {
                // 如果窗口已经移动到边儿了
                break;
            }
            // 说明窗口还不能覆盖，窗口得扩大
            count[s.charAt(++r)]++;
        }
    }
    return maxR == Integer.MAX_VALUE ? "" : s.substring(maxL, maxR + 1);
}

// 对于英文字符和标点符号的，可以创建一个int[256]，因为ASCII码256个字符
// 将t串中的字符记录
int[] count(String t) {
    int[] counts = new int[256];
    final char[] chars = t.toCharArray();
    for (int c : chars) {
        counts[c]++;
    }
    return counts;
}

// 根据上面的函数设置下面的函数，因为我们要求的事最小覆盖子串，所以结果是比t串的字符大于等于的关系
boolean has(int[] s, int[] t) {
    for (int i = 0; i < 256; i++) {
        if (s[i] < t[i]) { // 根据上面的注释，如果这个条件满足说明当前串还不能覆盖子串
            return false;
        }
    }
    return true;
}

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

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

List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();

public List<List<Integer>> combine(int n, int k) {
    combineHelper(n, k, 1);
    return result;
}

/**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     *
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
private void combineHelper(int n, int k, int startIndex) {
    //终止条件
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    // i <= n - (k - path.size()) + 1 剪纸操作
    // 表示当前已经选择了path.size()个元素, 还剩下(k - path.size())个元素要选
    // 那么i至多从n - (k - path.size()) + 1开始,在他之前是一定可以的,在他之后一定不可以
    // 举个例子,n = 4, k = 4, 现在一个元素都没选, 那么 i <= 4 - (4 - 0) + 1 = 1,
    // 也就是说i至多从1开始选, 很好理解,因为总共四个元素,从第二个开始选肯定不够4个,之后的更是这样
    for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        combineHelper(n, k, i + 1);
        path.removeLast();
    }
}

78. 子集

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

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

示例 1：

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

/**
 * 回溯算法
 * 子集这道题强调的是,树形结构中,每一层上节点都是我们想要的结果
 * 前面的题目是,叶子节点才是收获节点的时候
 * 所以做回溯题还是要先画好树形结构
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> line = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        process(nums, 0);
        return res;
    }

    private void process(int[] nums, int startIndex) {
        // 从最上面说的,每进入一次递归,都是一次收获结果的时候
        res.add(new ArrayList<>(line));
        if (startIndex >= nums.length) {
            // 说明所有数字都选过了
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            line.add(nums[i]);
            process(nums, i + 1);
            line.remove(line.size() - 1);
        }
    }
}

79. 单词搜索

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

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

示例 1：

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

/**
 * 遍历整个数组, 每次都以当前位置出发,想四周扩散的去找,知道找到了满足条件的时候就返回true
 */
public boolean exist(char[][] board, String word) {
    char[] wordChar = word.toCharArray();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            // 对于每一个元素都要试一下process,从word的起点开始扫描(index初始为0)
            final boolean process = process(board, wordChar, i, j, 0);
            if(process){
                return true;
            }
        }
    }
    return false;
}

	/**
     * 检查当前是否已经存在单词
     * @param board 元数据
     * @param word 单词
     * @param i 元数据横坐标
     * @param j 元数据纵坐标
     * @param index 当前单词位置
     * @return 是否已经存在单词
     */
public boolean process(char[][] board, char[] word, int i, int j, int index){
    if (index == word.length) {
        // 当前已经找到了word
        return true;
    }
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        // 非法下标
        return false;
    }
    if (board[i][j] == word[index]) {
        board[i][j] = (char)(-board[i][j]);
        // 说明当前遍历到的是index处的字符,即可上下左右的去寻找"没有用过的且匹配的字符"
        boolean p1 = process(board, word, i - 1, j, index + 1);
        boolean p2 = process(board, word, i + 1, j, index + 1);
        boolean p3 = process(board, word, i, j - 1, index + 1);
        boolean p4 = process(board, word, i, j + 1, index + 1);
        // 回溯
        board[i][j] = (char)(-board[i][j]);
        return p1 || p2 || p3 || p4;
    }else{
        return false;
    }
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

二叉树的遍历题目, 强烈推荐面试的时候用 迭代法实现

其实本质就是递归, 于是我们用 栈 来模拟递归过程

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    Deque<TreeNode> stack = new LinkedList<>();
    while (root != null || !stack.isEmpty()) {
        // 左根右,左边全部放进去了
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        //  取出栈顶,根
        root = stack.pop();
        // 放入右节点的值
        res.add(root.val);
        root = root.right;
    }
    return res;
}

递归方式

void dfs(List<Integer> res, TreeNode root) {
    if(root==null) {
        return;
    }
    //按照 左-打印-右的方式遍历
    dfs(res,root.left);
    res.add(root.val);
    dfs(res,root.right);
}

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

解题关键: 如果满足二叉搜索树, 则中序遍历的结果就是升序的

private long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    if (!isValidBST(root.left)) {
        return false;
    }
    // 不满足二叉搜索树条件
    // prev其实就是左节点,左节点比当前节点还要小,那肯定不是二叉搜索树
    if (root.val <= prev) {
        return false;
    }
    prev = root.val;
    return isValidBST(root.right);
}

101. 对称二叉树

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

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

二叉树的题目一定要考虑遍历的方式, 这里也能体会 递归中的return 的意义, 在这里就是由深层逐级向上传递, 也正是后序遍历的顺序才能做到

// 递归真是太牛逼啦！
// 其实是后序遍历,而且只能是后序遍历,
// 因为我们要从底部逐层向上的告知顶部节点是否是对称的,直到到达根节点也是true
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return false;
        }
        return isSymmetric(root.left, root.right);
    }

    public boolean isSymmetric(TreeNode l, TreeNode r) {
        if (l == null && r == null) {
            return true;
        }
        if (l == null || r == null) {
            return false;
        }
        if (l.val != r.val) {
            return false;
        }
        // 这里的return,其实就是后序遍历,
        // isSymmetric(l.left, r.right) 左
        // isSymmetric(l.right, r.left) 右
        // 两者取与运算                   中
        return isSymmetric(l.left, r.right) && isSymmetric(l.right, r.left);
    }
}

102. 二叉树的层序遍历

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

示例 1：

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

public List<List<Integer>> resList = new ArrayList<List<Integer>>();

public List<List<Integer>> levelOrder(TreeNode root) {
    checkFun(root);
    return resList;
}

//BFS--迭代方式--借助队列
public void checkFun(TreeNode node) {
    if (node == null) return;
    Queue<TreeNode> que = new LinkedList<>();
    que.offer(node);

    while (!que.isEmpty()) {
        List<Integer> itemList = new ArrayList<>();
        int len = que.size();

        while (len > 0) {
            TreeNode tmpNode = que.poll();
            itemList.add(tmpNode.val);

            if (tmpNode.left != null) que.offer(tmpNode.left);
            if (tmpNode.right != null) que.offer(tmpNode.right);
            len--;
        }
        resList.add(itemList);
    }
}

106. 从中序与后序遍历序列构建二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

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

/**
 * 中序数组至关重要,因为它能确定中间跟在哪儿
 * 然后利用前序(第一个是根节点)或者后序(最后一个是根节点)的特性
 * 就可以对中序数组拆分,拆成左中序和右中序
 * 进而用左中序的长度和右中序的长度去拆分前序或者后序数组
 * 这样就可以递归了
 */
class Solution {
    // 方便根据数值查找位置
    Map<Integer, Integer> map;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        // 用map保存中序序列的数值对应位置
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 前闭后开
        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        // 不满足左闭右开，说明没有元素，返回空树
        if (inBegin >= inEnd || postBegin >= postEnd) {
            return null;
        }
        // 找到后序遍历的最后一个元素在中序遍历中的位置
        int rootIndex = map.get(postorder[postEnd - 1]);
        // 构造结点
        TreeNode root = new TreeNode(inorder[rootIndex]);
        // 保存中序左子树个数，用来确定后序数列的个数
        int lenOfLeft = rootIndex - inBegin;
        root.left = findNode(inorder, inBegin, rootIndex,
                             postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                              postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

• 

/**
 * 主要是考虑二分的思路
 * 把中间节点作为root
 * 然后分别设置左右子树
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return process(nums, 0, nums.length - 1);
    }

    public TreeNode process(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = process(nums, l, mid - 1);
        root.right = process(nums, mid + 1, r);
        return root;
    }
}

110. 平衡二叉树

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

示例 1：

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

	/**
     * 递归法
     * 整体还是后序遍历, -1 表示字数不是平衡二叉树,这样就可以逐层向上传递
     * 如果是平衡二叉树,我们就返回子树的高度,因为上一层递归还需要这一层子树的高度去比较得到结果
     * 递归的精髓在于返回,逐层返回执行结果
     */
public boolean isBalanced(TreeNode root) {
    return getHeight(root) != -1;
}

private int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 左
    int leftHeight = getHeight(root.left);
    if (leftHeight == -1) {
        return -1;
    }
    // 右
    int rightHeight = getHeight(root.right);
    if (rightHeight == -1) {
        return -1;
    }
    // 中
    // 左右子树高度差大于1，return -1表示已经不是平衡树了
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

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

	/**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     * 注意都是对于从根节点到叶子节点
     * 所以如果有根节点左节点或者右节点是空的,就应该去找非空节点那边,因为这不满足条件
     * 也是一个后序遍历,从低向上
     */
public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = minDepth(root.left);
    int rightDepth = minDepth(root.right);
    if (root.left == null) {
        return rightDepth + 1;
    }
    if (root.right == null) {
        return leftDepth + 1;
    }
    // 左右结点都不为null
    return Math.min(leftDepth, rightDepth) + 1;
}

121. 买卖股票的最佳时机

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

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

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

示例 1：

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

波谷和波峰, 最低的波谷 和 最高的波峰, 且波谷出现的位置要靠前

public int maxProfit(int prices[]) {
    // 在寻找股价最低的同时,又计算每一天的利润是多少,获得一个最大的利润
    int minprice = Integer.MAX_VALUE;
    int maxprofit = 0;
    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < minprice) {
            minprice = prices[i];
        } else if (prices[i] - minprice > maxprofit) {
            maxprofit = prices[i] - minprice;
        }
    }
    return maxprofit;
}

122. 买卖股票的最佳时机2

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7

把所有的📈上升都买断, 这样就能赚到所有的增值

	/**
     * 贪心:
     * 因为可以一直买卖
     * 把所有上升期都赚了,就是最大利润
     */
public int maxProfit(int[] prices) {
    int pre = prices[0];
    int res = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] - pre > 0) {
            res += (prices[i] - pre);
        }
        pre = prices[i];
    }
    return res;
}