2021-02-10：如何求出两个字符串的最大公共子串长度？ 福哥答案2021-02-10： 自然智慧即可。1.动态规划。时间复杂度是O(MN),空间复杂度是O(MN)。有代码。dp[i][j]只依赖左上边。①.如果str1[i]==str2[j]，dp[i][j]=【左上边】+1。②.如果str1[i]==str2[j]，dp[i][j]=0。2.dp压缩的动态规划。时间复杂度是O(M*N),空间复杂度是O(1)。有代码。3.后缀数组。时间复杂度是O(M+N)。无代码。 代码用golang编写，代码如下： package main import "fmt" func ma...

2021-02-10：如何求出两个字符串的最大公共子串长度？

2021-02-10：如何求出两个字符串的最大公共子串长度？

2021-02-09：如何删除一个链表的倒数第n个元素？福哥答案2021-02-09： 1.创建虚拟头元素，虚拟头元素的Next指针指向头元素。2.根据快慢指针求倒数第n+1个元素，假设这个元素是slow。3.设置元素slow的Next指针。slow.Next=slow.Next.Next。4.返回虚拟头元素的Next指针。 代码用golang编写，代码如下： package main import "fmt" type ListNode struct { Val int Next *ListNode } func main() { head := &ListNod...

2021-02-09：如何删除一个链表的倒数第n个元素？

2021-02-09：如何删除一个链表的倒数第n个元素？

2021-02-08：给定一个字符串str，请问这个字符串的最长回文子序列长度是多少？ 福哥答案2021-02-08： 自然智慧即可。1.原序列和反序列求公共子序列。无代码。2.递归。有代码。3.动态规划。有代码。根据动态规划表，dp[i][j]取【左边】，【下边】，【左下边】或者【左下边+2】）的最大值。【左下边】还是【左下边+2】？i==j,取【左下边+2】；i!=j，取【左下边】。 代码用golang编写，代码如下： package main import "fmt" func main() { ret := longestPalindromeSubseq(&quot...

2021-02-08：给定一个字符串str，请问这个字符串的最长回文子序列长度是多少？

2021-02-08：给定一个字符串str，请问这个字符串的最长回文子序列长度是多少？

2021-02-07：给定两棵二叉树的头节点head1和head2，如何判断head1中是否有某个子树的结构和head2完全一样？ 福哥答案2021-02-07： 对head1和head2序列化为str1和str2。然后用kmp算法去判断str2是否是str1的子串。如果是，head2是子树；如果不是，head2不是子树。 代码用golang编写，代码如下： package main import "fmt" func main() { root := &TreeNode{} root.Val = 1 root.Left = &TreeNode{} root...

2021-02-07：给定两棵二叉树的头节点head1和head2，如何判断head1中是否有某个子树的结构和head2完全一样？

2021-02-07：给定两棵二叉树的头节点head1和head2，如何判断head1中是否有某个子树的结构和head2完全一样？

福哥答案2021-02-06： 1.动态规划。无代码，见图。2.中心扩展法。无代码。3.Manacher算法。有代码，见图。1）理解回文半径数组。2）理解所有中心的回文最右边界R，和取得R时的中心点C。3）理解 L…(i`)…C…(i)…R 的结构，以及根据i’回文长度进行的状况划分。4）每一种情况划分，都可以加速求解i回文半径的过程。 代码用的是第3种方法，用golang编写，代码如下： package main import "fmt" func main() { fmt.Println("yyabcbaxxx的最长回文子串长度是：", manach...

2021-02-06：假设字符串str长度为N，请问最长回文子串的长度是多少？