# 第 53 场双周赛题解
# Q1 1876. 长度为三且各字符不同的子字符串 (opens new window)
直接硬暴力遍历。
时间复杂度:
class Solution1876 {
fun countGoodSubstrings(s: String): Int {
var ans = 0
for (i in 0 until s.length - 2) {
if (s[i] != s[i + 1] && s[i + 1] != s[i + 2] && s[i] != s[i + 2])
ans++
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# Q2 1877. 数组中最大数对和的最小值 (opens new window)
可以贪心的做,每次匹对取一个最大值和一个最小值。
时间复杂度:
class Solution1877 {
fun minPairSum(nums: IntArray): Int {
nums.sort()
var ans = 0
for (i in nums.indices) {
ans = maxOf(ans, nums[i] + nums[nums.lastIndex - i])
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# Q3 1878. 矩阵中最大的三个菱形和 (opens new window)
本题还算简单,就是写起来很麻烦...理解时还以为只算四个角的和,怒吃一个WA才发现不对了...
直接枚举所有情况,然后把和入到一个或其他排序方案即可。
时间复杂度:
class Solution1878 {
fun getBiggestThree(grid: Array<IntArray>): IntArray {
val m = grid.size
val n = grid[0].size
fun valid(z: Pair<Int, Int>): Boolean {
return z.first in 0 until m && z.second in 0 until n
}
val ts = TreeSet<Int>()
fun cal(x1: Pair<Int, Int>, k: Int) {
val set = HashSet<Pair<Int, Int>>()
set.add(x1)
for (i in 0..k) {
set.add(Pair(x1.first + i, x1.second + i))
set.add(Pair(x1.first + i, x1.second - i))
set.add(Pair(x1.first + i + k, x1.second - k + i))
set.add(Pair(x1.first + i + k, x1.second + k - i))
}
var t = 0
set.forEach {
t += grid[it.first][it.second]
}
ts.add(t)
}
for (i in 0 until m) {
for (j in 0 until n) {
for (k in 0 until maxOf(m, n)) {
val x1 = Pair(i, j)
val x2 = Pair(i + k, j + k)
val x3 = Pair(i + k, j - k)
val x4 = Pair(i + 2 * k, j)
if (valid(x1) && valid(x2) && valid(x3) && valid(x4)) {
cal(x1, k)
}
}
}
}
val ans = ArrayList<Int>()
while (ans.size != 3 && ts.isNotEmpty()) {
ans.add(ts.pollLast())
}
return ans.toIntArray()
}
}
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
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
# Q4 1879. 两个数组最小的异或值之和 (opens new window)
这道题看到异或值直接想偏了,用字典树处理想着如何贪心判断,最后发现不对...
数组长度,则可以向的复杂度考虑。使用状态压缩 + 动态规划求出所有可能的最优解。类似于题目1723. 完成所有工作的最短时间 (opens new window),将第一个数组看做工人,第二个数组看做工作,而其工作时间使用的是异或操作。
// 二进制 状态压缩
class Solution5756 {
fun minimumXORSum(nums1: IntArray, nums2: IntArray): Int {
val n = nums1.size
val dp = Array<IntArray>(n + 1) { IntArray(1 shl n) { Int.MAX_VALUE } }
dp[0][0] = 0
for (i in 1..n) {
for (j in 1..(1 shl n)) {
for (k in 0 until n) {
if (j and (1 shl k) != 0) {
// j xor (1 shl k) 回退到nums2未选择k的状态
dp[i][j] = minOf(dp[i][j], dp[i - 1][j xor (1 shl k)] + (nums2[k] xor nums1[i - 1]))
}
}
}
}
return dp[n][(1 shl n) - 1]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
还看到大神们有其他的两种解法,学习一下。
# 二分图KM完美匹配
OIWiki 二分图最大权匹配 (opens new window)
GeeksForGeeks Maximum Bipartite Matching (opens new window)
首先学习几个定义:
- 二分图:图中所有边的顶点可以分为两组,两组内无组内的边
- 完美匹配:每一个顶点只有一条边并相连到另一组顶点中
这个算法可以将矩阵任务一对一的完美分配,如个人完成个任务,但每个人完成人的的耗时或效果不同等,可以求任意要求的最大最小值。
利用该算法,将图中边的权重设置为异或值的取负数,即可算得最小值。
class Solution5756 {
// 二分图 最大权匹配
fun minimumXORSum(nums1: IntArray, nums2: IntArray): Int {
val n = nums1.size
val graph = Graph(2 * n)
for (i in 0 until n) {
for (j in 0 until n) {
// Init Graph with weight
graph.addEdge(i, n + j, -(nums1[i] xor nums2[j]))
}
}
return -graph.km()
}
}
class Graph(val n: Int) {
// 图中边(可以有方向)
var adj: Array<LinkedList<Int>> = Array(n) { LinkedList<Int>() }
// 图中边的权重(可以有方向)
val weight = HashMap<Int, HashMap<Int, Int>>()
init {
for (i in 0 until n) {
weight[i] = hashMapOf()
}
}
fun addEdgeOri(i: Int, j: Int, w: Int = 0) {
adj[i].add(j)
weight[i]!![j] = w
}
fun addEdge(i: Int, j: Int, w: Int = 0) {
// Add w to v's list.
adj[i].add(j)
// Add v to w's list
adj[j].add(i)
weight[i]!![j] = w
weight[j]!![i] = w
}
}
/**
* 参考资料
* http://elmagnifico.tech/2018/01/24/BipartiteGraph-Max-Weight/
* https://www.cnblogs.com/fzl194/p/8834847.html
*
* 二分图带权最大匹配
* */
fun Graph.km(): Int {
// n为总点数,m为两个分组的点的数量
val m = n / 2
val match = IntArray(m) { -1 }
val lval = IntArray(m)
val rval = IntArray(m)
for (i in 0 until m) {
// 使用右侧第一个点初始化左侧集合值)
lval[i] = weight[i]!![m]!!
for (j in m + 1 until n) {
// 最大化可行顶标
lval[i] = maxOf(lval[i], weight[i]!![j]!!)
}
}
// 左右点集合访问状态
val ls = BooleanArray(m)
val rs = BooleanArray(m)
fun dfs(u: Int): Boolean {
ls[u] = true
for (v in 0 until m) {
if (!rs[v] && lval[u] + rval[v] == weight[u]!![v + m]) {
rs[v] = true
if (match[v] == -1 || dfs(match[v])) {
match[v] = u
return true
}
}
}
return false
}
// 遍历左顶点,寻找最大匹配
for (u in 0 until m) {
while (true) {
// 清空之前的状态
ls.fill(false)
rs.fill(false)
if (dfs(u)) break
var d = Int.MAX_VALUE
for (i in 0 until m)
if (ls[i])
for (j in 0 until m)
if (!rs[j])
d = minOf(d, lval[i] + rval[j] - weight[i]!![m + j]!!)
// 更新顶点权值,直到完美匹配
for (i in 0 until m) {
if (ls[i])
lval[i] -= d
if (rs[i])
rval[i] += d
}
}
}
var res = 0
for (i in 0 until m) {
res += weight[match[i]]!![i + m]!!
}
return res
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# 玄学退火算法(Simulated Annealing)
还有一种利用随机算法模拟最优解的玄学算法。针对总解数范围不大的题目可以尝试用该方案。经验大概可以支持到长度为以下的数组随机排序。
1815. 得到新鲜甜甜圈的最多组数 (opens new window) 该题也可以使用退火算法
import kotlin.math.exp
class Solution5756 {
// 模拟退火算法 玄学
// Simulated annealing
fun minimumXORSum(nums1: IntArray, nums2: IntArray): Int {
val eps = 1e-5
val delta = 0.98
var ans = Int.MAX_VALUE
val n = nums1.size
fun getSum(): Int {
var cur = 0
for (i in nums1.indices) {
cur += nums1[i] xor nums2[i]
}
ans = minOf(ans, cur)
return cur
}
fun sa() {
var t = 1e6
while (t > eps) {
val x: Int = (0 until n).random()
val y: Int = (0 until n).random()
val last: Int = getSum()
nums2.swap(x, y)
val now: Int = getSum()
val diff = now - last
// 取最小值
if (diff > 0 && exp(-1.0 * diff / t) * n <= (0 until n).random()) {
// 还原操作
nums2.swap(x, y)
}
t *= delta
}
}
repeat(20) {
sa()
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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