515. find the maximum value / Sword finger offer II 095 in each tree row Longest common subsequence

515. Find the maximum in each tree row 【 Medium question 】【 A daily topic 】

Ideas ：【BFS】

BFS The template questions , Pay attention to the root = null The special circumstances of .

Code ：

/** * 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;
    }
}

---

The finger of the sword Offer II 095. Longest common subsequence 【 Medium question 】

Ideas ：【 Dynamic programming 】

Define second order dp Array ,dp[i][j] Express text1 Before i Characters and text2 Before j The length of the longest common subsequence of characters .

The boundary conditions ：
i = 0 or j = 0 when ,dp[j][j] = 0

Transfer equation ：
set up text1 Of the i The characters are c1,text2 Of the j Characters c2 （i and j from 1 Start ）
c1 == c2 when
dp[i][j] = dp[i-1][j-1] + 1;
c2 != c2 when
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

Code ：

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
    
        // Record text1 The length of is m, Record text2 The length of is n
        int m = text1.length(),n = text2.length();
        // Define second order dp Array ,dp[i][j]  representative  text1 Before i Characters and text2 Before j The length of the longest common subsequence of characters 
        // The boundary condition is  i = 0  or  j = 0  when ,dp[0][j] = 0  or  dp[i][0] = 0
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
    
            // Find out text1 Of the  i  Characters  c1
            char c1 = text1.charAt(i-1);
            for (int j = 1; j <= n; j++) {
    
                // Find out text2 Of the  j  Characters  c2
                char c2 = text2.charAt(j-1);
                // Transfer equation 
                // If  c1 == c2  that   The first [i,j] Length of the longest common subsequence of the position  =  The first [i-1][j-1] Length of the longest common subsequence of the position  + 1( Common characters )
                // namely  dp[i][j] = dp[i-1][j-1] + 1
                if (c1 == c2){
    
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
    
                    // If  c1 != c2  that   The first [i,j] Length of the longest common subsequence of the position  =  The first [i-1,j] Length of the longest common subsequence of the position   And   The first  [i,j-1] Length of the longest common subsequence of the position   The maximum of both 
                    // namely  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] That is to say text1 and text2 The longest common subsequence length of 
        return dp[m][n];
    }
}