leetcode困难题

找到矩阵中的好子集

解：
答案至多选取两行矩阵。
分析：
选取一行矩阵时，floor(c/2)=0，那么必须全为0才能满足。
选取两行矩阵时，floor(c/2)=1，同一列元素不能都是1，也就是相&为0
选取三行矩阵时，floor(c/2)=1，去掉一列后，等同于两行的情况
选取四行时，floor(c/2)=2，假如上述都没有答案：
选取四行中1最少的一行来分析：
1.这一行为10……0，因为上述<4行时都不成立，所以2行时任意两行都不能相&为0，所以其他行第一列必须是1，第一列相加为4，不满足要求
2.这一行为11……0，第二行为10……，第三行为01……为了让第二行与第三行相&不为0，必须在后边的一列都为1，第四行为了与第二行和第三行相&不为0，必须拿出一列使得其与第一行、第二行和第三行都为1，这样算起来就需要6列数据，而题目所说列数小于等于5，所以不满足条件
选取超过四行时，类似方法证明答案不存在

func goodSubsetofBinaryMatrix(grid [][]int) []int {
	n := len(grid)
	if n == 0 {
		return nil
	}
	num := make(map[int]int, n)
	for i, row := range grid {
		mask := 0
		for j, v := range row {
			mask |= v << j
		}
		num[mask] = i
	}
	if v, ok := num[0]; ok {
		return []int{v}
	}
	for i, v := range num {
		for j, v2 := range num {
			if i&j == 0 {
				if v < v2 {
					return []int{v, v2}
				}
				return []int{v2, v}
			}
		}
	}
	return nil
}
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

最长合法子字符串的长度

func longestValidSubstring(word string, forbidden []string) int {
	n := len(word)
	if n == 0 {
		return -1
	}
	vis := make(map[string]struct{}, len(forbidden))
	for _, v := range forbidden {
		vis[v] = struct{}{}
	}
	l := 0
	ans := 0
	for i := 0; i < n; i++ {
		for j := i; j >= l && j >= i-10; j-- {
			if _, ok := vis[word[j:i+1]]; ok {
				l = j + 1
				break
			}
		}
		if i-l+1 > ans {
			ans = i - l + 1
		}
	}
	return ans
}

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

情侣牵手

var f []int

func fin(x int) int {
	if x != f[x] {
		f[x] = fin(f[x])
	}
	return f[x]
}

func union(x, y int) {
	fx, fy := fin(x), fin(y)
	if fx < fy {
		f[fy] = fx
	} else {
		f[fy] = fx
	}
}

func minSwapsCouples(row []int) int {
	n := len(row)
	f = make([]int, n/2)
	for i := 0; i < n/2; i++ {
		f[i] = i
	}
	for i := 0; i < n; i += 2 {
		union(row[i]/2, row[i+1]/2)
	}
	cnt := 0
	for i := 0; i < n/2; i++ {
		if f[i] == i {
			cnt++
		}
	}
	return n/2 - cnt
}

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

我们将 N 对情侣看做图中的 N 个节点；对于每对相邻的位置，如果是第 i 对与第 j 对坐在了一起，则在 i号节点与 j 号节点之间连接一条边，代表需要交换这两对情侣的位置。如果图中形成了一个大小为 k 的环：i→j→k→…→l→i 则我们沿着环的方向，先交换i，j 的位置，再交换 j，k 的位置，以此类推。在进行了 k−1 次交换后，这 k 对情侣就都能够彼此牵手了。

故我们只需要利用并查集求出图中的每个连通分量；对于每个连通分量而言，其大小减 111 就是需要交换的次数。

三个无重叠子数组的最大和

func maxSumOfThreeSubarrays(nums []int, k int) []int {
	sum1, sum2, sum3 := 0, 0, 0
	maxSum1, maxSum2, maxSum3 := 0, 0, 0
	m1_id := 0
	m2_id1, m2_id2 := 0, 0
	m3_id1, m3_id2, m3_id3 := 0, 0, 0
	for i := 2 * k; i < len(nums); i++ {
		sum1 += nums[i-2*k]
		sum2 += nums[i-k]
		sum3 += nums[i]
		if i >= 3*k-1 {
			if sum1 > maxSum1 {
				maxSum1 = sum1
				m1_id = i - 3*k + 1
			}
			if sum2+maxSum1 > maxSum2 {
				maxSum2 = sum2 + maxSum1
				m2_id1, m2_id2 = m1_id, i-2*k+1
			}
			if sum3+maxSum2 > maxSum3 {
				maxSum3 = sum3 + maxSum2
				m3_id1, m3_id2, m3_id3 = m2_id1, m2_id2, i-k+1
			}
			sum1 -= nums[i-3*k+1]
			sum2 -= nums[i-2*k+1]
			sum3 -= nums[i-k+1]
		}
	}
	return []int{m3_id1, m3_id2, m3_id3}
}
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

时间复杂度：O(n)
空间复杂度：O(n)

思想：滑动数组+贪心