2022-03-05：不相交的线。 在两条独立的水平线上按给定的顺序写下 nums1

2022-03-05：不相交的线。 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足： nums1[i] == nums2[j] 且绘制的直线不与任何其他连线（非水平线）相交。 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。 以这种方法绘制线条，并返回可以绘制的最大连线数。 输入：nums1 = [1,4,2], nums2 = [1,2,4]。 输出：2。 解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。 力扣1035。

答案2022-03-05：

求最长公共子序列。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	if true {
		A := []int{1, 4, 2}
		B := []int{1, 2, 4}
		ret := maxUncrossedLines1(A, B)
		fmt.Println(ret)
	}
	if true {
		A := []int{1, 4, 2}
		B := []int{1, 2, 4}
		ret := maxUncrossedLines2(A, B)
		fmt.Println(ret)
	}
}

// 针对这个题的题意，做的动态规划
func maxUncrossedLines1(A, B []int) int {
	if len(A) == 0 || len(B) == 0 {
		return 0
	}
	N := len(A)
	M := len(B)
	// dp[i][j]代表: A[0...i]对应B[0...j]最多能划几条线
	dp := make([][]int, N)
	for i := 0; i < N; i++ {
		dp[i] = make([]int, M)
	}
	if A[0] == B[0] {
		dp[0][0] = 1
	}
	for j := 1; j < M; j++ {
		dp[0][j] = twoSelectOne(A[0] == B[j], 1, dp[0][j-1])
	}
	for i := 1; i < N; i++ {
		dp[i][0] = twoSelectOne(A[i] == B[0], 1, dp[i-1][0])
	}
	// 某个值(key)，上次在A中出现的位置(value)
	AvalueLastIndex := make(map[int]int)
	AvalueLastIndex[A[0]] = 0
	// 某个值(key)，上次在B中出现的位置(value)
	BvalueLastIndex := make(map[int]int)
	for i := 1; i < N; i++ {
		AvalueLastIndex[A[i]] = i
		BvalueLastIndex[B[0]] = 0
		for j := 1; j < M; j++ {
			BvalueLastIndex[B[j]] = j
			// 可能性1，就是不让A[i]去划线
			p1 := dp[i-1][j]
			// 可能性2，就是不让B[j]去划线
			p2 := dp[i][j-1]
			// 可能性3，就是要让A[i]去划线，那么如果A[i]==5，它跟谁划线？
			// 贪心的点：一定是在B[0...j]中，尽量靠右侧的5
			p3 := 0
			if _, ok := BvalueLastIndex[A[i]]; ok {
				last := BvalueLastIndex[A[i]]
				p3 = twoSelectOne(last > 0, dp[i-1][last-1], 0) + 1
			}
			// 可能性4，就是要让B[j]去划线，那么如果B[j]==7，它跟谁划线？
			// 贪心的点：一定是在A[0...i]中，尽量靠右侧的7
			p4 := 0
			if _, ok := AvalueLastIndex[B[j]]; ok {
				last := AvalueLastIndex[B[j]]
				p4 = twoSelectOne(last > 0, dp[last-1][j-1], 0) + 1
			}
			dp[i][j] = getMax(getMax(p1, p2), getMax(p3, p4))
		}
		BvalueLastIndex = make(map[int]int)
	}
	return dp[N-1][M-1]
}

// 但是其实这个题，不就是求两个数组的最长公共子序列吗？
func maxUncrossedLines2(A, B []int) int {
	if len(A) == 0 || len(B) == 0 {
		return 0
	}
	N := len(A)
	M := len(B)
	dp := make([][]int, N)
	for i := 0; i < N; i++ {
		dp[i] = make([]int, M)
	}
	dp[0][0] = twoSelectOne(A[0] == B[0], 1, 0)
	for j := 1; j < M; j++ {
		dp[0][j] = twoSelectOne(A[0] == B[j], 1, dp[0][j-1])
	}
	for i := 1; i < N; i++ {
		dp[i][0] = twoSelectOne(A[i] == B[0], 1, dp[i-1][0])
	}
	for i := 1; i < N; i++ {
		for j := 1; j < M; j++ {
			p1 := dp[i-1][j]
			p2 := dp[i][j-1]
			p3 := twoSelectOne(A[i] == B[j], 1+dp[i-1][j-1], 0)
			dp[i][j] = getMax(p1, getMax(p2, p3))
		}
	}
	return dp[N-1][M-1]
}

func twoSelectOne(c bool, a, b int) int {
	if c {
		return a
	} else {
		return b
	}
}

func getMax(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

执行结果如下：

左神java代码