算法编程题-不相交的线 & 联通网络的利用次数 & 销售代价减少的颜色球

择要：本文将先容三道LeetCode原题，分别是不相交的线，联通网络的利用次数，销售代价减少的颜色球。首先会简单描述原题，接着给出思路分析，然后是基于golang语言实现且通过所有测试用例的代码，末了是相应的复杂度分析。
关键词：LeetCode，面试，golang，算法，并查集
不相交的线

原题描述

LeetCode1035 不相交的线：给定两个数组nums1和nums2，作为上下两行的数字排列，现在必要将上下两行中相等数字用直线连接起来，但是不能出现两线交叉，在端点处交叉也不被答应，求出最多能够连多少条直线。
思路简述

如下图，如果nums1选择nums2[j]连线后，那么对于nums1[i+1]来说，为了制止交叉，其只能选择nums2[j+1:]中的元素进行连线，那么这其实就是一个子标题了。所以定义dp[j]表示对于nums1[i:]和nums[j:]中的元素进行连线，不交叉的最多连线数量。在匹配nums1时，从nums[j]开始往右找第一个相等的元素即可，整体推导的方向是从后往前推导，必要注意的是，对于nums1来说，也可以选择不连线。

从nums2数组内里查找某一个元素的时候，可以直接遍历去查找，这样做整体的时间复杂度为                                   O                         (                         m                                   n                            2                                  )                              O(mn^2)                  O(mn2)，但现实上可以利用哈希表将查找的复杂度降低到                                   O                         (                         1                         )                              O(1)                  O(1)，从而使得整体的时间复杂度为                                   O                         (                         m                         n                         )                              O(mn)                  O(mn)。
此外，这道标题也是一个经典标题的换皮题，即最长公共子前缀标题，也是可以利用动态规划思路完成的。三种方法的代码实现如下。
代码实现

• 平凡动态规划
  

1. func maxUncrossedLines(nums1 []int, nums2 []int) int {
2.     m := len(nums1)
3.         n := len(nums2)
4.         // dp[i][j] 表示nums1[i:] nums2[j:]区域内最大的交叉线数目
5.         dp := make([][]int, m + 1)
6.         for i := 0; i <= m; i++ {
7.                 dp[i] = make([]int, n + 1)
8.         }
10.         for i := m - 1; i >= 0; i-- {
11.                 for j := n - 1; j >= 0; j-- {
12.                         dp[i][j] = dp[i + 1][j]
13.                         // 往前找一个相等的
14.                         k := j
15.                         for k < n && nums2[k] != nums1[i] {
16.                                 k++
17.                         }
18.                         if k != n {
19.                                 dp[i][j] = max(dp[i][j], dp[i + 1][k + 1] + 1)
20.                         }
21.                 }
22.         }
23.         return dp[0][0]
24. }

复制代码

LeetCode运行截图如下：

• 优化动态规划
  

1. func maxUncrossedLines(nums1 []int, nums2 []int) int {
2.     m := len(nums1)
3.         n := len(nums2)
4.         // dp[i][j] 表示nums1[i:] nums2[j:]区域内最大的交叉线数目
5.         dp := make([][]int, m + 1)
6.         for i := 0; i <= m; i++ {
7.                 dp[i] = make([]int, n + 1)
8.         }
10.         var value2Index map[int]int
11.         for i := m - 1; i >= 0; i-- {
12.                 value2Index = make(map[int]int)
13.                 for j := n - 1; j >= 0; j-- {
14.                         value2Index[nums2[j]] = j
15.                         dp[i][j] = dp[i + 1][j]
16.                         if k, ok := value2Index[nums1[i]]; ok {
17.                                 dp[i][j] = max(dp[i][j], dp[i + 1][k + 1] + 1)
18.                         }
19.                 }
20.         }
21.         return dp[0][0]
22. }

复制代码

LeetCode运行截图如下：

3. 经典动态规划

1. func maxUncrossedLines(nums1 []int, nums2 []int) int {
2.         m := len(nums1)
3.         n := len(nums2)
4.         // dp[i][j] 表示nums1[:i] nums2[:j]区域内最大的交叉线数目
5.         dp := make([][]int, m+1)
6.         for i := 0; i <= m; i++ {
7.                 dp[i] = make([]int, n+1)
8.         }
10.         for i := 1; i <= m; i++ {
11.         for j := 1; j <= n; j++ {
12.             dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
13.             if nums1[i - 1] == nums2[j - 1] {
14.                 dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
15.             }
16.         }
17.     }
18.         return dp[m][n]
19. }

复制代码

LeetCode运行截图如下：

复杂度分析

• 时间复杂度：第一种方法的时间复杂度为                                        O                            (                            m                                       n                               2                                      )                                  O(mn^2)                     O(mn2)，背面两种方法的时间复杂度为                                        O                            (                            m                            n                            )                                  O(mn)                     O(mn)
  
• 空间复杂度：                                        O                            (                            m                            n                            )                                  O(mn)                     O(mn)
  

连通网络的最少利用次数

原题描述

LeetCode1319 连通网络的最少利用次数：给定一个网络，可以将某些边摘出放在别的两个节点之间，求用最少利用次数使得这个网络成为一个连通图，如果不能做到，返回-1。
思路简述

