共计 5773 个字符,预计需要花费 15 分钟才能阅读完成。
本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 发问。
大家好,我是小彭。
上周末是 LeetCode 第 339 场周赛,你加入了吗?这场周赛笼罩的知识点比拟少,前三题很简略,第四题上难度。
周赛纲要
2609. 最长均衡子字符串(Easy)
- 模仿:$O(n)$
2610. 转换二维数组(Medium)
- 贪婪:$O(n)$
2611. 老鼠和奶酪(Medium)
- 排序 + 贪婪:$O(nlgn)$
2612. 起码翻转操作数(Hard)
- 题解一:拓扑排序 · 超出工夫限度 $O(nk)$
- 题解二:BFS + 均衡二叉树 $O(nlgn)$
2609. 最长均衡子字符串(Easy)
题目地址
https://leetcode.cn/problems/find-the-longest-balanced-substr…
题目形容
给你一个仅由 0
和 1
组成的二进制字符串 s
。
如果子字符串中 所有的 0
都在 1
之前 且其中 0
的数量等于 1
的数量,则认为 s
的这个子字符串是均衡子字符串。请留神,空子字符串也视作均衡子字符串。
返回 s
中最长的均衡子字符串长度。
子字符串是字符串中的一个间断字符序列。
题解(模仿)
简略模拟题。
保护间断 0 的计数 cnt0
和间断 1 的计数 cnt1
,并在 cnt0 == cnt1
时更新最长均衡子串长度为 2 * cnt1
。另外,在每段 0 的起始地位从新计数。
class Solution {fun findTheLongestBalancedSubstring(s: String): Int {
var index = 0
var cnt0 = 0
var cnt1 = 0
var ret = 0
while (index < s.length) {if (s[index] == '0') {
// 每段 0 的起始地位清零
if (index > 0 && s[index - 1] == '1') {
cnt0 = 0
cnt1 = 0
}
cnt0++
} else {cnt1++}
if (cnt1 <= cnt0) ret = Math.max(ret, cnt1 * 2)
index++
}
return ret
}
}
复杂度剖析:
- 工夫复杂度:$O(n)$ 其中 $n$ 为 $nums$ 数组的长度;
- 空间复杂度:$O(1)$ 仅应用常数级别变量。
2610. 转换二维数组(Medium)
题目地址
https://leetcode.cn/problems/convert-an-array-into-a-2d-array…
题目形容
给你一个整数数组 nums
。请你创立一个满足以下条件的二维数组:
- 二维数组应该 只 蕴含数组
nums
中的元素。 - 二维数组中的每一行都蕴含 不同 的整数。
- 二维数组的行数应尽可能 少。
返回后果数组。如果存在多种答案,则返回其中任何一种。
请留神,二维数组的每一行上能够存在不同数量的元素。
题解(贪婪)
贪婪思路:首先计算每个元素的呈现次数,为了防止同一行的反复,将反复元素从上到下排列到不同行中。
优化:能够在一次遍历中实现,在呈现更大呈现次数时减少一行,在更新元素技术 cnt 后插入到第 cnt – 1 行。
class Solution {fun findMatrix(nums: IntArray): List<List<Int>> {val cnts = IntArray(201)
val ret = LinkedList<LinkedList<Int>>()
var maxCnt = 0
// 计数
for (num in nums) {
// 累加
val curCnt = ++cnts[num]
// 创立新行
if (curCnt > maxCnt) {
maxCnt = curCnt
ret.add(LinkedList<Int>())
}
// 散布
ret[curCnt - 1].add(num)
}
return ret
}
}
复杂度剖析:
- 工夫复杂度:$O(n)$ 其中 $n$ 为 $nums$ 数组的长度,每个元素拜访一次;
- 空间复杂度:$O(U)$ 计数数组空间。
2611. 老鼠和奶酪(Medium)
题目地址
https://leetcode.cn/problems/mice-and-cheese/
题目形容
有两只老鼠和 n
块不同类型的奶酪,每块奶酪都只能被其中一只老鼠吃掉。
下标为 i
处的奶酪被吃掉的得分为:
- 如果第一只老鼠吃掉,则得分为
reward1[i]
。 - 如果第二只老鼠吃掉,则得分为
reward2[i]
。
给你一个正整数数组 reward1
,一个正整数数组 reward2
,和一个非负整数 k
。
请你返回第一只老鼠恰好吃掉 k
块奶酪的状况下,最大 得分为多少。
题解(排序 + 贪婪)
容易了解:为了使最终得分最大,应该让每只老鼠吃到尽可能大的奶酪。
因为两只老鼠吃的奶酪是互斥关系,因而咱们能够先假如所有奶酪被第一只老鼠食得,而后再筛选 n - k
个奶酪还给第二只老鼠。
那么,对于每个地位 i
,将奶酪从第一只老鼠还给第二只老鼠存在差值 diff = reward2[i] - reward1[i]
,示意得分的差值为 diff
。差值为正得分变大,差值为负得分升高,显然升高越少越好。
因而,咱们的算法是对 diff
排序,将得分升高越大的地位保留给第一只老鼠,其余还给第二只老鼠。
class Solution {fun miceAndCheese(reward1: IntArray, reward2: IntArray, k: Int): Int {
// 贪婪:优先选择差值最大的地位
val n = reward1.size
var ret = 0
val indexs = Array(n) {it}
// 升序
Arrays.sort(indexs) { i1, i2 ->
(reward2[i1] - reward1[i1]) - (reward2[i2] - reward1[i2])
}
for (i in 0 until n) {ret += if (i < k) {reward1[indexs[i]]
} else {reward2[indexs[i]]
}
}
return ret
}
}
复杂度剖析:
- 工夫复杂度:$O(nlgn + n)$ 其中 $n$ 为 $nums$ 数组的长度;
- 空间复杂度:$O(n + lgn)$ 索引数组和递归栈空间。
2612. 起码翻转操作数(Hard)
题目地址
https://leetcode.cn/problems/minimum-reverse-operations/
题目形容
给你一个整数 n
和一个在范畴 [0, n - 1]
以内的整数 p
,它们示意一个长度为 n
且下标从 0 开始的数组 arr
,数组中除了下标为 p
处是 1
以外,其余所有数都是 0
。
同时给你一个整数数组 banned
,它蕴含数组中的一些地位。banned
中第 i 个地位示意 arr[banned[i]] = 0
,题目保障 banned[i] != p
。
你能够对 arr
进行 若干次 操作。一次操作中,你抉择大小为 k
的一个 子数组 ,并将它 翻转 。在任何一次翻转操作后,你都须要确保 arr
中惟一的 1
不会达到任何 banned
中的地位。换句话说,arr[banned[i]]
始终 放弃 0
。
请你返回一个数组 ans
,对于 [0, n - 1]
之间的任意下标 i
,ans[i]
是将 1
放到地位 i
处的 起码 ** 翻转操作次数,如果无奈放到地位 i
处,此数为 -1
。
- 子数组 指的是一个数组里一段间断 非空 的元素序列。
- 对于所有的
i
,ans[i]
相互之间独立计算。 - 将一个数组中的元素 翻转 指的是将数组中的值变成 相同程序。
题解一(拓扑排序 · 超出工夫限度)
剖析 1:对于翻转窗口 [L, R] 中的地位 i,翻转后的下标为 $\frac{L+R}{2} +(\frac{L+R}{2} – i) = L + R – i$
剖析 2:首先地位 p
的翻转次数恒等于 0,而 banned
数组示意的地位翻转次数恒等于 -1。
剖析 3:当地位 i
位于翻转窗口的左半局部时,将翻转到更大地位;当地位 i
位于翻转窗口的右半局部时,将翻转到更小地位;
剖析 4:当初咱们须要剖析地位 i
(初始 i 为 0)能够翻转到的地位:
-
状况 1:如果将
i
作为翻转窗口的左右边界,则有:- 位于左边界时,翻转后的下标为
i + k - 1
; - 位于有边界时,翻转后的下标为
i - k + 1
。
- 位于左边界时,翻转后的下标为
- 状况 2:如果将 i 放在翻转窗口外部,则所有翻转后的下标正好形成差值为
2
的等差数列。
因而,i 能够翻转的区间为 [i – k + 1, i + k – 1] 中距离 2 的地位(排除 banned 数组),或者了解为奇偶性雷同的下标。
剖析 5:因为翻转窗口有地位限度,会限度翻转:
- 窗口左边界在地位
0
时,且i
位于翻转窗口的右半局部时(筹备向左翻),则翻转后的地位是0 + (k - 1) - i = k - 1 - i
。因为窗口无奈持续左移,所以小于k - i - 1
的地位都不可达; - 同理,窗口右边界位于
n - 1
时,且i
位于翻转窗口的右边局部时(筹备向右翻),则翻转后的地位是(n - k) + (n - 1) - i = 2n - k - i - 1
。因为窗口无奈持续右移,所以大于2n - k - i - 1
的地位都不可达。
综上,可得翻转后区间为 [max(i – k + 1, k – i – 1), min(i + k – 1, 2n – k – i – 1)] 中与 i 奇偶性雷同的地位。
至此,容易发现问题能够用拓扑排序(BFS 写法)解决:初始时将 p 地位入队,随后每一轮的翻转次数 + 1,并将该地位入队。
class Solution {fun minReverseOperations(n: Int, p: Int, banned: IntArray, k: Int): IntArray {val ret = IntArray(n) {-1}
// 初始位
ret[p] = 0
// 禁止位
val bannedSet = banned.toHashSet()
// BFS(最小跳转索引)val queue = LinkedList<Int>()
queue.offer(p)
while (!queue.isEmpty()) {val i = queue.poll()!!
val min = Math.max(i - k + 1, k - i - 1)
val max = Math.min(i + k - 1, 2 * n - k - i - 1)
val curStep = ret[i] + 1
for (j in min..max step 2) {
// 不可达
if (bannedSet.contains(j)) continue
// 已拜访
if (ret[j] != -1) continue
// 可达
ret[j] = curStep
// 入队
queue.offer(j)
}
}
return ret
}
}
复杂度剖析:
- 工夫复杂度:$O(n·k)$ 每个元素最多拜访 1 次,且每轮最多须要拜访 $k$ 个元素。
- 空间复杂度:$O(n)$ 队列的长度最大为 $n$。
题解二(BFS + 均衡二叉树)
在题解一中,当 k
比拟大时每轮 BFS 中会反复判断曾经被标记过的地位,如何防止呢?咱们能够提前将所有下标退出到散列表中,在每次标记后将下标从散列表移除,这样能防止反复拜访曾经标记过的地位。
其次,因为每轮中须要标记的区间位于 [min, max]
,那么咱们能够将散列表降级为基于均衡二叉树的 TreeSet,以便在 O(lgn) 工夫内找到区间中的元素。具体形式是寻找树中大于等于 min
的最小元素(且小于等于 max
),将其标记和移除。
最初,因为偶数下标和奇数下标是离开的,所以须要建设两个均衡二叉树。
class Solution {fun minReverseOperations(n: Int, p: Int, banned: IntArray, k: Int): IntArray {val ret = IntArray(n) {-1}
// 初始位
ret[p] = 0
// 禁止位
val bannedSet = banned.toHashSet()
// 均衡二叉树
val sets = Array(2) {TreeSet<Int>() }
for (i in 0 until n) {if (i != p && !bannedSet.contains(i)) sets[i % 2].add(i)
}
// BFS(最小跳转索引)val queue = LinkedList<Int>()
queue.offer(p)
while (!queue.isEmpty()) {val i = queue.poll()!!
val min = Math.max(i - k + 1, k - i - 1)
val max = Math.min(i + k - 1, 2 * n - k - i - 1)
val curStep = ret[i] + 1
// 依据左端点确定奇偶性(右端点也行)val set = sets[min % 2]
// 枚举均衡树中的 [min,max] 区间
while (true) {val index = set.ceiling(min) ?: break // 大于等于 min 的最小键值
if (index > max) break
// 标记并删除
set.remove(index)
ret[index] = curStep
// 入队
queue.offer(index)
}
}
return ret
}
}
复杂度剖析:
- 工夫复杂度:$O(nlgn + nlgn)$ 建均衡树为 $O(nlgn)$,BFS 中每个元素最多删除一次,每轮须要 $O(lgn)$ 工夫找到左边界,整体是 $O(nlgn)$;
- 空间复杂度:$O(n)$ 均衡二叉树空间。
<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:16px;”> 点击上方按钮关注 </span>
<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:16px;”> 每周继续原创更新 </span>
<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:16px;”> 与你一起深度思考 </span>
<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:18px;”>The End</span>
<span style=”display:block;text-align:center;color:black;font-size:12px;”>—— 我 们 下 次 见 ——</span>