企业seo多少费用_桂林网丫网业管理有限公司_深圳网络推广引流_百度pc端入口

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

不相交的线

原题描述

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

思路简述

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

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

代码实现

1. 普通动态规划

func maxUncrossedLines(nums1 []int, nums2 []int) int {m := len(nums1)n := len(nums2)// dp[i][j] 表示nums1[i:] nums2[j:]区域内最大的交叉线数目dp := make([][]int, m + 1)for i := 0; i <= m; i++ {dp[i] = make([]int, n + 1)}for i := m - 1; i >= 0; i-- {for j := n - 1; j >= 0; j-- {dp[i][j] = dp[i + 1][j]// 往前找一个相等的k := jfor k < n && nums2[k] != nums1[i] {k++}if k != n {dp[i][j] = max(dp[i][j], dp[i + 1][k + 1] + 1)}}}return dp[0][0]
}

LeetCode运行截图如下：

2. 优化动态规划

func maxUncrossedLines(nums1 []int, nums2 []int) int {m := len(nums1)n := len(nums2)// dp[i][j] 表示nums1[i:] nums2[j:]区域内最大的交叉线数目dp := make([][]int, m + 1)for i := 0; i <= m; i++ {dp[i] = make([]int, n + 1)}var value2Index map[int]intfor i := m - 1; i >= 0; i-- {value2Index = make(map[int]int)for j := n - 1; j >= 0; j-- {value2Index[nums2[j]] = jdp[i][j] = dp[i + 1][j]if k, ok := value2Index[nums1[i]]; ok {dp[i][j] = max(dp[i][j], dp[i + 1][k + 1] + 1)}}}return dp[0][0]
}

LeetCode运行截图如下：

3. 经典动态规划

func maxUncrossedLines(nums1 []int, nums2 []int) int {m := len(nums1)n := len(nums2)// dp[i][j] 表示nums1[:i] nums2[:j]区域内最大的交叉线数目dp := make([][]int, m+1)for i := 0; i <= m; i++ {dp[i] = make([]int, n+1)}for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])if nums1[i - 1] == nums2[j - 1] {dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)}}}return dp[m][n]
}

LeetCode运行截图如下：

复杂度分析

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

连通网络的最少操作次数

原题描述

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

思路简述

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

代码实现

func makeConnected(n int, connections [][]int) int {m := len(connections)if m < n - 1 {return -1}uSet := NewUnionSet(n)clusterCount := nfor _, conn := range connections {a, b := conn[0], conn[1]if !uSet.InSame(a, b) {uSet.Merge(a, b)clusterCount--}}return clusterCount - 1
}type UnionSet struct {parent []int
}// 新建一个长度为n的并查集
func NewUnionSet(n int) *UnionSet {parent := make([]int, n)for i := 0; i < n; i++ {parent[i] = -1}return &UnionSet{parent: parent}
}// FindRoot 找到其所在的集合的根节点
func (u *UnionSet) FindRoot(node int) int {root := nodefor u.parent[root] >= 0 {root = u.parent[root]}return root
}// MergeRoot 合并两个集合，传入的应该是集合的根节点
func (u *UnionSet) MergeRoot(root1, root2 int) {if u.parent[root1] < u.parent[root2] {  // 说明root2集合元素更多u.parent[root2] += u.parent[root1]u.parent[root1] = root2return} u.parent[root1] += u.parent[root2]u.parent[root2] = root1
}// Merge 合并两个集合
func (u *UnionSet) Merge(node1, node2 int) {root1 := u.FindRoot(node1)root2 := u.FindRoot(node2)u.MergeRoot(root1, root2)
}func (u *UnionSet) InSame(node1, node2 int) bool {root1 := u.FindRoot(node1)root2 := u.FindRoot(node2)return root1 == root2
}

LeetCode运行截图如下：

销售价值减少的颜色球

原题描述

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

思路简述

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

代码实现

func maxProfit(inventory []int, orders int) int {// 从贪心的角度出发，一定是优先从库存量大的可以取用// 1. 按照库存从大到小排序sort.Slice(inventory, func(i, j int) bool {return inventory[i] > inventory[j]})// 2. 计算前缀和n := len(inventory)prefixSum := make([]int64, n)sum := int64(0)for i := 0; i < n; i++ {sum += int64(inventory[i])prefixSum[i] = sum}// 3. 基于二分查找找到初始库存量最小的会被取用的序号low := 0high := n - 1for low < high {mid := (low + high + 1) / 2if prefixSum[mid - 1] - int64(mid) * int64(inventory[mid]) < int64(orders) {low = mid} else {high = mid - 1}}// 4. 计算初始价值value := int64(0)for i := 0; i < low; i++ {value += int64(inventory[i] + inventory[low] + 1) * int64(inventory[i] - inventory[low]) / 2orders -= (inventory[i] - inventory[low])}// 5. 计算剩余价值k1, k2 := orders / (low + 1), orders % (low + 1)value += int64(low + 1) * int64(inventory[low] + inventory[low] - k1 + 1) * int64(k1) / 2value += int64(k2) * int64(inventory[low] - k1)return int(value % (1e9 + 7))
}

LeetCode运行截图如下：

复杂度分析

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$