“This is the 17th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

takeaway

Fat friends in order to better help new students adapt to the algorithm and questions, recently we began a special assault step by step. We’re going to start with one of the most frustrating types of algorithms, dynamic programming and we’re going to do a 21-day incubation program. What are you waiting for? Come and join us for 21 days of dynamic programming challenge!!

21 Days Dynamic Planning Introduction

Given the strings s and t, determine whether S is a subsequence of t.

A subsequence of strings is a new string formed by deleting some (or none) characters from the original string without changing the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not).

Advanced:

If S has a lot of inputs, it’s called S1, S2… Sk where k >= 1 billion, you need to check in order to see if they are subsequences of T. How would you change the code in this case?

The sample1: Enter: s ="abc", t = "ahbgdc"Output:true
Copy the code

The sample2: Enter: s ="axc", t = "ahbgdc"Output:false
Copy the code

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();

        int[][] f = new int[m + 1] [26];
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j]; }}int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s.charAt(i) - 'a'] == m) {
                return false;
            }
            add = f[add][s.charAt(i) - 'a'] + 1;
        }
        return true; }}Copy the code

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.

A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none).

For example, “ace” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”. A common subsequence of two strings is a subsequence that is shared by both strings.

The sample1: Enter text1 ="abcde", text2 = "ace"Output:3Explanation: The longest common subsequence is"ace"And its length is zero3 。
Copy the code

The sample2: Enter text1 ="abc", text2 = "abc"Output:3Explanation: The longest common subsequence is"abc"And its length is zero3 。
Copy the code

The sample3: Enter text1 ="abc", text2 = "def"Output:0Explanation: Two strings have no common subsequence, return0 。
Copy the code

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); }}}returndp[m][n]; }}Copy the code

The interview questions

So we’re going to continue with binary trees: today we’re going to look at a complete binary tree, and we’re going to review what a complete binary tree is. In order to enhance your memory ability, we will compare the memory of complete binary tree and full binary tree:

So in a nutshell:

Complete binary tree: Let the depth of the binary tree be H, except for the h layer, the number of nodes of all other layers (1-H-1) reaches the maximum, and all nodes of the H layer are continuously concentrated on the left

Full binary tree: A full binary tree with depth K and 2^ K-1 nodes is called a full binary tree

package tree;

import java.util.LinkedList;
import java.util.Queue;

public class completeTree {
	// Check whether it is a complete binary tree
	public boolean isCompleteTree(node root) {
		if(root==null)return false;
		Queue<node> queue=new LinkedList<node>();
		queue.add(root);
		boolean NoChild=false,result=true;
		while(! queue.isEmpty()) { node current=queue.remove();if(NoChild) {
				if(current.left! =null||current.right! =null) {
					result=false;
					break; }}else {
				if(current.left! =null&&current.right! =null) {
					queue.add(current.left);
					NoChild=true;
					
				}else if(current.left! =null&&current.right==null) {
					queue.add(current.left);
					NoChild=true;
					
				}else if(current.left==null&&current.right! =null) {
					result=false;
					break;
				}else {
					NoChild=true; }}}returnresult; }}Copy the code