LeetCode题解——随机刷题(二)

素颜马尾好姑娘i 2022-12-07 01:53 205阅读 0赞

### 文章目录 ###

*   *  114. 二叉树展开为链表
     *   *  寻找前驱节点
     *  221. 最大正方形
     *   *  动态规划
     *  301. 删除无效的括号
     *   *  回溯算法
     *  312. 戳气球
     *   *  动态规划
     *  399. 除法求值
     *   *  并查集
         *   *  推荐阅读

## 114. 二叉树展开为链表 ##

[114. 二叉树展开为链表][114.]

给定一个二叉树，原地将它展开为一个单链表。
    
     
    
    例如，给定二叉树
    
        1
       / \
      2   5
     / \   \
    3   4   6
    将其展开为：
    
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

### 寻找前驱节点 ###

/**
     * 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 void flatten(TreeNode root) {
        
            TreeNode cur = root;
            while (cur != null) {
        
                if (cur.left != null) {
        
                    TreeNode next = cur.left;
                    TreeNode preNode = next;
                    while (preNode.right != null) {
        
                        preNode = preNode.right;
                    }
                    preNode.right = cur.right;
                    cur.left = null;
                    cur.right = next;
                }
                cur = cur.right;
            }       
        }
    }

## 221. 最大正方形 ##

[221. 最大正方形][221.]

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

### 动态规划 ###

![72956aeb14afa22749558daad7677fde.png][]

class Solution {
        
        public int maximalSquare(char[][] matrix) {
        
            int maxSide = 0;
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        
                return 0;
            }
            int rows = matrix.length, columns = matrix[0].length;
            int[][] dp = new int[rows][columns];
            for (int i = 0; i < rows; i++) {
        
                for (int j = 0; j < columns; j++) {
        
                    if (matrix[i][j] == '1') {
        
                        if (i == 0 || j == 0) {
        
                            dp[i][j] = 1;
                        } else {
        
                            dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                        }
                        maxSide = Math.max(maxSide, dp[i][j]);
                    }
                }
            }
            return maxSide * maxSide;
        }
    }

## 301. 删除无效的括号 ##

[301. 删除无效的括号][301.]

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
    
    说明: 输入可能包含了除 ( 和 ) 以外的字符。
    
    示例 1:
    
    输入: "()())()"
    输出: ["()()()", "(())()"]
    示例 2:
    
    输入: "(a)())()"
    输出: ["(a)()()", "(a())()"]
    示例 3:
    
    输入: ")("
    输出: [""]

### 回溯算法 ###

class Solution {
        
        Set<String> set = new HashSet<>();
        int maxLen = 0;
        public List<String> removeInvalidParentheses(String s) {
        
            int rmLeft = 0, rmRight = 0;
            // 1、对于括号，有选和不选两种情况；对于字母，必须选
            // 2、用计数器维护字符串状态，"("则加一，")"则减一
            // 3、set去重
            // 4、提前计算应当删除的左括号或者右括号的数量，用于剪枝
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == '(') {
        
                    rmLeft++;
                } else if (s.charAt(i) == ')'){
        
                    if (rmLeft > 0) {
        
                        rmLeft--;
                    } else {
        
                        rmRight++;
                    }
                }
            }
            helper(s, 0, 0, new StringBuilder(), rmLeft, rmRight);
            return new ArrayList<>(set);
        }
        private void helper(String s, int idx, int count, StringBuilder path, int rmLeft, int rmRight) {
        
            if (count < 0 || rmLeft < 0 || rmRight < 0) {
        
                return;
            }
            if (idx == s.length()) {
        
                if (count == 0 && rmLeft == 0 && rmRight == 0) {
        
                    if (path.length() >= maxLen) {
        
                        maxLen = path.length();
                        set.add(path.toString());
                    }
                }
                return;
            }
            // 添加当前字符到path中
            char c = s.charAt(idx);
            path.append(c);
            if (c == '(') {
        
                helper(s, idx + 1, count + 1, path, rmLeft, rmRight);
            } else if (c == ')') {
        
                helper(s, idx + 1, count - 1, path, rmLeft, rmRight);
            } else {
        
                helper(s, idx + 1, count, path, rmLeft, rmRight);
            }
            // 不添加当前字符到path中
            path.deleteCharAt(path.length() - 1);
            if (c == '(') {
        
                helper(s, idx + 1, count, path, rmLeft - 1, rmRight);
            } else if (c == ')') {
        
                helper(s, idx + 1, count, path, rmLeft, rmRight - 1);
            }
        }
    }

## 312. 戳气球 ##

[312. 戳气球][312.]

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
    
    现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
    
    求所能获得硬币的最大数量。
    
    说明:
    
    你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
    0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
    示例:
    
    输入: [3,1,5,8]
    输出: 167 
    解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
         coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

### 动态规划 ###

![442783c133fe3d41dc56770e7c0f41cb.png][]

class Solution {
        
        public int maxCoins(int[] nums) {
        
            int n = nums.length;
            int[][] res = new int[n + 2][n + 2];
            int[] val = new int[n + 2];
            val[0] = val[n + 1] = 1;
            for (int i = 1; i <= n; i++) {
        
                val[i] = nums[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
        
                for (int j = i + 1; j <= n + 1; j++) {
        
                    for (int k = i + 1; k < j; k++) {
        
                        int sum = val[i] * val[k] * val[j];
                        sum += res[i][k] + res[k][j];
                        res[i][j] = Math.max(res[i][j], sum);
                    }
                }
            }
            return res[0][n + 1];
        }
    }

## 399. 除法求值 ##

[399. 除法求值][399.]

给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
    
    示例 :
    给定 a / b = 2.0, b / c = 3.0
    问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
    返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]
    
    输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。
    
    基于上述例子，输入如下：
    
    equations(方程式) = [ ["a", "b"], ["b", "c"] ],
    values(方程式结果) = [2.0, 3.0],
    queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
    输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

### 并查集 ###

详解见[leetcode][]

class Solution {
        
        
        private Map<String, String> parents = new HashMap<>();
        private Map<String, Double> values = new HashMap<>();
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        
            for (int i = 0; i < equations.size(); i++) {
        
                union(equations.get(i).get(0), equations.get(i).get(1), values[i]);
            }
            double[] result = new double[queries.size()];
            for (int i = 0; i < queries.size(); i++) {
        
                String e = queries.get(i).get(0);
                String q = queries.get(i).get(1);
                if (!(parents.containsKey(e) && parents.containsKey(q))) {
        
                    result[i] = -1;
                    continue;
                }
                if (e.equals(q)) {
        
                    result[i] = 1;
                    continue;
                }
                String r1 = root(e);
                String r2 = root(q);
                if (!r1.equals(r2)) {
        
                    result[i] = -1;
                    continue;
                }
                result[i] = pm(q) / pm(e);
            }
            return result;
        }
        private void union(String parent, String child, double value) {
        
            add(parent);
            add(child);
            String r1 = root(parent);
            String r2 = root(child);
            if (!r1.equals(r2)) {
        
                parents.put(r2, r1);
                values.put(r2, value * (pm(parent) / pm(child)));
            }
        }
        private void add(String x) {
        
            if (!parents.containsKey(x)) {
        
                parents.put(x, x);
                values.put(x, 1.0);
            }
        }
        private String root(String x) {
        
            while (!parents.get(x).equals(x)) {
        
                x = parents.get(x);
            }
            return x;
        }
        private double pm(String x) {
        
            double v = 1;
            while (!parents.get(x).equals(x)) {
        
                v *= values.get(x);
                x = parents.get(x);
            }
            return v;
        }
        
    }

--------------------

#### 推荐阅读 ####

*  [剑指offer精品题解][offer]
 *  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

**欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。**  
![269c45b435ef227981055f48c43978c2.png][]

[114.]: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
[221.]: https://leetcode-cn.com/problems/maximal-square/
[72956aeb14afa22749558daad7677fde.png]: /images/20221123/2e6023f54e394021b0e23fae83c040f5.png
[301.]: https://leetcode-cn.com/problems/remove-invalid-parentheses/
[312.]: https://leetcode-cn.com/problems/burst-balloons/
[442783c133fe3d41dc56770e7c0f41cb.png]: /images/20221123/d8ad10679eee4ffc8389a021c505a1a3.png
[399.]: https://leetcode-cn.com/problems/evaluate-division/
[leetcode]: https://leetcode-cn.com/problems/evaluate-division/solution/ni-zhen-de-zhi-dao-bing-cha-ji-de-gou-zao-guo-chen/
[offer]: https://mp.weixin.qq.com/s/R5VKVxOYBr6CcGTIrlLQpw
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[269c45b435ef227981055f48c43978c2.png]: /images/20221123/0d6696d114264276b01113b0ab30354b.png