2021-06-08：一个字符串至少要切几刀能让切出来的子串都是回文串？ 福大大 答案2021-06-08： 方法一、自然智慧，从左往右，尝试切。回文判断是O(N2)。时间复杂度是O(N3)，空间复杂度是O(N)。 方法二、对字符串范围做是否是回文串的dp。dp[i][j]=true是[i,j]范围上是回文串，dp[i][j]依赖左下方。消耗O(N2)的空间。再弄个dp2，相当于方法一的递归。dp2[i]相当于从i的位置切下去。消耗O(N)的空间。时间复杂度是O(N2)。空间复杂度是O(N**2)。 代码用golang编写。代码如下： package main import ( "f...

2021-06-08：一个字符串至少要切几刀能让切出来的子串都是回文串？

2021-06-07：一个字符串添加最少的字符变成回文串，回文串有多个，请返回所有结果。 福大大 答案2021-06-07： 动态规划回溯。按照前天的每日一题求出二维数组dp，然后根据dp回溯。从dp右上角出发，看dp的左边，下边，左下边。如果dp和左边差值是1，朝左走；如果dp和下边差值是1，朝下走；剩余情况，朝左下走。回溯的时候需要走递归，保证每个符合条件的分支都能走到。 代码用golang编写。代码如下： package main import ( "fmt" "math/rand" "time" ) func main() {...

2021-06-07：一个字符串添加最少的字符变成回文串，回文串有多个，请返回所有结果。

2021-06-06：一个字符串添加最少的字符变成回文串，请返回其中一个结果。 福大大 答案2021-06-06： 动态规划回溯。按照昨天的每日一题求出二维数组dp，然后根据dp回溯。从dp右上角出发，看dp的左边，下边，左下边。如果dp和左边差值是1，朝左走；如果dp和下边差值是1，朝下走；剩余情况，朝左下走。 代码用golang编写。代码如下： package main import ( "fmt" "math/rand" "time" ) func main() { rand.Seed(time.Now().Unix()) TO...

2021-06-06：一个字符串添加最少的字符变成回文串，请返回其中一个结果。

2021-06-05：一个字符串至少需要添加多少个字符能整体变成回文串？ 福大大 答案2021-06-05： 动态规划。s[i]和s[j]不等时：dp[i][j]=min(左边，下边)+1。s[i]和s[j]相等时：dp[i][j]=左下边。 代码用golang编写。代码如下： package main import "fmt" func main() { s := "moonfdd" ret := minInsertions(s) fmt.Println(ret) } func minInsertions(s string) int { if len(...

2021-06-05：一个字符串至少需要添加多少个字符能整体变成回文串？

2021-06-04：给定三个参数：二叉树的头节点head，树上某个节点target，正数K，从target开始，可以向上走或者向下走。返回与target的距离是K的所有节点。 福大大 答案2021-06-04： 记录父节点的map，key是当前节点，value是父节点。访问集合，凡是节点被访问过，放在这个集合中。队列，广度优先遍历。 代码用golang编写。代码如下： package main import "fmt" func main() { root := &Node{Val: 1} root.Left = &Node{Val: 2} root.Ri...

2021-06-04：给定三个参数：二叉树的头节点head，树上某个节点target，正数K，从target开始，可以向上走或者向下走。返回与target的距离是K的所有节点。

2021-06-03：布尔运算。给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。 福大大 答案2021-06-03： 方法一：递归。方法二：动态规划。 代码用golang编写。代码如下： package main import "fmt" func main() { express := "1&1&1" desired := 1 ret0 :=...

2021-06-03：布尔运算。给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。

2021-06-02：给定一棵搜索二叉树头节点，转化成首尾相接的有序双向链表。 福大大 答案2021-06-02： 二叉树递归。左子树串完，右子树串完，最终串自己。 代码用golang编写。代码如下： package main import "fmt" func main() { head := &Node{Val: 5} head.Left = &Node{Val: 3} head.Left.Left = &Node{Val: 1} head.Left.Right = &Node{Val: 4} head.Right = &Node...

2021-06-02：给定一棵搜索二叉树头节点，转化成首尾相接的有序双向链表。