2021-05-24：盛最多水的容器。给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 福大大 答案2021-05-24： 双指针。左指针最左，符合条件时右移；右指针最右，符合条件时左移。左指针和右指针，谁小谁移动；同样大，移动左指针。时间复杂度O(N)，额外空间复杂度O(1)。 代码用golang编写。代码如下： package main import "fmt" fun...

2021-05-24：盛最多水的容器。给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

2021-05-23：给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号。返回公式的计算结果，难点在于括号可能嵌套很多层。str="48((70-65)-43)+81"，返回-1816。str="3+14"，返回7。str="3+(1*4)"，返回7。【说明】 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。2.如果是负数，就需要用括号括起来，比如“4(-3)”但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如"-34"和"(-34)...

2021-05-23：给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号。返回公式的计算结果，难点在于括号可能嵌套很多层。str="48*((70-65)-43)+8*1"，返回-1816。str="3+1*4"，返回7。str="3+(1*4)"，返回7。【说明】 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。2.如果是负数，就需要用括号括起来，比如“4*(-3)”但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3*4)"都是合法的。 3.不用考虑计算过程中会发生溢出的情况。

2021-05-22：假设所有字符都是小写字母， 大字符串是str，arr是去重的单词表， 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式。 返回方法数。 福大大 答案2021-05-22： 前缀树。时间复杂度O(N2)。传统方法的时间复杂度是O(N3)。 代码用golang编写。代码如下： package main import "fmt" func main() { s := "aaab" arr := []string{"a", "aa", "aaa",...

2021-05-20：给定一个数组arr， 返回如果排序之后，相邻两数的最大差值。要求：时间复杂度O(N) 。 福大大 答案2021-05-20： 假设答案法。N个数，根据最大值和最小值的范围等分成N+1个桶。每个桶只需要存当前桶的最大值和最小值。根据鸽笼原理，必然存在空桶。最后只需要遍历求【右桶min-左桶max】，返回最大值。最终答案可能来自相邻桶（这个很难想到），也可能来自跨桶（空桶的左侧和右侧就是跨桶），但是一定不会来自同一个桶内部的情况。另外，这道题是以空间复杂度换取时间复杂度 代码用golang编写。代码如下： package main import ( "fmt&quo...

2021-05-22：假设所有字符都是小写字母， 大字符串是str，arr是去重的单词表， 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式。 返回方法数。

2021-05-21：给定一个数组arr，先递减然后递增，返回arr中有多少个绝对值不同的数字？ 福大大 答案2021-05-21： 双指针。左指针最左，符合条件时右移；右指针最右，符合条件时左移。左指针和右指针，谁大谁移动；同样大，都移动。时间复杂度O(N)，额外空间复杂度O(1)。 代码用golang编写。代码如下： package main import ( "fmt" ) func main() { arr := []int{-2, -2, -3, -4, -3, -3, -2, -2, 3, 4} if true { ret := diff1(arr) fmt.P...

2021-05-21：给定一个数组arr，先递减然后递增，返回arr中有多少个绝对值不同的数字？

2021-05-20：给定一个数组arr， 返回如果排序之后，相邻两数的最大差值。要求：时间复杂度O(N) 。

2021-05-19：给定一个非负数组成的数组，长度一定大于1，想知道数组中哪两个数&的结果最大。返回这个最大结果。时间复杂度O(N)，额外空间复杂度O(1)。 福大大 答案2021-05-19： 因为是正数，所以不用考虑符号位(31位)首先来到30位，假设剩余的数字有N个(整体)，看看这一位是1的数，有几个如果有0个、或者1个说明不管怎么在数组中选择，任何两个数&的结果在第30位上都不可能有1了答案在第30位上的状态一定是0，保留剩余的N个数，继续考察第29位，谁也不淘汰(因为谁也不行，干脆接受30位上没有1的事实)如果有2个，说明答案就是这两个数(直接返回答案)，因为别的数...

2021-05-19：给定一个非负数组成的数组，长度一定大于1，想知道数组中哪两个数&的结果最大。返回这个最大结果。时间复杂度O(N)，额外空间复杂度O(1)。

2021-05-18：Nim博弈。给定一个正数数组arr，先手和后手每次可以选择在一个位置拿走若干值， 值要大于0，但是要小于该处的剩余。谁最先拿空arr，谁赢。根据arr，返回谁赢 。 福大大 答案2021-05-18： 两个数的先手必胜策略：比如[6,8]，先手把数组变成[6,6]。后手不管拿多少，先手保证两个数都一样，这样先手一定会赢。多个数：所有数异或等于0，后手赢。所有数异或不等于0，先手赢。 代码用golang编写。代码如下： package main import "fmt" func main() { arr := []int{1, 2, 3, 4, 5, ...

2021-05-18：Nim博弈。给定一个正数数组arr，先手和后手每次可以选择在一个位置拿走若干值， 值要大于0，但是要小于该处的剩余。谁最先拿空arr，谁赢。根据arr，返回谁赢 。