2021-04-23：TSP问题 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的距离都为0。所有点到点的距 离都存在一个N*N的二维数组matrix里，也就是整张图由邻接矩阵表示。现要求一旅行商从k城市 出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的k城，返回总距离最短的路的 距离。参数给定一个matrix，给定k。 福大大 答案2021-04-23： 动态规划。 代码用golang编写。代码如下： package main import ( "fmt" "math" ) func main() { matrix := [][...

2021-04-22：给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间，规定：1）线段的开始和结束位置一定都是整数值，2）线段重合区域的长度必须>=1。返回线段最多重合区域中，包含了几条线段 。 福大大 答案2021-04-22：  小根堆。1.按线段起点排序。2.遍历线段，push和pop小根堆。2.1.小根堆循环pop小于等于线段起点的值。2.2.把线段结束位置push到小根堆中。2.3.收集最大的小根堆长度，假设是max。3.返回max。  代码用golang编写。代码如下：  package main import ( &quo...

2021-04-21：手写代码：Dijkstra算法。 福大大 答案2021-04-21： Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。时间紧，未完成。 代码用golang编写。代码如下： package main import ( "fmt" "math" ) func main() { fmt.Println("") } func dijkstra1(from *Node) map[*Node]int { distanceMap := make(map[*Node]int) d...

2021-04-20：手写代码：最小生成树算法之Prim。 福大大 答案2021-04-20： 解锁点，解锁边，解锁点，解锁边，一直解锁下去。 代码用golang编写。代码如下： package main import ( "fmt" "math" ) func main() { graph := [][]int{ {0, 11, 55}, {math.MaxInt32, 0, 22}, {math.MaxInt32, math.MaxInt32, 0}} ret := prim(graph) fmt.Println(ret) } // 请保证graph...

2021-04-19：手写代码：最小生成树算法之Kruskal。 福大大 答案2021-04-19： 并查集。边从小到大，找最小边，无环。 代码用golang编写。代码如下： package main import ( "fmt" "sort" ) func main() { graph := &Graph{} graph.nodes = make(map[int]*Node) graph.nodes[0] = &Node{} graph.nodes[1] = &Node{} graph.nodes[2] = &Node{...

2021-04-18：给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量。 福大大 答案2021-04-18： 并查集。 代码用golang编写。代码如下： package main import "fmt" func main() { arr := [][]byte{ {49, 49, 49, 49, 48}, {49, 49, 48, 49, 48}, {49, 49, 48, 49, 48}, {49, 49, 48, 48, 48}, {48, 48, 48, 48, 48}} ret := numIs...

2021-04-17：给定一个整型数组 arr，数组中的每个值都为正数，表示完成一幅画作需要的时间，再 给定 一个整数 num，表示画匠的数量，每个画匠只能画连在一起的画作。所有的画家 并行工作，请 返回完成所有的画作需要的最少时间。【举例】arr=[3,1,4]，num=2。最好的分配方式为第一个画匠画 3 和 1，所需时间为 4。第二个画匠画 4，所需时间 为 4。 因为并行工作，所以最少时间为 4。如果分配方式为第一个画匠画 3，所需时 间为 3。第二个画 匠画 1 和 4，所需的时间为 5。那么最少时间为 5，显然没有第一 种分配方式好。所以返回 4。arr=[1,1,1,4,3]，n...

2021-04-16：摆放着n堆石子。现要将石子有次序地合并成一堆，规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。求出将n堆石子合并成一堆的最小得分（或最大得分）合并方案。 福大大 答案2021-04-16： 动态规划。 代码用golang编写。代码如下： package main import ( "fmt" "math" ) func main() { arr := []int{1, 4, 2, 3} ret := StoneMerge(arr) fmt.Println(ret) } func sum(arr []...

2021-04-15：给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果。 福大大 答案2021-04-15： “b”和“ba”，直接比较两个字符串大小，得到的答案很容易出错。比较“b”+“ba”和“ba”+“b”，得到的答案一定正确。 代码用golang编写。代码如下： package main import ( "fmt" "sort" ) func main() { strs := []string{"b", "ba", "baa"}...

2021-04-25：给定一个数组arr，和一个正数M，返回在arr的子数组在长度不超过M的情况下，求最大的累加和。

2021-04-24：手写代码：拓扑排序。

2021-04-23：TSP问题 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的距离都为0。所有点到点的距 离都存在一个N*N的二维数组matrix里，也就是整张图由邻接矩阵表示。现要求一旅行商从k城市 出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的k城，返回总距离最短的路的 距离。参数给定一个matrix，给定k。

2021-04-22：给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间，规定：1）线段的开始和结束位置一定都是整数值，2）线段重合区域的长度必须>=1。返回线段最多重合区域中，包含了几条线段 。

2021-04-21：手写代码：Dijkstra算法。