2021-06-16：返回一个数组中，选择的数字不能相邻的情况下， 最大子序列累加和。

2021-06-15：返回一个二维数组中，子矩阵最大累加和。 福大大 答案2021-06-15： 根据昨天的每日一题计算出0 ~ 0行，0 ~ 1行，0 ~ 2行，……0N行的子数组最大累加和。根据昨天的每日一题计算出1 ~ 1行，1 ~ 2行，1 ~ 3行，……1N行的子数组最大累加和。根据昨天的每日一题计算出2 ~ 2行，2 ~ 3行，2 ~ 4行，……2~N行的子数组最大累加和。……最后取最大值做返回值。 时间复杂度：O(N^2 * M)。 代码用golang编写。代码如下： package main import ( "fmt" "math" )...

2021-06-15：返回一个二维数组中，子矩阵最大累加和。

2021-06-14：返回一个数组中，子数组最大累加和。 福大大 答案2021-06-14： 动态规划。这道题过于经典，就不说具体过程了。时间复杂度：O(N)。空间复杂度：O(1)。 代码用golang编写。代码如下： package main import "fmt" func main() { arr := []int{-1, 2, 3, 4} ret := maxSubArray2(arr) fmt.Println(ret) } func maxSubArray2(arr []int) int { if len(arr) == 0 { return 0 } N := ...

2021-06-14：返回一个数组中，子数组最大累加和。

2021-06-13：如果一个节点X，它左树结构和右树结构完全一样，那么我们说以X为头的树是相等树。给定一棵二叉树的头节点head，返回head整棵树上有多少棵相等子树。 福大大 答案2021-06-14： 方法一：自然智慧。递归函数：头num=左num+右num+0或1。相等判断函数：左结构=右结构，O(N)。树越不平衡，复杂度越低，因此算复杂度的时候，只需要考虑平衡树。master公式：T(N)=2T(N/2)+O(N)。2T(N/2)是递归。O(N)是相等判断函数。根据master公式，时间复杂度是O(N*logN)。 方法二：方法一的相等判断函数用哈希函数。递归函数：头num=左num...

如果一个节点X，它左树结构和右树结构完全一样，那么我们说以X为头的树是相等树。给定一棵二叉树的头节点head，返回head整棵树上有多少棵相等子树。

2021-06-12：已知一棵搜索二叉树上没有重复值的节点，现在有一个数组arr，是这棵搜索二叉树先序遍历的结果。请根据arr生成整棵树并返回头节点。 福大大 答案2021-06-12： 先序遍历+中序遍历（搜索树）+不重复值=唯一的二叉树。 解法一自然智慧。第0位置为根节点，遍历1~N-1位置，找到比0位置大的，那就是属于根的右节点。时间复杂度是O(N**2)。 解法二单调栈。时间复杂度是O(N)。 代码用golang编写。代码如下： package main import ( "container/list" "fmt" ) func main() ...

2021-06-12：已知一棵搜索二叉树上没有重复值的节点，现在有一个数组arr，是这棵搜索二叉树先序遍历的结果。请根据arr生成整棵树并返回头节点。

2021-06-11：给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？ 比如 s1 = "abcde"，s2 = "axbc"。 福大大 答案2021-06-11： 解法一求出str2所有的子序列，然后按照长度排序，长度大的排在前面。然后考察哪个子序列字符串和s1的某个子串相等(KMP)，答案就出来了。分析：因为题目原本的样本数据中，有特别说明s2的长度很小。所以这么做也没有太大问题，也几乎不会超时。但是如果某一次考试给定的s2长度远大于s1，这么做就不合适了。str1长度为N，str2长度为M。时间复杂度：O(2的M次方*N)。 解...

2021-06-11：给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？ 比如 s1 = "abcde"，s2 = "axbc"。

2021-06-10：一个字符串用最少刀数切出来的子串都是回文串，返回所有划分结果 。 福大大 答案2021-06-10： 此题是前天的每日一题的变种。时间紧，有不对的地方，请指正。对字符串范围做是否是回文串的dp。dp[i][j]=true是[i,j]范围上是回文串，dp[i][j]依赖左下方。消耗O(N2)的空间。再弄个dp2，相当于方法一的递归。dp2[i]相当于从i的位置切下去。消耗O(N)的空间。根据dp和dp2，采用递归，就能求出答案。跟前天的每日一题不同的地方，就是这里。时间复杂度是O(N2)。空间复杂度是O(N**2)。 代码用golang编写。代码如下： package ma...

2021-06-10：一个字符串用最少刀数切出来的子串都是回文串，返回所有划分结果 。

2021-06-09：一个字符串用最少刀数切出来的子串都是回文串，返回其中一种划分结果 。 福大大 答案2021-06-09： 此题是昨天的每日一题的变种。对字符串范围做是否是回文串的dp。dp[i][j]=true是[i,j]范围上是回文串，dp[i][j]依赖左下方。消耗O(N2)的空间。再弄个dp2，相当于方法一的递归。dp2[i]相当于从i的位置切下去。消耗O(N)的空间。根据dp2，动态规划回溯，就能求出答案。跟昨天的每日一题不同的地方，就是这里。时间复杂度是O(N2)。空间复杂度是O(N**2)。 代码用golang编写。代码如下： package main import ( &q...