# 第 73 场双周赛题解
# Q1 2190. 数组中紧跟 key 之后出现最频繁的数字 (opens new window)
模拟。
class SolutionA {
fun mostFrequent(nums: IntArray, key: Int): Int {
val map = HashMap<Int, Int>()
for (i in 0 until nums.lastIndex) {
if (nums[i] == key) {
map[nums[i + 1]] = map.getOrDefault(nums[i + 1], 0) + 1
}
}
return map.maxByOrNull { it.value }!!.key
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# Q2 2191. 将杂乱无章的数字排序 (opens new window)
利用sortBy可以很容易的转化。
class SolutionB {
fun sortJumbled(mapping: IntArray, nums: IntArray): IntArray {
val list = nums.sortedBy {
var ans = 0
it.toString().forEach {
ans *= 10
ans += mapping[(it - '0')]
}
ans
}
return list.toIntArray()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# Q3 5300. 有向无环图中一个节点的所有祖先 (opens new window)
反向建图即可。再根据每个点的最短路径确定是否可达,输出结果即可。时间复杂度。
class SolutionC {
fun getAncestors(n: Int, edges: Array<IntArray>): List<List<Int>> {
val g = Graph(n)
edges.forEach {
g.addEdgeOri(it[1], it[0], 1)
}
val ans = ArrayList<ArrayList<Int>>()
for (i in 0 until n) {
val tmp = ArrayList<Int>()
g.dijkstra(i).forEachIndexed { index, l ->
if (l > 0 && l < Int.MAX_VALUE) {
tmp.add(index)
}
}
ans.add(tmp)
}
return ans
}
}
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
# Q4 2193. 得到回文串的最少操作次数 (opens new window)
贪心的来处理,从左到右依次遍历,每遇到一个字母,需要从右侧对应位置,逆序找到对应的字母,然后距离就是需要增加的交换值。对于奇数(右侧一直找到左侧自己的Case),直接与后一个元素交换即可,这样可以一步步把当前元素移动到中间。
class SolutionD {
fun minMovesToMakePalindrome(s: String): Int {
val n = s.length
var l = 0
val sb = ArrayList<Char>()
sb.addAll(s.toCharArray().toList())
var ans = 0
while (l < n / 2) {
var r = s.lastIndex - l
var tmp = 0
while (sb[l] != sb[r]) {
r--
tmp++
}
if (l == r) {
sb.swap(l, l + 1)
ans++
} else {
sb.removeAt(r)
sb.add(sb[l])
ans += tmp
l++
}
}
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
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