对于n个节点的无向图来说，只要边数大于即是n-1，就可以将这张图连成一个连通图，基于这一点快速判断是否能够将网络连成一个连通图。接着，只要计算出连通分量的数量，那么连通分量减去一就是利用次数。而计算连通分量的数量可以有两种做法，分别是深度优先搜刮已经并查集，下面给出并查集的代码实现。
代码实现

1. func makeConnected(n int, connections [][]int) int {
2.     m := len(connections)
3.     if m < n - 1 {
4.         return -1
5.     }
6.         uSet := NewUnionSet(n)
7.         clusterCount := n
9.         for _, conn := range connections {
10.                 a, b := conn[0], conn[1]
11.                 if !uSet.InSame(a, b) {
12.                         uSet.Merge(a, b)
13.                         clusterCount--
14.                 }
15.         }
16.     return clusterCount - 1
17. }
20. type UnionSet struct {
21.         parent []int
22. }
24. // 新建一个长度为n的并查集
25. func NewUnionSet(n int) *UnionSet {
26.         parent := make([]int, n)
27.         for i := 0; i < n; i++ {
28.                 parent[i] = -1
29.         }
30.         return &UnionSet{parent: parent}
31. }
33. // FindRoot 找到其所在的集合的根节点
34. func (u *UnionSet) FindRoot(node int) int {
35.         root := node
36.         for u.parent[root] >= 0 {
37.                 root = u.parent[root]
38.         }
39.         return root
40. }
42. // MergeRoot 合并两个集合，传入的应该是集合的根节点
43. func (u *UnionSet) MergeRoot(root1, root2 int) {
44.         if u.parent[root1] < u.parent[root2] {  // 说明root2集合元素更多
45.                 u.parent[root2] += u.parent[root1]
46.                 u.parent[root1] = root2
47.                 return
48.         }
49.         u.parent[root1] += u.parent[root2]
50.         u.parent[root2] = root1
51. }
53. // Merge 合并两个集合
54. func (u *UnionSet) Merge(node1, node2 int) {
55.         root1 := u.FindRoot(node1)
56.         root2 := u.FindRoot(node2)
57.         u.MergeRoot(root1, root2)
58. }
60. func (u *UnionSet) InSame(node1, node2 int) bool {
61.         root1 := u.FindRoot(node1)
62.         root2 := u.FindRoot(node2)
63.         return root1 == root2
64. }

复制代码

LeetCode运行截图如下：

销售代价减少的颜色球

原题描述

LeetCode1648 销售代价减少的颜色球：给定一个表示各个颜色球的库存量，每一个球的代价是买这个球时仓库中剩下的同种球的数量，现在有一笔订单购买M个颜色球，求这笔订单能够得到的最大代价。
思路简述

从贪婪的角度去想，要想代价最大化，肯定是去优先卖库存量最大的颜色球，那么可以按照库存量从大到小排序，对于最大库存量的颜色球，当卖了一些之后，使得其当前库存量即是第二大的，那么这个时候优先去卖这两种颜色球，依次类推，所以一定存在一个初始最小库存量的球i，所有初始库存量大于即是该球库存量的球都会被卖，而所有初始库存量小于该球的都不会卖。只要找到了这个球，就可以计算出来最终的代价。如何去找了，可以用二分查找，具体实现过程参考如下代码。
代码实现

1. func maxProfit(inventory []int, orders int) int {
2.         // 从贪心的角度出发，一定是优先从库存量大的可以取用
3.         // 1. 按照库存从大到小排序
4.         sort.Slice(inventory, func(i, j int) bool {
5.                 return inventory[i] > inventory[j]
6.         })
7.         // 2. 计算前缀和
8.         n := len(inventory)
9.         prefixSum := make([]int64, n)
10.         sum := int64(0)
11.         for i := 0; i < n; i++ {
12.                 sum += int64(inventory[i])
13.                 prefixSum[i] = sum
14.         }
15.         // 3. 基于二分查找找到初始库存量最小的会被取用的序号
16.         low := 0
17.         high := n - 1
18.         for low < high {
19.                 mid := (low + high + 1) / 2
20.                 if prefixSum[mid - 1] - int64(mid) * int64(inventory[mid]) < int64(orders) {
21.                         low = mid
22.                 } else {
23.                         high = mid - 1
24.                 }
25.         }
26.         // 4. 计算初始价值
27.         value := int64(0)
28.         for i := 0; i < low; i++ {
29.                 value += int64(inventory[i] + inventory[low] + 1) * int64(inventory[i] - inventory[low]) / 2
30.                 orders -= (inventory[i] - inventory[low])
31.         }
32.         // 5. 计算剩余价值
33.         k1, k2 := orders / (low + 1), orders % (low + 1)
34.         value += int64(low + 1) * int64(inventory[low] + inventory[low] - k1 + 1) * int64(k1) / 2
35.         value += int64(k2) * int64(inventory[low] - k1)
36.         return int(value % (1e9 + 7))
37. }

复制代码

LeetCode运行截图如下：

复杂度分析

• 时间复杂度：                                        O                            (                            n                            l                            o                            g                            n                            )                                  O(nlogn)                     O(nlogn)
  
• 空间复杂度：                                        O                            (                            n                            )                                  O(n)                     O(n)
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。