2021-04-09：rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。 【要求】时间复杂度O(N)，额外空间复杂度O(1) 。 福大大 答案2021-04-09：  假设链表节点是A1→B1→C1。1.复制节点，插入原链表，链表变成A1→A2→B1→B2→C1→C2。2.设置A2、B2、C2的随机指针。3.拆分链表。变成A1→B1→C1和A2→B2→C2。4.返回A2→B2→C2。  代码用golang编写。代码如下： ...

2021-04-09：rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。 【要求】时间复杂度O(N)，额外空间复杂度O(1) 。

2021-04-09：rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。 【要求】时间复杂度O(N)，额外空间复杂度O(1) 。

2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。 福大大 答案2021-04-08： 1.找中点。2.按中点切分成两个链表。3.反转右边链表。4.相等判断。5.反转右边链表。6.左右链表合并。7.返回true或者false。 代码用golang编写。代码如下： package main import "fmt" func main() { head := &ListNode{Val: 1} head.Next = &ListNode{Val: 2} head.Next.Next = &ListNode{Val: 3}...

2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。

2021-04-07：给定一个非负数组arr，长度为N，那么有N-1种方案可以把arr切成左右两部分，每一种方案都有，min{左部分累加和，右部分累加和}，求这么多方案中，min{左部分累加和，右部分累加和}的最大值是多少？ 整个过程要求时间复杂度O(N)。 福大大 答案2021-04-07： 自然智慧即可。1.算出总累加和。2.依次遍历，算出左累加和、右累加和。假设最小值是min。3.当min大于ans时，保存min到ans中。4.当左累加和大于右累加和时，退出循环。5.返回ans。 代码用golang编写。代码如下： package main import "fmt" ...

2021-04-07：给定一个非负数组arr，长度为N，那么有N-1种方案可以把arr切成左右两部分，每一种方案都有，min{左部分累加和，右部分累加和}，求这么多方案中，min{左部分累加和，右部分累加和}的最大值是多少？ 整个过程要求时间复杂度O(N)。

2021-04-06：假设有一个源源吐出不同球的机器，只有装下10个球的袋子，每一个吐出的球，要么放入袋子，要么永远扔掉。如何做到机器吐出每一个球之后，所有吐出的球都等概率被放进袋子里。 福大大 答案2021-04-06： i为球的序号。i从1开始，小于等于10的时候直接进袋子。i大于10的时候，10/i的几率进袋子；在袋子中的球，1/10的几率淘汰。 代码用golang编写。代码如下： package main import ( "fmt" "math/rand" "time" ) func main() { rand.Seed(t...

2021-04-06：假设有一个源源吐出不同球的机器，只有装下10个球的袋子，每一个吐出的球，要么放入袋子，要么永远扔掉。如何做到机器吐出每一个球之后，所有吐出的球都等概率被放进袋子里。

2021-04-05：给两个长度分别为M和N的整型数组nums1和nums2，其中每个值都不大于9，再给定一个正数K。 你可以在nums1和nums2中挑选数字，要求一共挑选K个，并且要从左到右挑。返回所有可能的结果中，代表最大数字的结果。 福大大 答案2021-04-05： 自然智慧想不到，需要练敏感度。1.动态规划+选元素+双指针的合并。无代码。2.动态规划+选元素+双指针的DC3合并。有代码。2.1.dp[i][j]，i是数组序号，j是[0,K]的数，dp[i][j]是最优位置。2.2.从arr1和arr2中选元素。2.3.合并arr1中的选中的元素和arr2中的选中的元素，采用dc算法...

2021-04-05：给两个长度分别为M和N的整型数组nums1和nums2，其中每个值都不大于9，再给定一个正数K。 你可以在nums1和nums2中挑选数字，要求一共挑选K个，并且要从左到右挑。返回所有可能的结果中，代表最大数字的结果。

2021-04-04：给定一个非负数组arr，和一个正数m。 返回arr的所有子序列中累加和%m之后的最大值。 福大大 答案2021-04-04： 自然智慧即可。1.递归，累加和。2.动态规划，累加和。3.动态规划，累加和%m。4.双向动态规划，累加和%m。 代码用golang编写。代码如下： package main import ( "fmt" "math/rand" "sort" "time" ) func main() { rand.Seed(time.Now().Unix()) const TOTAL =...

2021-04-04：给定一个非负数组arr，和一个正数m。 返回arr的所有子序列中累加和%m之后的最大值。

2021-04-03：给定两个字符串str1和str2，想把str2整体插入到str1中的某个位置，形成最大的字典序，返回字典序最大的结果。 福大大 答案2021-04-03： 1.暴力法。2.DC3算法。自然智慧想不到，需要练敏感度。2.1.构造字符串。str = str1+最小字符+str2。2.2.对str进行dc3算法，求出rank数组。2.3.遍历0到str1长度，找到小于str2起始位置的序号。2.4.根据序号算出bestSplit值。时间紧，先放一放。2.5.根据bestSplit拆分str1，然后合并。返回str1左+str2+str1右。 代码用golang编写。代码如下： ...