算法编程题-不相交的线 联通网络的操作次数 销售价值减少的颜色球

不相交的线

原题描述

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 := j
			for 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]int
	for i := m - 1; i >= 0; i-- {
		value2Index = make(map[int]int)
		for j := n - 1; j >= 0; j-- {
			value2Index[nums2[j]] = j
			dp[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 := n

	for _, 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 := node
	for 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] = root2
		return
	} 
	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 := 0
	high := n - 1
	for low < high {
		mid := (low + high + 1) / 2
		if 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]) / 2
		orders -= (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) / 2
	value += int64(k2) * int64(inventory[low] - k1)
	return int(value % (1e9 + 7))
}

LeetCode运行截图如下：

复杂度分析

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