「这是我参与11月更文挑战的第17天,活动详情查看:2021最后一次更文挑战」
导读
肥友们为了更好的去帮助新同学适应算法和面试题,最近我们开始进行专项突击一步一步来。我们先来搞一下让大家最头疼的一类算法题,动态规划我们将进行为时21天的养成计划。还在等什么快来一起肥学进行动态规划21天挑战吧!!
21天动态规划入门
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
进阶:
如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T
的子序列。在这种情况下,你会怎样改变代码?
示例 1:
输入:s = "abc", t = "ahbgdc"
输出:true
复制代码
示例 2:
输入:s = "axc", t = "ahbgdc"
输出:false
复制代码
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" 的子序列。 两个字符串的 公共子序列
是这两个字符串所共同拥有的子序列。
示例 1:
输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 。
复制代码
示例 2:
输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。
复制代码
示例 3:
输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。
复制代码
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个结点的二叉树称为满二叉树
package tree;
import java.util.LinkedList;
import java.util.Queue;
public class completeTree {
//判断是否为完全二叉树
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&¤t.right!=null) {
queue.add(current.left);
NoChild=true;
}else if(current.left!=null&¤t.right==null) {
queue.add(current.left);
NoChild=true;
}else if(current.left==null&¤t.right!=null) {
result=false;
break;
}else {
NoChild=true;
}
}
}
return result;
}
}
复制代码
近期评论