福大大架构师每日一题

2020-03-02：在无序数组中，如何求第K小的数？ 福哥答案2021-03-02： 1.堆排序。工夫复杂度：O(N*lgK)。有代码。2.单边快排。工夫复杂度：O(N)。有代码。3.bfprt算法。工夫复杂度：O(N)。有代码。 代码用golang编写，代码如下： package mainimport ( "container/heap" "fmt" "math/rand" "sort")func main() { //1 2 3 4 5 6 7 arr := []int{1, 2, 3, 4, 5, 10, 9, 8, 7, 6} ret := minKth1(arr, 7) fmt.Println("1.堆排序：", ret) ret = minKth2(arr, 7) fmt.Println("2.单边快排：", ret) ret = minKth3(arr, 7) fmt.Println("3.bfprt算法：", ret)}// 利用大根堆，工夫复杂度O(N*logK)func minKth1(arr []int, k int) int { maxHeap := &IntHeap{} heap.Init(maxHeap) for i := 0; i < k; i++ { heap.Push(maxHeap, arr[i]) } for i := k; i < len(arr); i++ { heap.Push(maxHeap, arr[i]) heap.Pop(maxHeap) //heap.Push(maxHeap, arr[i]) } return heap.Pop(maxHeap).(int)}type IntHeap sort.IntSlicefunc (h IntHeap) Len() int { return len(h) }func (h IntHeap) Less(i, j int) bool { return !(h[i] < h[j]) }func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }//func (h IntHeap) Len() int { return sort.IntSlice(h).Len() }//func (h IntHeap) Less(i, j int) bool { return !sort.IntSlice(h).Less(i, j) }//func (h IntHeap) Swap(i, j int) { sort.IntSlice(h).Swap(i, j) }func (h *IntHeap) Push(x interface{}) { //fmt.Println("push----") // Push and Pop use pointer receivers because they modify the slice's length, // not just its contents. *h = append(*h, x.(int))}func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x}// 改写快排，工夫复杂度O(N)// k >= 1func minKth2(arr []int, k int) int { arrc := make([]int, len(arr)) copy(arrc, arr) return process2(arrc, 0, len(arr)-1, k-1)}// arr 第k小的数// process2(arr, 0, N-1, k-1)// arr[L..R] 范畴上，如果排序的话(不是真的去排序)，找位于index的数// index [L..R]func process2(arr []int, L int, R int, index int) int { if L == R { // L = =R ==INDEX return arr[L] } // 不止一个数 L + [0, R -L] pivot := arr[L+rand.Intn(R-L)] rang := partition(arr, L, R, pivot) if index >= rang[0] && index <= rang[1] { return arr[index] } else if index < rang[0] { return process2(arr, L, rang[0]-1, index) } else { return process2(arr, rang[1]+1, R, index) }}func partition(arr []int, L int, R int, pivot int) []int { less := L - 1 more := R + 1 cur := L for cur < more { if arr[cur] < pivot { less++ arr[less], arr[cur] = arr[cur], arr[less] cur++ } else if arr[cur] > pivot { more-- arr[cur], arr[more] = arr[more], arr[cur] } else { cur++ } } return []int{less + 1, more - 1}}// 利用bfprt算法，工夫复杂度O(N)func minKth3(arr []int, k int) int { arrc := make([]int, len(arr)) copy(arrc, arr) return bfprt(arrc, 0, len(arr)-1, k-1)}// arr[L..R] 如果排序的话，位于index地位的数，是什么，返回func bfprt(arr []int, L int, R int, index int) int { if L == R { return arr[L] } // L...R 每五个数一组 // 每一个小组外部排好序 // 小组的中位数组成新数组 // 这个新数组的中位数返回 pivot := medianOfMedians(arr, L, R) rang := partition(arr, L, R, pivot) if index >= rang[0] && index <= rang[1] { return arr[index] } else if index < rang[0] { return bfprt(arr, L, rang[0]-1, index) } else { return bfprt(arr, rang[1]+1, R, index) }}// arr[L...R] 五个数一组// 每个小组外部排序// 每个小组中位数领进去，组成marr// marr中的中位数，返回func medianOfMedians(arr []int, L int, R int) int { size := R - L + 1 offset := 0 if size%5 != 0 { offset = 1 } mArr := make([]int, size/5+offset) for team := 0; team < len(mArr); team++ { teamFirst := L + team*5 // L ... L + 4 // L +5 ... L +9 // L +10....L+14 mArr[team] = getMedian(arr, teamFirst, getMin(R, teamFirst+4)) } // marr中，找到中位数 // marr(0, marr.len - 1, mArr.length / 2 ) return bfprt(mArr, 0, len(mArr)-1, len(mArr)/2)}func getMedian(arr []int, L int, R int) int { insertionSort(arr, L, R) return arr[(L+R)/2]}func insertionSort(arr []int, L int, R int) { for i := L + 1; i <= R; i++ { for j := i - 1; j >= L && arr[j] > arr[j+1]; j-- { arr[j], arr[j+1] = arr[j+1], arr[j] } }}func getMin(a int, b int) int { if a < b { return a } else { return b }}执行后果如下： ...

2020-03-01：给定一个非负数组arr，代表直方图。返回直方图的最大长方形面积。福哥答案2020-03-01： 枯燥栈，大压小。有代码。 代码用golang编写，代码如下： package mainimport ( "container/list" "fmt")func main() { arr := []int{3, 2, 4, 2, 5} fmt.Println(largestRectangleArea1(arr)) fmt.Println(largestRectangleArea2(arr))}func largestRectangleArea1(height []int) int { if len(height) == 0 { return 0 } maxArea := 0 stack := list.New().Init() N := len(height) for i := 0; i < N; i++ { for !(stack.Len() == 0) && height[i] <= height[stack.Back().Value.(int)] { j := stack.Back().Value.(int) stack.Remove(stack.Back()) k := 0 if stack.Len() == 0 { k = -1 } else { k = stack.Back().Value.(int) } curArea := (i - k - 1) * height[j] maxArea = getMax(maxArea, curArea) } stack.PushBack(i) } for !(stack.Len() == 0) { j := stack.Back().Value.(int) stack.Remove(stack.Back()) k := 0 if stack.Len() == 0 { k = -1 } else { k = stack.Back().Value.(int) } curArea := (N - k - 1) * height[j] maxArea = getMax(maxArea, curArea) } return maxArea}func largestRectangleArea2(height []int) int { if len(height) == 0 { return 0 } N := len(height) stack := make([]int, N) si := -1 maxArea := 0 for i := 0; i < N; i++ { for si != -1 && height[i] <= height[stack[si]] { j := stack[si] si-- k := 0 if si == -1 { k = -1 } else { k = stack[si] } curArea := (i - k - 1) * height[j] maxArea = getMax(maxArea, curArea) } si++ stack[si] = i } for si != -1 { j := stack[si] si-- k := 0 if si == -1 { k = -1 } else { k = stack[si] } curArea := (N - k - 1) * height[j] maxArea = getMax(maxArea, curArea) } return maxArea}func getMax(a int, b int) int { if a > b { return a } else { return b }}执行后果如下： ...

2021-02-28：给定一个整型数组arr，和一个整数num。某个arr中的子数组sub，如果想达标，必须满足：sub中最大值 – sub中最小值 <= num，返回arr中达标子数组的数量。 福哥答案2021-02-28： 采纳两个双端队列，存序号。maxWindow从大到小，minWindow从小到大。1.两个双端队列同时右扩。当最大值-最小值大于sum，退出循环。2.计数。3.删除双端队列右边的过期序号。有代码。 代码用golang编写，代码如下： package mainimport ( "container/list" "fmt")func main() { arr := []int{1, 2} sum := 6 ret := num(arr, sum) fmt.Println(ret)}func num(arr []int, sum int) int { arrLen := len(arr) if arrLen == 0 || sum < 0 { return 0 } count := 0 maxWindow := list.New().Init() minWindow := list.New().Init() R := 0 for L := 0; L < arrLen; L++ { for R < arrLen { //右扩 for maxWindow.Len() > 0 && arr[maxWindow.Back().Value.(int)] <= arr[R] { maxWindow.Remove(maxWindow.Back()) } maxWindow.PushBack(R) //右扩 for minWindow.Len() > 0 && arr[minWindow.Back().Value.(int)] >= arr[R] { minWindow.Remove(minWindow.Back()) } minWindow.PushBack(R) //如果最大值-最小值>sum，就不右扩了。 if arr[maxWindow.Front().Value.(int)]-arr[minWindow.Front().Value.(int)] > sum { break } else { R++ } } //计数 count += R - L //删除过期窗口数据 if maxWindow.Front().Value.(int) == L { maxWindow.Remove(maxWindow.Front()) } if minWindow.Front().Value.(int) == L { minWindow.Remove(minWindow.Front()) } } return count}执行后果如下： ...

2021-02-27：假如一个固定大小为W的窗口，顺次划过arr，返回每一次滑出情况的最大值。例如，arr = [4,3,5,4,3,3,6,7], W = 3。返回：[5,5,5,4,6,7]。 福哥答案2021-02-27： 采纳双端队列，存序号。遍历数组。1.当双端队列里没值或者双端队列最左边的值小于以后值，则把以后值的序号从左边push到队列里。2.否则pop最左边的序号，直到符合条件为止。3.双端队列右边的序号太小，以后序号-左序号>=窗口大小W，须要pop右边的序号。4.双端队列最左边的值就是最大值。有代码。 代码用golang编写，代码如下： package mainimport ( "container/list" "fmt")func main() { arr := []int{4, 3, 5, 4, 3, 3, 6, 7} w := 3 ret := getMaxWindow(arr, w) fmt.Println(ret)}func getMaxWindow(arr []int, w int) []int { arrLen := len(arr) if arrLen < w || w < 1 { return nil } qmax := list.New().Init() res := make([]int, arrLen-w+1) index := 0 for R := 0; R < arrLen; R++ { for qmax.Len() > 0 && arr[qmax.Back().Value.(int)] <= arr[R] { qmax.Remove(qmax.Back()) } qmax.PushBack(R) if qmax.Front().Value.(int) == R-w { qmax.Remove(qmax.Front()) } if R >= w-1 { res[index] = arr[qmax.Front().Value.(int)] index++ } } return res}执行后果如下： ...

2021-02-26：一个数组arr是二叉树的中序遍历后果，每条边的开销是父节点和子节点的乘积，总开销是所有边的开销之和。请问最小总开销是多少？ 链接：https://www.nowcoder.com/ques...起源：牛客网 小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团依照二叉树的中序遍历顺次记录下每个节点的权值，即他记录下了N个数，第i个数示意位于中序遍历第i个地位的节点的权值。之后因为某种原因，小团忘记了二叉树的具体构造。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。当初，小团请小美求出最优二叉树的总开销。 输出形容:第一行输出一个整数N（1<=N<=300），示意二叉树的节点数。第二行输出N个由空格隔开的整数，示意按中序遍历记录下的各个节点的权值，所有权值均为不超过1000的正整数。 输入形容:输入一个整数，示意最优二叉树的总开销。 福哥答案2021-02-26： 天然智慧即可。1.递归。有代码。2.记忆化搜寻。有代码。 代码用golang编写，代码如下： package mainimport "fmt"const MAX = int(^uint(0) >> 1)//https://www.nowcoder.com/questionTerminal/0d939e874a004f449a370aca1346dd5cfunc main() { arr := []int{7, 6, 5, 1, 3} ret := f1(arr) fmt.Println("1.递归：", ret) ret = f2(arr) fmt.Println("2.记忆化搜寻：", ret)}func f1(arr []int) int { arrLen := len(arr) if arrLen <= 1 { return 0 } return process1(arr, -1, 0, arrLen-1)}func process1(arr []int, cur int, L int, R int) int { length := R - L + 1 if length == 0 { return 0 } ans := MAX for i := L; i <= R; i++ { temp := 0 if cur >= 0 { temp = arr[cur] * arr[i] } ans = getMin(temp+process1(arr, i, L, i-1)+process1(arr, i, i+1, R), ans) } return ans}func f2(arr []int) int { arrLen := len(arr) if arrLen <= 1 { return 0 } dp := make([][][]int, arrLen+1) for i := 0; i < arrLen+1; i++ { dp[i] = make([][]int, arrLen) for j := 0; j < arrLen; j++ { dp[i][j] = make([]int, arrLen) for k := 0; k < arrLen; k++ { dp[i][j][k] = -1 } } } ret := process2(arr, -1, 0, arrLen-1, dp) //fmt.Println(dp) return ret}func process2(arr []int, cur int, L int, R int, dp [][][]int) int { length := R - L + 1 if length == 0 { return 0 } if dp[cur+1][L][R] != -1 { //fmt.Println("记忆化", dp[cur+1][L][R]) return dp[cur+1][L][R] } ans := MAX for i := L; i <= R; i++ { temp := 0 if cur >= 0 { temp = arr[cur] * arr[i] } ans = getMin(temp+process2(arr, i, L, i-1, dp)+process2(arr, i, i+1, R, dp), ans) } dp[cur+1][L][R] = ans return ans}func getMin(a int, b int) int { if a < b { return a } else { return b }}执行后果如下： ...

2021-02-25：给定一个负数数组arr，请把arr中所有的数分成两个汇合。如果arr长度为偶数，两个汇合蕴含数的个数要一样多；如果arr长度为奇数，两个汇合蕴含数的个数必须只差一个。请尽量让两个汇合的累加和靠近，返回最靠近的状况下，较小汇合的累加和。 福哥答案2020-02-25：天然智慧即可。1.递归。有代码。2.动静布局。dp是三维数组。有代码。 代码用golang编写，代码如下： package mainimport "fmt"const INT_MAX = int(^uint(0) >> 1)const INT_MIN = ^INT_MAXfunc main() { arr := []int{1, 2, 3, 4, 100} ret := right1(arr) fmt.Println("1.递归：", ret) ret = right2(arr) fmt.Println("2.动静布局：", ret)}func right1(arr []int) int { if len(arr) < 2 { return 0 } sum := 0 for _, v := range arr { sum += v } if len(arr)&1 == 0 { return process1(arr, 0, len(arr)/2, sum/2) } else { ret1 := process1(arr, 0, len(arr)/2, sum/2) ret2 := process1(arr, 0, len(arr)/2+1, sum/2) if ret1 < ret2 { return ret2 } else { return ret1 } }}func process1(arr []int, i int, picks int, rest int) int { if i == len(arr) { if picks == 0 { return 0 } else { return -1 } } else { p1 := process1(arr, i+1, picks, rest) p2 := -1 next := -1 if arr[i] <= rest { next = process1(arr, i+1, picks-1, rest-arr[i]) } if next != -1 { p2 = arr[i] + next } return GetMax(p1, p2) }}func right2(arr []int) int { if len(arr) < 2 { return 0 } sum := 0 for _, v := range arr { sum += v } sum >>= 1 N := len(arr) M := (len(arr) + 1) >> 1 dp := make([][][]int, N) for i := 0; i < N; i++ { dp[i] = make([][]int, M+1) for j := 0; j < M+1; j++ { dp[i][j] = make([]int, sum+1) for k := 0; k < sum+1; k++ { dp[i][j][k] = INT_MIN } } } for i := 0; i < N; i++ { for k := 0; k <= sum; k++ { dp[i][0][k] = 0 } } for k := 0; k <= sum; k++ { if arr[0] <= k { dp[0][1][k] = arr[0] } else { dp[0][1][k] = INT_MIN } } for i := 1; i < N; i++ { for j := 1; j <= GetMin(i+1, M); j++ { for k := 0; k <= sum; k++ { dp[i][j][k] = dp[i-1][j][k] if k-arr[i] >= 0 { dp[i][j][k] = GetMax(dp[i][j][k], dp[i-1][j-1][k-arr[i]]+arr[i]) } } } } return GetMax(dp[N-1][M][sum], dp[N-1][N-M][sum])}func GetMin(a int, b int) int { if a < b { return a } else { return b }}func GetMax(a int, b int) int { if a > b { return a } else { return b }}执行后果如下： ...

福哥答案2020-02-24：天然智慧即可。1.递归。有代码。2.动静布局。dp是二维数组。有代码。 代码用golang编写，代码如下： package mainimport ("fmt")func main() { arr := []int{1, 2, 3} aim := 8 ret := minCoins1(arr, aim) fmt.Println("1.递归：", ret) ret = minCoins2(arr, aim) fmt.Println("2.动静布局：", ret)}const INT_MAX = int(^uint(0) >> 1)func minCoins1(arr []int, aim int) int { return process1(arr, 0, aim)}func process1(arr []int, index int, rest int) int { if index == len(arr) { if rest == 0 { return 0 } else { return INT_MAX } } else { ans := INT_MAX for zhang := 0; zhang*arr[index] <= rest; zhang++ { next := process1(arr, index+1, rest-zhang*arr[index]) if next != INT_MAX { if ans > zhang+next { ans = zhang + next } } } return ans }}func minCoins2(arr []int, aim int) int { if aim == 0 { return 0 } N := len(arr) dp := make([][]int, N+1) for i := 0; i < N+1; i++ { dp[i] = make([]int, aim+1) } dp[N][0] = 0 for j := 1; j <= aim; j++ { dp[N][j] = INT_MAX } for index := N - 1; index >= 0; index-- { for rest := 0; rest <= aim; rest++ { dp[index][rest] = dp[index+1][rest] if rest-arr[index] >= 0 && dp[index][rest-arr[index]] != INT_MAX { dp[index][rest] = getMin(dp[index][rest], dp[index][rest-arr[index]]+1) } } } return dp[0][aim]}func getMin(a int, b int) int { if a < b { return a } else { return b }}执行后果如下： ...

2021-02-23：给定一个负数n，求n的裂开办法数。规定：前面的数不能比后面的数小 。比方4的裂开办法有： 1+1+1+1、1+1+2、1+3、2+2、4，5种，所以返回5。 福哥答案2021-02-23： 天然智慧即可。1.递归。有代码。2.动静布局。dp是二维数组。有代码。3.动静布局，空间压缩。两个一维数组搞定。有代码。 代码用golang编写，代码如下： package mainimport "fmt"func main() { for i := 20; i < 40; i++ { fmt.Println(i, GetWays1(i), GetWays2(i), GetWays3(i)) }}//1.递归func GetWays1(n int) int { if n <= 0 { return 0 } if n == 1 { return 1 } return process1(1, n)}func process1(startMax int, rest int) int { if rest == 0 { return 1 } ans := 0 for i := startMax; i <= rest; i++ { ans += process1(i, rest-i) } return ans}//2.动静布局func GetWays2(n int) int { if n <= 0 { return 0 } if n == 1 { return 1 } dp := make([][]int, n+1) for i := 0; i < n+1; i++ { dp[i] = make([]int, n+1) } for i := 1; i <= n; i++ { dp[i][0] = 1 dp[i][i] = 1 } for startMax := n - 1; startMax >= 1; startMax-- { for rest := startMax + 1; rest <= n; rest++ { dp[startMax][rest] = dp[startMax][rest-startMax] + dp[startMax+1][rest] } } return dp[1][n]}//3.动静布局，空间压缩func GetWays3(n int) int { if n <= 0 { return 0 } if n == 1 { return 1 } dp := make([][]int, 2) for i := 0; i < 2; i++ { dp[i] = make([]int, n+1) } dp[1][0] = 1 dp[1][n] = 1 for startMax := n - 1; startMax >= 1; startMax-- { dp[0][startMax] = 1 dp[0][0] = 1 for rest := startMax + 1; rest <= n; rest++ { dp[0][rest] = dp[0][rest-startMax] + dp[1][rest] } dp[1], dp[0] = dp[0], dp[1] } return dp[1][n]}执行后果如下： ...

2021-02-22：一个象棋的棋盘，而后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)地位，那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域。给你三个 参数 x，y，k。返回“马”从(0,0)地位登程，必须走k步。最初落在(x,y)上的办法数有多少种? 福哥答案2021-02-22： 天然智慧即可。1.递归。有代码。2.记忆化搜寻。有代码。3.动静布局。dp是三维数组。棋盘是二维数组，走k步，须要k+1个棋盘。有代码。4.动静布局，空间压缩。只有相邻棋盘才有依赖，所以只须要用两个棋盘，就能走完。有代码。 代码用golang编写，代码如下： package mainimport "fmt"func main() { a := 3 b := 4 k := 5 fmt.Println("1.递归：", jump1(a, b, k)) fmt.Println("---") fmt.Println("2.记忆化搜寻：", jump2(a, b, k)) fmt.Println("---") fmt.Println("3.动静布局：", jump3(a, b, k)) fmt.Println("---") fmt.Println("4.动静布局,空间压缩：", jump4(a, b, k))}func jump1(a int, b int, k int) int { return process1(0, 0, k, a, b)}func process1(x int, y int, rest int, a int, b int) int { if x < 0 || x >= 9 || y < 0 || y >= 10 { return 0 } if rest == 0 { if x == a && y == b { return 1 } else { return 0 } } ways := process1(x+2, y+1, rest-1, a, b) ways += process1(x+2, y-1, rest-1, a, b) ways += process1(x-2, y+1, rest-1, a, b) ways += process1(x-2, y-1, rest-1, a, b) ways += process1(x+1, y+2, rest-1, a, b) ways += process1(x+1, y-2, rest-1, a, b) ways += process1(x-1, y+2, rest-1, a, b) ways += process1(x-1, y-2, rest-1, a, b) return ways}func jump2(a int, b int, k int) int { dp := make([][][]int, 10) for i := 0; i < 10; i++ { dp[i] = make([][]int, 9) for j := 0; j < 9; j++ { dp[i][j] = make([]int, k+1) for m := 0; m < k+1; m++ { dp[i][j][m] = -1 } } } return process2(0, 0, k, a, b, dp)}func process2(x int, y int, rest int, a int, b int, dp [][][]int) int { if x < 0 || x >= 10 { return 0 } if y < 0 || y >= 9 { return 0 } if dp[x][y][rest] != -1 { return dp[x][y][rest] } if rest == 0 { if x == a && y == b { dp[x][y][rest] = 1 return 1 } else { dp[x][y][rest] = 0 return 0 } } ways := process2(x+2, y+1, rest-1, a, b, dp) ways += process2(x+2, y-1, rest-1, a, b, dp) ways += process2(x-2, y+1, rest-1, a, b, dp) ways += process2(x-2, y-1, rest-1, a, b, dp) ways += process2(x+1, y+2, rest-1, a, b, dp) ways += process2(x+1, y-2, rest-1, a, b, dp) ways += process2(x-1, y+2, rest-1, a, b, dp) ways += process2(x-1, y-2, rest-1, a, b, dp) dp[x][y][rest] = ways return ways}func jump3(a int, b int, k int) int { dp := make([][][]int, 10) for i := 0; i < 10; i++ { dp[i] = make([][]int, 9) for j := 0; j < 9; j++ { dp[i][j] = make([]int, k+1) } } dp[a][b][0] = 1 for rest := 1; rest <= k; rest++ { for x := 0; x < 10; x++ { for y := 0; y < 9; y++ { ways := pick3(x+2, y+1, rest-1, dp) ways += pick3(x+1, y+2, rest-1, dp) ways += pick3(x-1, y+2, rest-1, dp) ways += pick3(x-2, y+1, rest-1, dp) ways += pick3(x-2, y-1, rest-1, dp) ways += pick3(x-1, y-2, rest-1, dp) ways += pick3(x+1, y-2, rest-1, dp) ways += pick3(x+2, y-1, rest-1, dp) dp[x][y][rest] = ways } } } return dp[0][0][k]}func pick3(x int, y int, rest int, dp [][][]int) int { if x < 0 || x >= 10 || y < 0 || y >= 9 { return 0 } return dp[x][y][rest]}func jump4(a int, b int, k int) int { dp := make([][][]int, 10) for i := 0; i < 10; i++ { dp[i] = make([][]int, 9) for j := 0; j < 9; j++ { dp[i][j] = make([]int, 2) } } dp[a][b][0] = 1 for rest := 1; rest <= k; rest++ { for x := 0; x < 10; x++ { for y := 0; y < 9; y++ { ways := pick4(x+2, y+1, dp) ways += pick4(x+1, y+2, dp) ways += pick4(x-1, y+2, dp) ways += pick4(x-2, y+1, dp) ways += pick4(x-2, y-1, dp) ways += pick4(x-1, y-2, dp) ways += pick4(x+1, y-2, dp) ways += pick4(x+2, y-1, dp) dp[x][y][1] = ways } } for i := 0; i < 10; i++ { for j := 0; j < 9; j++ { dp[i][j][0], dp[i][j][1] = dp[i][j][1], 0 } } } return dp[0][0][0]}func pick4(x int, y int, dp [][][]int) int { if x < 0 || x >= 10 || y < 0 || y >= 9 { return 0 } return dp[x][y][0]}执行后果如下： ...

2021-02-21：手写代码：高性能路由，也就是一个字符串和多个匹配串进行含糊匹配。一个数组arr里是["a","moonfdd"]，字符串"moonfdd"能匹配到，理由是arr里有。字符串"xayy"也能匹配到，理由是arr里的"a"，第1个星对应"x"，第2个星对应"yy"。 福哥答案2021-02-21： 1.前缀树。字符匹配和星号匹配。abcd和abcd,当左c和右对应的时候，下一步分两种状况，左d和右*对应，左c和右c对应。有代码。2.ACOK算法。过后和面试官聊的时候，面试官说了ACOK算法，但这个算法在网上没找到。百度了一番，感觉就是Aho-Corasick automaton算法，也就是AC自动机。AC自动机，没找到解法，所以没代码。 代码用golang编写，代码如下： package mainimport "fmt"func main() { fmt.Println("力扣208 测试") trie := Constructor() trie.Insert("apple") trie.Search("apple") // 返回 true trie.Search("app") // 返回 false trie.StartsWith("app") // 返回 true trie.Insert("app") trie.Search("app") // 返回 true fmt.Println("--------------------") fmt.Println("高性能路由 测试") ret := "" ret = RouteMatching("fudada", []string{"fudada*"}) fmt.Println("ret = ", ret) ret = RouteMatching("fudada", []string{"fu******da*"}) fmt.Println("ret = ", ret) ret = RouteMatching("fudada", []string{"fudada**"}) fmt.Println("ret = ", ret)}type TrieNode struct { pass int end int nextMap map[byte]*TrieNode}type Trie struct { root *TrieNode}/** Initialize your data structure here. */func Constructor() Trie { return Trie{root: &TrieNode{nextMap: make(map[byte]*TrieNode)}}}/** Inserts a word into the trie. */func (this *Trie) Insert(word string) { wordLen := len(word) if wordLen == 0 { return } node := this.root node.pass++ for i := 0; i < wordLen; i++ { // 从左往右遍历字符 if node.nextMap[word[i]] == nil { node.nextMap[word[i]] = &TrieNode{nextMap: make(map[byte]*TrieNode)} } node = node.nextMap[word[i]] node.pass++ } node.end++}/** Returns if the word is in the trie. */func (this *Trie) Search(word string) bool { wordLen := len(word) if wordLen == 0 { fmt.Println(false) return false } node := this.root for i := 0; i < wordLen; i++ { // 从左往右遍历字符 if node.nextMap[word[i]] == nil { fmt.Println(false) return false } node = node.nextMap[word[i]] } fmt.Println(node.end > 0) return node.end > 0}/** Returns if there is any word in the trie that starts with the given prefix. */func (this *Trie) StartsWith(prefix string) bool { word := prefix wordLen := len(word) if wordLen == 0 { fmt.Println(false) return false } node := this.root for i := 0; i < wordLen; i++ { // 从左往右遍历字符 if node.nextMap[word[i]] == nil { fmt.Println(false) return false } node = node.nextMap[word[i]] } fmt.Println(node.pass > 0) return node.pass > 0}func RouteMatching(url string, fuzzyMatches []string) string { fuzzyMatchesLen := len(fuzzyMatches) if fuzzyMatchesLen == 0 && len(url) == 0 { return "" } trie := Constructor() for i := 0; i < fuzzyMatchesLen; i++ { trie.Insert(fuzzyMatches[i]) } return process(url, 0, trie.root, "")}func process(url string, index int, root *TrieNode, retPre string) string { urlLen := len(url) if index >= urlLen { if root.end > 0 { return retPre } else { if root.nextMap['*'] != nil { return process(url, index, root.nextMap['*'], retPre+"*") } return "" } } ret := "" //1.匹配字符 if root.nextMap[url[index]] != nil { ret = process(url, index+1, root.nextMap[url[index]], retPre+url[index:index+1]) if ret != "" { return ret } } //2.匹配* if root.nextMap['*'] != nil { ret = process(url, index, root.nextMap['*'], retPre+"*") if ret != "" { return ret } ret = process(url, index+1, root, retPre) if ret != "" { return ret } } return ret}执行后果如下： ...

福哥答案2021-02-20： 四大办法：读加锁，读解锁，写加锁，写解锁。读加锁里有写加锁，读解锁里有写解锁。代码有写线程饥饿景象，但实现简略。 代码用golang编写，代码如下： package mainimport ( "fmt" "sync" "time")func main() { fdd := FddRWMutex{} go func() { i := 0 for k := 0; k < 5; k++ { go func() { j := i i++ fdd.RLock() fmt.Println("读操作", j) time.Sleep(5 * time.Second) fdd.RUnlock() }() time.Sleep(3 * time.Second) } }() time.Sleep(1000) fdd.Lock() fmt.Println("写操作------------------------------------------") fdd.Unlock() fmt.Println("有写线程饥饿景象")}type FddRWMutex struct { w sync.Mutex r sync.Mutex readerCount int}func (rw *FddRWMutex) RLock() { rw.r.Lock() rw.readerCount++ if rw.readerCount == 1 { rw.w.Lock() } rw.r.Unlock()}func (rw *FddRWMutex) RUnlock() { rw.r.Lock() rw.readerCount-- if rw.readerCount == 0 { rw.w.Unlock() } rw.r.Unlock()}func (rw *FddRWMutex) Lock() { rw.w.Lock()}func (rw *FddRWMutex) Unlock() { rw.w.Unlock()}执行后果如下： ...

2021-02-19：给定一个二维数组matrix，一个人必须从左上角登程，最初达到右下角。沿途只能够向下或者向右走，沿途的数字都累加就是间隔累加和。请问最小间隔累加和是多少？ 福哥答案2021-02-19：天然智慧即可。个别会思考dpi的左边和下边，谁小选谁，尽管你能确定下一步是最小值，然而下一步的当前就不肯定是最小值了，不是门路最优。逆向思维，dpi的右边和上边，谁小选谁，右边和上边曾经确定了，必定门路最优。这道题能够用空间压缩技巧，所以dp不须要二维数组，用一维数组即可。这揭示了一个人生情理：将来是不确定的，过来是确定的。代码用golang编写，代码如下： package mainimport "fmt"func main() { if true { arr := [][]int{ {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}} ret := minPathSum(arr) fmt.Println(ret) }}func minPathSum(m [][]int) int { row := len(m) if row == 0 { return 0 } col := len(m[0]) if col == 0 { return 0 } dp := make([]int, col) dp[0] = m[0][0] for j := 1; j < col; j++ { dp[j] = dp[j-1] + m[0][j] } for i := 1; i < row; i++ { dp[0] += m[i][0] for j := 1; j < col; j++ { dp[j] = getMin(dp[j-1], dp[j]) + m[i][j] } } return dp[col-1]}func getMin(a int, b int) int { if a < b { return a } else { return b }}执行后果如下： ...

2021-02-18：给定一个字符串str，给定一个字符串类型的数组arr，呈现的字符都是小写英文。arr每一个字符串，代表一张贴纸，你能够把单个字符剪开应用，目标是拼出str来。返回须要至多多少张贴纸能够实现这个工作。例子：str= "babac"，arr = {"ba","c","abcd"}。a + ba + c 3 abcd + abcd 2 abcd+ba 2。所以返回2。 福哥答案2021-02-18：天然智慧即可。带记忆的递归。对“babac”排序，变成“aabbc”，而后依据数组，顺次消掉a，而后b，最初c，这是一个优化点。有代码。代码用golang编写，代码如下： package mainimport ( "fmt" "strings")const MAX = int(^uint(0) >> 1) //结构0111111111.... 9223372036854775807const MIN = int(^MAX) //结构10000000... -9223372036854775808func main() { ret := minStickers([]string{"ba", "c", "abcd"}, "babac") fmt.Println(ret)}func minStickers(stickers []string, target string) int { N := len(stickers) counts := make([][]int, N) for i := 0; i < N; i++ { counts[i] = make([]int, 26) } for i := 0; i < N; i++ { str := stickers[i] for _, cha := range str { counts[i][cha-'a']++ } } dp := make(map[string]int) dp[""] = 0 ans := process(counts, target, dp) if ans == MAX { return -1 } else { return ans }}func process(stickers [][]int, t string, dp map[string]int) int { if _, ok := dp[t]; ok { return dp[t] } tcounts := make([]int, 26) for _, cha := range t { tcounts[cha-'a']++ } N := len(stickers) min := MAX for i := 0; i < N; i++ { sticker := stickers[i] if sticker[t[0]-'a'] > 0 { builder := strings.Builder{} for j := 0; j < 26; j++ { if tcounts[j] > 0 { nums := tcounts[j] - sticker[j] for k := 0; k < nums; k++ { builder.WriteByte('a' + byte(j)) } } } rest := builder.String() min = getMin(min, process(stickers, rest, dp)) } } ans := min if min != MAX { ans++ } dp[t] = ans return ans}func getMin(a int, b int) int { if a < b { return a } else { return b }}执行后果如下： ...

2021-02-17：规定1和A对应、2和B对应、3和C对应...26和Z对应，那么一个数字字符串比方"111”就能够转化为:"AAA"、"KA"和"AK"。给定一个只有数字字符组成的字符串str，请问有多少种转化后果？ 福哥答案2021-02-17： 天然智慧即可。1.递归。有代码。2.动静布局。有代码。 代码用golang编写，代码如下： package mainimport "fmt"func main() { str := "7210231231232031203123" fmt.Println("1.递归：", number1(str)) fmt.Println("2.动静布局：", number2(str))}func number1(str string) int { if len(str) == 0 { return 0 } return process1(str, 0)}func process1(str string, index int) int { strLen := len(str) if strLen == index { //1 return 1 } if str[index] == '0' { return 0 } ret := process1(str, index+1) if index+1 < strLen && (str[index] == '1' || (str[index] == '2' && str[index+1] <= '6')) { ret += process1(str, index+2) } return ret}func number2(str string) int { strLen := len(str) if strLen == 0 { return 0 } dp := make([]int, strLen+1) dp[strLen] = 1 //1 for i := strLen - 1; i >= 0; i-- { if str[i] == '0' { continue } dp[i] = dp[i+1] if i+1 < strLen && (str[i] == '1' || (str[i] == '2' && str[i+1] <= '6')) { dp[i] += dp[i+2] } } return dp[0]}执行后果如下： ...

福哥答案2021-02-16： 天然智慧即可。1.一般递归。有代码。须要判断同列和斜线。2.位运算递归。有代码。3.我的递归。有代码。只须要判断斜线。 代码用golang编写，代码如下： package mainimport ( "fmt" "time")func main() { n := 12 fmt.Println(n, "皇后问题") fmt.Println("------") now := time.Now() fmt.Println("1.一般递归：", num1(n)) fmt.Println("工夫：", time.Now().Sub(now)) fmt.Println("------") now = time.Now() fmt.Println("2.位运算递归：", num2(n)) fmt.Println("工夫：", time.Now().Sub(now)) fmt.Println("------") now = time.Now() fmt.Println("3.我的递归：", num3(n)) fmt.Println("工夫：", time.Now().Sub(now))}func num1(n int) int { if n < 1 { return 0 } record := make([]int, n) return process1(0, record, n)}func process1(i int, record []int, n int) int { if i == n { return 1 } res := 0 for j := 0; j < n; j++ { if isValid(record, i, j) { record[i] = j res += process1(i+1, record, n) } } return res}func isValid(record []int, i int, j int) bool { for k := 0; k < i; k++ { if j == record[k] || abs(record[k]-j) == abs(i-k) { return false } } return true}func abs(a int) int { if a < 0 { return -a } else { return a }}func num2(n int) int { if n < 1 || n > 32 { return 0 } limit := -1 if n != 32 { limit = (1 << n) - 1 } return process2(limit, 0, 0, 0)}func process2(limit int, colLim int, leftDiaLim int, rightDiaLim int) int { if colLim == limit { return 1 } pos := limit & (^(colLim | leftDiaLim | rightDiaLim)) mostRightOne := 0 res := 0 for pos != 0 { mostRightOne = pos & (^pos + 1) pos = pos - mostRightOne res += process2(limit, colLim|mostRightOne, (leftDiaLim|mostRightOne)<<1, (rightDiaLim|mostRightOne)>>1) } return res}func num3(n int) int { rest := make([]int, n) record := make([]int, n) for i := 0; i < n; i++ { rest[i] = i } ansval := 0 ans := &ansval process3(record, 0, rest, ans) return *ans}func process3(record []int, recordLen int, rest []int, ans *int) { restLen := len(rest) if restLen == 0 { *ans++ return } for i := 0; i < restLen; i++ { isValid := true for j := 0; j < recordLen; j++ { //不须要看同行和同列，只须要思考斜线 if abs(j-recordLen) == abs(record[j]-rest[i]) { isValid = false break } } if isValid { record[recordLen] = rest[i] restCopy := make([]int, restLen) copy(restCopy, rest) restCopy = append(restCopy[:i], restCopy[i+1:]...) process3(record, recordLen+1, restCopy, ans) } }}执行后果如下： ...