本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。
- LeetCode 单周赛第 345 场 · 体验一题多解的算法之美
单周赛 345 概览
T1. 删除子串后的字符串最小长度(Easy)
标签:栈
T2. 字典序最小回文串(Medium)
标签:贪心、双指针
T3. 求一个整数的惩罚数(Medium)
标签:回溯、状态压缩、前缀和
T4. 修改图中的边权(Hard)
标签:贪心、最短路
T1. 删除子串后的字符串最小长度(Easy)
https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/
题解(栈)
使用栈模拟扫描过程,当扫描到 D
和 B
时检查栈顶元素,最后栈内剩余的元素个数就是无法消除的最小长度:
class Solution {
fun minLength(s: String): Int {
val stack = ArrayDeque()
for (c in s) {
if (c == 'D' && stack.isNotEmpty() && stack.peek() == 'C') stack.pop()
else if (c == 'B' && stack.isNotEmpty() && stack.peek() == 'A') stack.pop()
else stack.push(c)
}
return stack.size
}
}
复杂度分析:
- 时间复杂度:$O(n)$ 其中 n 为 s 字符串的长度;
- 空间复杂度:$O(n)$ 栈空间。
T2. 字典序最小回文串(Medium)
https://leetcode.cn/problems/lexicographically-smallest-palindrome/
题解(贪心)
贪心思路:当对称位置不相等时,只需要将其中一个位置修改到与另一个位置相同时,得到的操作次数是最少的:
class Solution {
fun makeSmallestPalindrome(s: String): String {
val arr = s.toCharArray()
val n = s.length
// 判断回文串写法
for (i in 0 until n / 2) {
val j = n - 1 - i
if(arr[i] != arr[j]) {
val temp = if(arr[i]
复杂度分析:
- 时间复杂度:$O(n)$ 其中 n 为 s 字符串的长度;
- 空间复杂度:$O(n)$ 字符数组空间。
T3. 求一个整数的惩罚数(Medium)
https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/
题解一(子集型回溯)
枚举每个数,使用子集型回溯检查是否存在满足条件的切分方案:
class Solution {
fun punishmentNumber(n: Int): Int {
if (n
复杂度分析:
- 时间复杂度:$O(n^2)$ 每个数字 i 转字符串后的长度为 $log_i$,而枚举长度为 $log_i$ 的字符串的切分方案后 $2^{log_i}$ = i 种方案,因此整体的时间复杂度是 $O(n^2)$;
- 空间复杂度:$O(lgn)$ 递归栈空间。
题解二(状态压缩)
由于数字的长度小于 32,我们可以用 int 表示所有切分方案,再检查是否存在满足条件的切分方案:
class Solution {
fun punishmentNumber(n: Int): Int {
if (n
复杂度分析:
- 时间复杂度:同上;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
题解三(预处理 + 前缀和)
题解一和题解二在多个测试用例间会重复计算相同数字的切分方案,我们可以预处理 1 – 1000 中所有满足条件的数平方,并维护前缀和数组:
class Solution {
companion object {
private val U = 1000
private val preSum = IntArray(U + 1)
init {
for (x in 4 .. U) {
val target = x * x
if (check("$target", x)) preSum[x] += target
preSum[x] += preSum[x - 1]
}
}
// 状态压缩
private fun check(str : String, target : Int) : Boolean {
}
}
fun punishmentNumber(n: Int): Int {
return preSum[n] + 1
}
}
复杂度分析:
- 时间复杂度:$O(U^2)$ 其中 U 是数据大小上界;
- 空间复杂度:$O(U)$ 前缀和数组空间。
T4. 修改图中的边权(Hard)
https://leetcode.cn/problems/modify-graph-edge-weights/submissions/434224996/
LeetCode 少有的难题,排进历史 Top 10 没问题吧?
问题无解的情况:
- 1、假设将所有负权边设置为 INF(2*10^9)时的最短路长度 dis
- 2、假设将所有负权边设置为 1 时的最短路长度 dis > target(不论是否经过负权边),由于继续增大边权最短路不可能变小,因此问题无解。
错误的思路:
先把所有负权边设置为 1,再跑 Dijkstra 最短路,如果最短路长度 dis
正确的思路:
- 1、先把所有负权边改为 1 跑 Dijkstra 最短路,计算出起点到终点的最短路长度。同时,如果该长度 dis > target,则问题无解;如果该长度 dis == target,则直接返回;如果该长度 dis
- 2、问题的关键在于,按什么顺序修改,以及修改到什么值。
- 顺序:利用 Dijkstra 最短路算法每次使用「确定集」中最短路长度最短的节点去松弛其他点的时机,由于修改该点不会影响已确定路径,因此这是一个不错的时机;
- 修改到什么值:需要满足 dis[0][x] + w + dis[y][e] = target,那么有 w = target – dis[0][x] – (dis[0][e] – dis[0][y]) = delta – dis[0][x] + dis[0][y]
- 3、虽然修改后最短路不一定经过 w,但由于不断的使用最短路长度最短的节点,因此最终总能修改成功,除非修改后最短路依然小于 target(例如存在直接从 s 到 e 的边)
- 4、最后,将未修改的边增加到 INF。
class Solution {
private val INF = 1e9.toInt()
fun modifiedGraphEdges(n: Int, edges: Array, source: Int, destination: Int, target: Int): Array {
if (source !in 0 .. n - 1 || destination !in 0 .. n - 1) return edges
if (source == destination || edges.isNullOrEmpty()) return edges
// 建图(领接表,节点号 + 边号方便修改边权)
val graph = Array(n) { ArrayList() }
for ((i, edge) in edges.withIndex()) {
graph[edge[0]].add(intArrayOf(edge[1], i))
graph[edge[1]].add(intArrayOf(edge[0], i))
}
// 第一轮最短路
val originDis = dijkstra1(graph, edges, source, destination)
if (originDis[destination] > target) return emptyArray() // 无解
// 第二轮最短路
val delta = target - originDis[destination] // 需要补全的最短路
val dis = dijkstra2(graph, edges, source, destination, delta, originDis)
if (dis[destination] >, edges: Array, source :Int, destination:Int) : IntArray {
val n = graph.size
val visit = BooleanArray(n)
val dis = IntArray(n) { INF }
dis[source] = 0
while (true) {
// 寻找最短路长度最短的节点
var x = -1
for (i in 0 until n) {
if (visit[i]) continue
if (-1 == x || dis[i] >, edges: Array, source :Int, destination:Int, delta: Int, originDis:IntArray /* 首轮计算的最短路 */) : IntArray {
val n = graph.size
val visit = BooleanArray(n)
val dis = IntArray(n) { INF }
dis[source] = 0
while (true) {
// 寻找最短路长度最短的节点
var x = -1
for (i in 0 until n) {
if (visit[i]) continue
if (-1 == x || dis[i] = 1) edges[to[1]][2] = w
}
if (dis[x] + w
复杂度分析:
- 时间复杂度:$O(n^2)$ 两轮最短路算法;
- 空间复杂度:$O(m)$ 图空间。
往期回顾
- LeetCode 单周赛第 345 场 · 体验一题多解的算法之美
- LeetCode 单周赛第 344 场 · 手写递归函数的通用套路
- LeetCode 双周赛第 104 场 · 流水的动态规划,铁打的结构化思考
- LeetCode 双周赛第 103 场 · 区间求和的树状数组经典应用
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net