515. 在每个树行中找最大值 / 剑指 Offer II 095. 最长公共子序列

515. 在每个树行中找最大值【中等题】【每日一题】

思路：【BFS】

BFS模板题，注意把root = null的特殊情况排除掉。

代码：

/** * 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> largestValues(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        if (root == null){
    
            return list;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
    
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
    
                TreeNode node = queue.poll();
                max = Math.max(max,node.val);
                if (node.left != null){
    
                    queue.offer(node.left);
                }
                if (node.right != null){
    
                    queue.offer(node.right);
                }
            }
            list.add(max);
        }
        return list;
    }
}

---

剑指 Offer II 095. 最长公共子序列【中等题】

思路：【动态规划】

定义二阶dp数组，dp[i][j]表示text1的前i个字符与text2的前j个字符的最长公共子序列的长度。

边界条件：
i = 0 或 j = 0 时，dp[j][j] = 0

转移方程：
设text1的第i个字符为 c1，text2的第j个字符 c2 （i 和j从1开始）
c1 == c2 时
dp[i][j] = dp[i-1][j-1] + 1;
c2 != c2时
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

代码：

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
    
        //记录text1的长度为m，记录text2的长度为n
        int m = text1.length(),n = text2.length();
        //定义二阶dp数组，dp[i][j] 代表 text1的前i个字符与text2的前j个字符能构成的最长公共子序列的长度
        //边界条件为 i = 0 或 j = 0 时，dp[0][j] = 0 或 dp[i][0] = 0
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
    
            //求出text1的第 i 个字符 c1
            char c1 = text1.charAt(i-1);
            for (int j = 1; j <= n; j++) {
    
                //求出text2的第 j 个字符 c2
                char c2 = text2.charAt(j-1);
                //转移方程
                //如果 c1 == c2 那么 第[i,j]位置的最长公共子序列长度 = 第[i-1][j-1]位置的最长公共子序列长度 + 1(公共字符)
                //即 dp[i][j] = dp[i-1][j-1] + 1
                if (c1 == c2){
    
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
    
                    //如果 c1 != c2 那么 第[i,j]位置的最长公共子序列长度 = 第[i-1,j]位置的最长公共子序列长度 与 第 [i,j-1]位置的最长公共子序列长度 两者的最大值
                    //即 dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        //dp[m][n]即为text1和text2的最长公共子序列长度
        return dp[m][n];
    }
}