衝刺大廠每日演算法&面試題,動態規劃21天——第十九天

語言: CN / TW / HK

highlight: a11y-dark theme: mk-cute


「這是我參與11月更文挑戰的第17天,活動詳情檢視:2021最後一次更文挑戰

導讀

在這裡插入圖片描述

肥友們為了更好的去幫助新同學適應演算法和麵試題,最近我們開始進行專項突擊一步一步來。我們先來搞一下讓大家最頭疼的一類演算法題,動態規劃我們將進行為時21天的養成計劃。還在等什麼快來一起肥學進行動態規劃21天挑戰吧!!

21天動態規劃入門

給定字串 s 和 t ,判斷 s 是否為 t 的子序列。

字串的一個子序列是原始字串刪除一些(也可以不刪除)字元而不改變剩餘字元相對位置形成的新字串。(例如,"ace"是"abcde"的一個子序列,而"aec"不是)。

進階:

如果有大量輸入的 S,稱作 S1, S2, ... , Sk 其中 k >= 10億,你需要依次檢查它們是否為 T 的子序列。在這種情況下,你會怎樣改變程式碼?

```java 示例 1:

輸入:s = "abc", t = "ahbgdc" 輸出:true ```

```java 示例 2:

輸入:s = "axc", t = "ahbgdc" 輸出:false ```

```java 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;
}

}

```

給定兩個字串 text1 和 text2,返回這兩個字串的最長 公共子序列 的長度。如果不存在 公共子序列 ,返回 0 。

一個字串的 子序列 是指這樣一個新的字串:它是由原字串在不改變字元的相對順序的情況下刪除某些字元(也可以不刪除任何字元)後組成的新字串。

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。 兩個字串的 公共子序列 是這兩個字串所共同擁有的子序列。

```java 示例 1:

輸入:text1 = "abcde", text2 = "ace" 輸出:3
解釋:最長公共子序列是 "ace" ,它的長度為 3 。 ```

```java 示例 2:

輸入:text1 = "abc", text2 = "abc" 輸出:3 解釋:最長公共子序列是 "abc" ,它的長度為 3 。 ```

```java 示例 3:

輸入:text1 = "abc", text2 = "def" 輸出:0 解釋:兩個字串沒有公共子序列,返回 0 。 ```

在這裡插入圖片描述

```java 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]); } } } return dp[m][n]; } }

```

面試題

繼續二叉樹的內容: 今天來講怎麼判斷是否為完全二叉樹,首先回顧一下什麼叫完全二叉樹。為了增強大家的記憶能力,我們將完全二叉樹和滿二叉樹對比記憶: 在這裡插入圖片描述

在這裡插入圖片描述 所以簡單來說:

完全二叉樹:設二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數, 第 h 層所有的結點都連續集中在最左邊

滿二叉樹:深度為k且有2^k-1個結點的二叉樹稱為滿二叉樹

```java package tree;

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

public class completeTree { //判斷是否為完全二叉樹 public boolean isCompleteTree(node root) { if(root==null)return false; Queue queue=new LinkedList(); 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;
            }
        }
    }
    return result;
}

}

```