【LeetCode 1035】不相交的线_code1035

/*
难度：中等
在两条独立的水平线上按给定顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字nums1[i]和nums2[j]的直线，这些直线需要满足：
1）nums1[i] == nums2[j]；
2）绘制的直线不与任何其他连线（非水平线）相交；
注意：连线即使在端点也不能相交；每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。

> 示例：
> 输入：nums1 = [1, 4, 2]， nums2 = [1, 2, 4]
> 输出：2

提示:
1 <= nums1.length <= 500
1 <= nums2.length <= 500
1 <= nums1[i], nums2[i] <= 2000
*/
extension Daily {
	static func test_leetCode1035() {
//		let nums2 = [1, 2, 4]
//		let nums1 = [1, 4, 2] 
		let nums1 = [5,1,2,5,1,2,2,3,1,1,1,1,1,3,1]
		let nums2 = [2,5,1,3,4,5,5,2,2,4,5,2,2,3,1,4,5,3,2,4,5,2,4,4,2,2,2,1,3,1]
		
		let start = NSDate.now
		print("开始时间 \(NSDate.now)")
		let res = Daily.leetCode1035(nums1: nums1, nums2: nums2)
		let end = NSDate.now
		print("耗时 \(end.timeIntervalSince(start))")
		print("最终结果 \(res)")
	}
	//
	static func leetCode1035(nums1: [Int], nums2: [Int]) -> Int {
		if nums1.count < 1 || nums2.count < 1 {
			return 0
		}
		
		let little = nums1.count < nums2.count ? nums1 : nums2; //元素个数较小的那个
		let large = nums1.count < nums2.count ? nums2 : nums1;//元素个数较多的那个
		
		var idxmap = Array(repeating: Int16(-1), count: little.count * large.count)
		var dic = [Int:Int16]()
		for idx in 0..<large.count {
			dic[large[idx]] = Int16(idx)
			for lidx in 0..<little.count {
				idxmap[lidx*large.count + idx] = dic[little[lidx]] ?? -1 
			}
		}
		
		let rows = little.count + 1
		let cols = large.count + 1
		let msize = rows * cols
		var map = Array(repeating: Int16(0), count: msize)
		
		for arow in 1..<rows {
			for acol in 1..<cols {
				let top = (arow-1)*cols + acol
				var	include:Int16 = 0
				let maxidx = Int(idxmap[top - arow])
				if maxidx >= 0 {
					include = 1 + map[top - acol + maxidx]
				}
				map[top + cols] = max(map[top], include)
			}
		}		
		return Int(map[msize - 1])
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69