本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 发问。

大家好，我是小彭。

今天是五一假期的第二天，打周赛的人数比前一天的双周赛多了，难道大家都只玩一天吗？这场周赛是 LeetCode 第 343 场单周赛，假如不考虑榜首题摆烂的翻译，全体标题质量仍是很不错哒。

往期回忆：LeetCode 双周赛第 103 场 区间求和的树状数组经典应用

周赛概览

Q1. 保龄球游戏的取胜者（Easy）

标签：数组、模仿、计数

Q2. 找出叠涂元素（Medium）

标签：矩阵、散列表、计数

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

Q3. 前往方针的最小价值（Medium）

标签：最短路、Dijkstra、最小堆

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

Q4. 字典序最小的美丽字符串（Hard）

标签：贪心、结构

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

Q1. 保龄球游戏的取胜者（Easy）

https://leetcode.cn/problems/determine-the-winner-of-a-bowling-game/

标题描绘

给你两个下标从0开端的整数数组player1和player2，分别表明玩家 1 和玩家 2 击中的瓶数。

保龄球竞赛由n轮组成，每轮的瓶数恰好为10。

假定玩家在第i轮中击中xi个瓶子。玩家第i轮的价值为：

  • 假如玩家在前两轮中击中了10个瓶子，则为2xi。
  • 不然，为xi。

玩家的得分是其n轮价值的总和。

回来

  • 假如玩家 1 的得分高于玩家 2 的得分，则为1；
  • 假如玩家 2 的得分高于玩家 1 的得分，则为2；
  • 假如平局，则为0。

示例 1：

输入：player1 = [4,10,7,9], player2 = [6,5,2,3]
输出：1
解说：player1 的得分是 4 + 10 + 2*7 + 2*9 = 46 。
player2 的得分是 6 + 5 + 2 + 3 = 16 。
player1 的得分高于 player2 的得分，所以 play1 在竞赛中取胜，答案为 1 。

示例 2：

输入：player1 = [3,5,7,6], player2 = [8,10,10,2]
输出：2
解说：player1 的得分是 3 + 5 + 7 + 6 = 21 。
player2 的得分是 8 + 10 + 2*10 + 2*2 = 42 。
player2 的得分高于 player1 的得分，所以 play2 在竞赛中取胜，答案为 2 。

示例 3：

输入：player1 = [2,3], player2 = [4,1]
输出：0
解说：player1 的得分是 2 + 3 = 5 。
player2 的得分是 4 + 1 = 5 。
player1 的得分等于 player2 的得分，所以这一场竞赛平局，答案为 0 。

提示：

  • n == player1.length == player2.length
  • 1 <= n <= 1000
  • 0 <= player1[i], player2[i] <= 10

题解（模仿）

简略模仿题，但标题描绘的中文翻译有歧义，并且不能依据示例区分出来：

  • 了解 1：只要最开端的两轮中击中了 10 个瓶子，那么后续得分加倍；
  • 了解 2：恣意轮的前两轮中击中了 10 个瓶子，那么该轮得分加倍。

依照了解 2 模仿即可：

class Solution {
    fun isWinner(player1: IntArray, player2: IntArray): Int {
        var cnt1 = 0
        var cnt2 = 0
        for (i in player1.indices) {
            val mul1 = player1.slice(Math.max(0, i - 2) until i).any { it == 10 }
            val mul2 = player2.slice(Math.max(0, i - 2) until i).any { it == 10 }
            cnt1 += if (mul1) 2 * player1[i] else player1[i]
            cnt2 += if (mul2) 2 * player2[i] else player2[i]
        }
        return if (cnt1 == cnt2) 0 else if (cnt1 > cnt2) 1 else 2
    }
}

复杂度剖析：

  • 时刻复杂度：O(n)O(n) 其间 n 是 player1 数组的长度；
  • 空间复杂度：O(1)O(1) 仅运用常量等级空间。

Q2. 找出叠涂元素（Medium）

https://leetcode.cn/problems/first-completely-painted-row-or-column/

标题描绘

给你一个下标从0开端的整数数组arr和一个m x n的整数矩阵mat。arr和mat都包括规模[1，m * n]内的一切整数。

从下标0开端遍历arr中的每个下标i，并将包括整数arr[i]的mat单元格涂色。

请你找出arr中在mat的某一行或某一列上都被涂色且下标最小的元素，并回来其下标i。

示例 1：

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解说：遍历如上图所示，arr[2] 在矩阵中的榜首行或第二列上都被涂色。

示例 2：

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输出：3
解说：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。

提示：

  • m == mat.length
  • n = mat[i].length
  • arr.length == m * n
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= arr[i], mat[r][c] <= m * n
  • arr中的一切整数互不相同
  • mat中的一切整数互不相同

问题结构化

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

1、归纳问标题标

核算涂满一行或一列时的最小下标。

2、调查数据特征

arr 数组和 mat 矩阵中的一切整数都没有重复数。

3、剖析问题要件
  • 涂色：运用 arr 数组对 mat 矩阵涂色；
  • 停止条件：当存在一行或一列被涂满时，回来当时的 arr 数组下标。

至此，程序全体框架确认：

for (数字 in arr 数组) {
    涂色
    if (涂满一行或一列) 回来索引
}
return -1 // 问题一定有解
4、进步笼统程度
  • 查找：对 mat 矩阵中的相同数字的单元格涂色时，需求查找数字在矩阵中的方位：
  • 计数：结合「无重复数」的数据特征，判别是否存在一行或一列被涂满时，便是判别一行或一列中被涂色的计数是否抵达行数或列数。
5、具体化处理手法

怎么查找数字的方位？

  • 手法 1（暴力枚举）：枚举 mat 矩阵，直到匹配方针数字时停止；
  • 手法 2（散列表）：结合「无重复数」的数据特征，能够预处理 mat 矩阵取得数字和方位的映射关系，在涂色时以 O(1) 时刻复杂度定位涂色方位。

怎么判别抵达停止条件？

  • 手法 1（暴力枚举）：枚举 mat 矩阵的队伍，当一行或一列的涂色个数抵达行数或列数时停止；
  • 手法 2（计数数组）：记载每一行和每一列的涂色计数，当计数抵达行数或列数时，说明抵达停止条件。

题解（散列表 + 计数）

标题的要害信息是「无重复数」，依据问题剖析模仿即可：

class Solution {
    fun firstCompleteIndex(arr: IntArray, mat: Array<IntArray>): Int {
        val n = mat.size
        val m = mat[0].size
        // 计数数组
        val rows = IntArray(n)
        val columns = IntArray(m)
        // 散列表
        val hashMap = HashMap<Int, IntArray>()
        // 预处理
        for (i in 0 until n) {
            for (j in 0 until m) {
                hashMap[mat[i][j]] = intArrayOf(i, j)
            }
        }
        // 涂色
        for ((i, e) in arr.withIndex()) {
            val node = hashMap[e]!!
            // 判别
            if (++rows[node[0]] == m || ++columns[node[1]] == n) return i
        }
        return -1
    }
}

复杂度剖析：

  • 时刻复杂度：O(nm)O(nm) 其间 n 和 m 分别为矩阵的行数和列数，预处理和涂色分别对每个元素拜访 1 次；
  • 空间复杂度：O(nm)O(nm) 散列表和计数数组空间。

Q3. 前往方针的最小价值（Medium）

https://leetcode.cn/problems/minimum-cost-of-a-path-with-special-roads/

标题描绘

给你一个数组start，其间start = [startX, startY]表明你的初始方位位于二维空间上的(startX, startY)。另给你一个数组target，其间target = [targetX, targetY]表明你的方针方位(targetX, targetY)。

从方位(x1, y1)到空间中任一其他方位(x2, y2)的价值是|x2 - x1| + |y2 - y1|。

给你一个二维数组specialRoads，表明空间中存在的一些特别途径。其间specialRoads[i] = [x1i, y1i, x2i, y2i, costi]表明第i条特别途径能够从(x1i, y1i)到(x2i, y2i)，但本钱等于costi。你能够运用每条特别途径恣意次数。

回来从(startX, startY)到(targetX, targetY)所需的最小价值。

示例 1：

输入：start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
输出：5
解说：从 (1,1) 到 (4,5) 的最优途径如下：
- (1,1) -> (1,2) ，移动的价值是 |1 - 1| + |2 - 1| = 1 。
- (1,2) -> (3,3) ，移动运用榜首条特别途径，价值是 2 。
- (3,3) -> (3,4) ，移动的价值是 |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5) ，移动运用第二条特别途径，价值是 1 。
总价值是 1 + 2 + 1 + 1 = 5 。
能够证明无法以小于 5 的价值完成从 (1,1) 到 (4,5) 。

示例 2：

输入：start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
输出：7
解说：最优途径是不运用任何特别途径，直接以 |5 - 3| + |7 - 2| = 7 的价值从初始方位抵达方针方位。

提示：

  • start.length == target.length == 2
  • 1 <= startX <= targetX <= 105
  • 1 <= startY <= targetY <= 105
  • 1 <= specialRoads.length <= 200
  • specialRoads[i].length == 5
  • startX <= x1i, x2i <= targetX
  • startY <= y1i, y2i <= targetY
  • 1 <= costi <= 105

预备常识 最短路算法

这道题是最短路问题，先回忆下几种最短路算法的差异：

  • Floyd 算法（多源汇正权最短路）
    • 适用于求恣意节点之间的最短路，需求三层循环枚举中转点 i、枚举起点 j 和枚举结尾 k，时刻复杂度最高。
  • Bellman Ford 算法（单源负权最短路）
    • 在每一轮迭代中，测验对图上每一条边进行松懈，直到没有松懈操作时结束。
  • Dijkstra 算法（单源正权最短路）：
    • 在每一轮迭代中，运用确认会集最短路长度最小的节点去松懈相邻节点，因为负权边会损坏贪心战略的挑选，无法处理负权问题；
    • 稀少图小顶堆的写法更优，稠密图朴素写法更优。
最短路算法 Floyd Bellman-Ford Dijkstra Johnson
最短路类型 每对结点之间的最短路 单源最短路 单源最短路 每对结点之间的最短路
作用于 恣意图 恣意图 非负权图 恣意图
能否检测负环？ 能 能 不能 能
时刻复杂度 O(n^3) O(nm) O(mlgn)最小堆 O(nmlgm)

其间 n 是节点数，m 是边数。

问题结构化

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

1、归纳问标题标

核算从 start 到 target 节点的最小价值。

2、调查数据特征
  • 数据巨细：节点数据规模的上界是 10^5，相比于节点规模，特别途径最多只要 200 条，特别途径是稀少的。
3、剖析问题要件

以 start 为起点，target 为结尾，在每次操作能够从 from 节点移动到 to 节点，花费的价值是 |x2 – x1| + |y2 – y1|，别的二维平面中有一些特别途径，花费的价值是特别的。

4、进步笼统程度
  • 曼哈顿间隔：花费的价值是 |x2 – x1| + |y2 – y1| 便是两个节点之间的曼哈顿间隔；
  • 正权边：「从 from 节点移动到 to 节点的价值 x」等价于「从 from 节点到 to 节点的边权为 x」；
  • 有向边：因为标题描绘特别途径只能从 (x1, y1) 走到 (x2, y2)，因而标题是有向边；
  • 是否为决策问题？因为每次操作有多种移动方位挑选，因而这是决策问题，精确来说是最短路问题；
  • 总结：这是一道图的单源正权有向边的最短路问题。
5、具体化处理计划

怎么处理图的单源正权最短路问题？

这道题只需求核算从 start – target 之间的最短路问题，并且边对错负权边，契合 Dijkstra 算法的应用场景。Dijkstra 算法的本质是贪心 + BFS，咱们需求将一切节点分为 2 类，在每一轮迭代中，咱们从 “候选集” 中挑选间隔起点最短路长度最小的节点，因为该点不存在更优解，所以能够用该点来 “松懈” 相邻节点。

  • 1、确认集：已确认（从起点开端）到当时节点最短途径的节点；
  • 2、候选集：未确认（从起点开端）到当时节点最短途径的节点。

需求考虑哪些节点？

这道题没有约束只能走特别途径，那么是不是二维平面上一切节点都需求考虑在呢？是不需求的，结合「三角不等式」调查，咱们发现两个点接连走两次曼哈顿间隔没有意义，也便是说，方针途径一定是在起点、结尾和特别途径节点中间移动。

  • 战略 1：从 from 到 to 走曼哈顿间隔；
  • 战略 2：先从 from 走到特别途径起点，走完特别途径后再走曼哈顿间隔；
  • 战略 3（没有意义）：先从 from 走曼哈顿间隔到 x，再从 x 走曼哈顿间隔到 to。

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

怎么表明二维节点？

最简略的办法是通过位移将 (x, y) 紧缩为一个仅有整数，因为这道题的坐标规模最大到 10^5，所以应该转化到长整型。

val U = 100001L // 数值上界 + 1
紧缩：
val key = x * U + y
复原：
val x = (key / U).toInt()
val y = (key % U).toInt()

至此，咱们能够运用朴素 Dijkstra 算法模仿问题。

是否有优化空间？

朴素 Dijkstra 的每轮迭代中需求遍历 n 个节点寻觅候选会集的最短路长度。事实上，这 n 个节点中有部分是 “确认集”，有部分是远离起点的边缘节点，每一轮都遍历显得没有必要。咱们运用小顶堆记载候选会集最近深度的节点。不过，这道题是稠密图，朴素 Dijkstra 优于 Dijkstra + 最小堆。

持续发掘三角不等式性质：

因为接连走两次曼哈顿间隔没有意义，那咱们乃至不需求把特别途径的起点考虑到图中，或者说直接能够运用 specialRoads 数组，而不需求建图的过程。

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

6、答疑
  • 这道题的数据规模到 10^5，而特别途径最多只要 200 条，不是应该算稀少图？

这个观点混杂了稠密图的定义，稠密或稀少取决于边数相关于节点数的巨细。简略来说，在节点数固定的状况下，边数越大则图越稠密。在这道题中，每个节点都存在到其他一切节点的途径，因而不仅是稠密图，乃至是彻底图。

题解一（朴素 Dijkstra）

  • 运用 Dijkstra 算法处理最短路问题。
class Solution {
    fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {
        // 单源正权最短路
        val U = 100001L // 数值上界 + 1
        val INF = 0x3F3F3F3F
        val startL = start[0] * U + start[1]
        val targetL = target[0] * U + target[1]
        if (startL == targetL) return 0
        // 1、节点与最短路长度
        val nodes = HashMap<Long, Int>()
        // 1.1 特别途径上的节点
        for (road in specialRoads) {
            // 过滤无意义的特别途径（途径花费大于曼哈顿间隔）
            nodes[road[0] * U + road[1]] = INF
            nodes[road[2] * U + road[3]] = INF
        }
        // 1.2 起点节点与结尾节点
        nodes[targetL] = INF
        nodes[startL] = 0 // 起点或许为结尾，假如最初不做特判需求注意次序
        // 2、建有向图（邻接表）<from -> <to -> cost>>
        val graph = HashMap<Long, HashMap<Long, Int>>()
        // 2.1 节点之间的途径（双向边）
        for ((from, _) in nodes) {
            graph[from] = HashMap<Long, Int>()
            val fromX = (from / U).toInt()
            val fromY = (from % U).toInt()
            for ((to, _) in nodes) {
                if (from == to) continue
                val toX = (to / U).toInt()
                val toY = (to % U).toInt()
                graph[from]!![to] = Math.abs(toX - fromX) + Math.abs(toY - fromY)
            }
        }
        // 2.2 特别途径（单向边）
        for (road in specialRoads) {
            val from = road[0] * U + road[1]
            val to = road[2] * U + road[3]
            graph[from]!![to] = Math.min(graph[from]!!.getOrDefault(to, INF), road[4]) // 特别途径的花费或许更长
        }
        // 3、拜访符号
        val visit = HashSet<Long>()
        // 4、朴素 Dijkstra
        while (true) {
            // 寻觅候选会集最短路长度最短的节点
            var minNode = -1L
            var minDis = -1
            for ((to, dis) in nodes) {
                if (visit.contains(to)) continue
                if (minDis == -1 || dis < minDis) {
                    minDis = dis
                    minNode = to
                }
            }
            // println("minNode=$minNode, minDis=$minDis")
            // 找到方针点的最短路长度
            if (minNode == targetL) return minDis
            // 拜访符号
            visit.add(minNode)
            // 松懈相邻节点
            for ((to, cost) in graph[minNode]!!) {
                // println("to=$to, cost=$cost")
                if (minDis + cost < nodes[to]!!) {
                    nodes[to] = minDis + cost
                }
            }
        }
        return -1 // 必定有解
    }
}

复杂度剖析：

  • 时刻复杂度：O(n2)O(n^2) 其间 n 是 specialRoads 特别途径数组的长度；
  • 空间复杂度：O(n2)O(n^2) 图空间 + 符号数组空间。

题解二（Dijkstra 优化）

  • 优化：剪去图空间。
class Solution {
    fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {
        // 单源正权最短路
        val U = 100001L // 数值上界 + 1
        val INF = 0x3F3F3F3F
        val startL = start[0] * U + start[1]
        val targetL = target[0] * U + target[1]
        if (startL == targetL) return 0
        // 1、节点与最短路长度
        val nodes = HashMap<Long, Int>()
        // 起点节点与结尾节点
        nodes[targetL] = INF
        nodes[startL] = 0 // 起点或许为结尾，假如最初不做特判需求注意次序
        // 2、拜访符号
        val visit = HashSet<Long>()
        // 3、朴素 Dijkstra
        while (true) {
            // 寻觅候选会集最短路长度最短的节点
            var minNode = -1L
            var minDis = -1
            for ((to, dis) in nodes) {
                if (visit.contains(to)) continue
                if (minDis == -1 || dis < minDis) {
                    minDis = dis
                    minNode = to
                }
            }
            // println("minNode=$minNode, minDis=$minDis")
            // 找到方针点的最短路长度
            if (minNode == targetL) return minDis
            // 拜访符号
            visit.add(minNode)
            val minNodeX = (minNode / U).toInt()
            val minNodeY = (minNode % U).toInt()
            // 1、直接到结尾
            nodes[targetL] = Math.min(nodes[targetL]!!, minDis + Math.min(nodes[targetL]!!, (target[1] - minNodeY) + (target[0] - minNodeX)))
            // 2、先通过特别途径（minNode -> 特别途径的起点 -> 特别途径的结尾）
            for (road in specialRoads) {
                val specialTo = road[2] * U + road[3]
                if (specialTo == minNode) continue // 重复途径
                val specialDis = minDis + Math.abs(road[0] - minNodeX) + Math.abs(road[1] - minNodeY) + road[4]
                if (specialDis < nodes.getOrDefault(specialTo, INF)) {
                    nodes[specialTo] = specialDis
                }
            }
        }
        return -1 // 必定有解
    }
}

复杂度剖析：

  • 时刻复杂度：O(n2)O(n^2) 其间 n 是 specialRoads 特别途径数组的长度；
  • 空间复杂度：O(n)O(n) 符号数组空间。

题解三（Dijkstra + 最小堆）

附赠一份 Dijkstra + 最小堆的代码：

class Solution {
    fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {
        // 单源正权最短路
        val U = 100001L // 数值上界 + 1
        val INF = 0x3F3F3F3F
        val startL = start[0] * U + start[1]
        val targetL = target[0] * U + target[1]
        if (startL == targetL) return 0
        // 1、节点与最短路长度
        val nodes = HashMap<Long, Int>()
        // 起点节点与结尾节点
        nodes[targetL] = INF
        nodes[startL] = 0 // 起点或许为结尾，假如最初不做特判需求注意次序
        // 2、最小堆
        val heap = PriorityQueue<Long>() { l1, l2 ->
            nodes.getOrDefault(l1, INF) - nodes.getOrDefault(l2, INF)
        }
        heap.offer(startL)
        heap.offer(targetL)
        // 3、Dijkstra
        while (!heap.isEmpty()) {
            // 候选会集最短路长度最短的节点
            val minNode = heap.poll()
            val minDis = nodes[minNode]!!
            // println("minNode=$minNode, minDis=$minDis")
            // 找到方针点的最短路长度
            if (minNode == targetL) return minDis
            val minNodeX = (minNode / U).toInt()
            val minNodeY = (minNode % U).toInt()
            // 1、直接到结尾
            val newDirectToTarget = minDis + Math.min(nodes[targetL]!!, (target[1] - minNodeY) + (target[0] - minNodeX))
            if (newDirectToTarget < nodes[targetL]!!) {
                nodes[targetL] = newDirectToTarget
                heap.offer(targetL)
            }
            // 2、先通过特别途径（minNode -> 特别途径的起点 -> 特别途径的结尾）
            for (road in specialRoads) {
                val specialTo = road[2] * U + road[3]
                if (specialTo == minNode) continue // 重复途径
                val specialDis = minDis + Math.abs(road[0] - minNodeX) + Math.abs(road[1] - minNodeY) + road[4]
                if (specialDis < nodes.getOrDefault(specialTo, INF)) {
                    nodes[specialTo] = specialDis
                    heap.offer(specialTo)
                }
            }
        }
        return -1 // 必定有解
    }
}

复杂度剖析：

  • 时刻复杂度：O(m⋅lgn)O(mlgn) 其间 n 是 specialRoads 特别途径数组的长度，m 是边数，因为这道题是彻底图，所以有 m = n^2；
  • 空间复杂度：O(n)O(n) 符号数组空间。

近期周赛最短路问题：

  • 2612. 最少翻转操作数（Hard）
  • 2608. 图中的最短环（Hard）
  • 2577. 在网格图中拜访一个格子的最少时刻（Hard）

Q4. 字典序最小的美丽字符串（Hard）

https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/

标题描绘

假如一个字符串满意以下条件，则称其为美丽字符串：

  • 它由英语小写字母表的前k个字母组成。
  • 它不包括任何长度为2或更长的回文子字符串。

给你一个长度为n的美丽字符串s和一个正整数k。

请你找出并回来一个长度为n的美丽字符串，该字符串还满意：在字典序大于s的一切美丽字符串中字典序最小。假如不存在这样的字符串，则回来一个空字符串。

关于长度相同的两个字符串a和b，假如字符串a在与字符串b不同的榜首个方位上的字符字典序更大，则字符串a的字典序大于字符串b。

  • 例如，"abcd"的字典序比"abcc"更大，因为在不同的榜首个方位（第四个字符）上d的字典序大于c。

示例 1：

输入：s = "abcz", k = 26
输出："abda"
解说：字符串 "abda" 既是美丽字符串，又满意字典序大于 "abcz" 。
能够证明不存在字符串同时满意字典序大于 "abcz"、美丽字符串、字典序小于 "abda" 这三个条件。

示例 2：

输入：s = "dc", k = 4
输出：""
解说：能够证明，不存在既是美丽字符串，又字典序大于 "dc" 的字符串。

提示：

  • 1 <= n == s.length <= 105
  • 4 <= k <= 26
  • s是一个美丽字符串

问题结构化

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

1、归纳问标题标

结构一个满意条件的方针字符串，命名为「美丽字符串」。

2、剖析问题要件
  • 字符集：标题要求方针字符串仅能运用小写字母表的前 k 个字母，例如 k = 4 只能运用 {a, b, c, d}；
  • 美丽字符串（约束回文）：标题要求方针字符串不包括长度大于 1 的回文子串；
  • 字典序更大：标题要求方针字符串的字典序大于字符串 s；
  • 字典序最小：标题要求回来字典序最小的计划；
3、调查数据特征
  • 数据量：数据量的上界是 10^5，这要求算法的时刻复杂度不能高于 O(n^2)；
  • 输入字符串 s 自身便是「美丽字符串」。
4、调查测试用例

以 s = “abcz”, k = 26 为例：

  • 修正 ‘z’：无法修正 ’z’ 取得字典序更高的字母；
  • 修正 ‘c’：能够修正 ‘c’ 为 ’d’ 得到 “abdz”，且构成「美丽字符串」；
  • 修正 ‘a’ 或 ’b’：也能够结构「美丽字符串」，但字典序不会优于 “abdz”。
5、进步笼统程度
  • 权重：字典序的规则中，字符串越靠前的方位对排序的影响权重越大，例如序列 ”ba“ 的字典序大于 ”az“；
  • 提高：为了结构字典序更大的「美丽字符串」，咱们需求将字符串中的某个字母修正为字母序更大的字母，例如将 ‘a’ 提高到 ‘b’ 或 ‘z’；
  • 下一个摆放：标题要求方针字符串的字典序大于字符串 s，又是一切计划中字典序最小的，问题模型类似经典标题「31.下一个摆放」，能够借鉴；
  • 是否为决策问题：因为每次提高操作有多种方位挑选，因而这是个决策问题，精确来说是一个结构问题。
  • 总结：这是一个结构问题，要求结构满意条件的「下一个美丽字符串」。
6、具体化处理手法

怎么结构满意条件的「下一个美丽字符串」？

因为标题要求结构字典序最小的计划，那么将 s[i] 提高为字母序更大的下一个字母是最优的，例如将 ’a’ 提高到 ‘b’ 优于提高到 ‘z’。除非在 s[i] 现已是字典序最大的字母 ‘z’ 时，咱们需求提高它的前一个字母 s[i – 1]，例如将 ”az“ 提高为 ”bz“ 优于 “cz”。

结构「下一个美丽字符串」需求提高字母序，那么怎么决策替换战略？

因为字符串中越靠前的方位的权重越高，简单想到的贪心战略是从后往前提高字符。假如提高 s[n – 1] 能够结构「美丽字符串」，那么直接提高 s[n – 1] 即可，不然需求提高更靠前的 s[n – 2]。

当咱们确认提高 s[i] 的有效性后，持续向前提高没有意义，而因为 s[i] 的字母序自身现已更大了，且 s[i] 的权重在 [i, n) 区间里是最高的，因而后面不管怎么填字典序都是更大的。那么，为了取得字典序最小的「下一个美丽字符串」，咱们能够贪心肠将后续字符下降到字母序最低的字母，例如 ”abcz“ 提高到 ”abdz” 后，将 ‘z’ 下降到 ‘a’。

这个思考过程，与「下一个摆放」问题是比较类似的。在「下一个摆放」问题中，咱们交换尽或许靠后的一个正序对，因为剩余的序列不管怎么填都是更大的摆放，所以咱们直接对后续字母做正序摆放能够得到最小的字典序。

怎么验证提高的有效性（提高字母序后会或许引入新的回文信息）？

在「调查数据特征」中得知，输入字符串 s 自身便是「美丽字符串」，并且咱们是从后向前提高字符，那么提高 s[i] 只或许结构出长度为 2 或长度为 3 的回文子串，咱们需求以 i 为中心向左右扩展，验证是否有回文串信息。结合上一个问题，因为咱们在提高 s[i] 后还需求下降后序方位的字母序，所以咱们只需求向左面扩展验证有效性。

至此，咱们能够确认全体框架，分为 2 个阶段：

阶段一：
提高 s[n - 1]
while (i 从后往前遍历) {
    for (c in s[i] + 1 until 'a' + k) { // 枚举字符集
        if (存在回文信息) continue
        s[i] = c // 确认有效性
        // 记载下标 i
    }
    // 无法提高 s[i]，测验提高 s[i - 1]
}
阶段二：
// 将 [i + 1, n) 下降为最小字符
for(j in i + 1 until n) {
    for (c in 'a' until 'a' + k) { // 枚举字符集
        if (存在回文信息）continue
        s[j] = c
        break
    }
}

LeetCode 周赛 343（2023/04/30）结合「下一个排列」的贪心构造问题

答疑：
  • 为什么阶段二没有处理无法结构的状况？

因为标题提示 k 的取值规模是大于等于 4 的，也便是字符集的巨细最小为 4，而验证「有效性」只需求调查方位 i 的前两个方位。那么在长度为 3 的子区间 [i-2, i] 中，咱们总能够从巨细为 4 的字符会集，挑选出一个不会结构出回文信息的子串。因而，阶段二是必定可结构的。乃至来说，标题将 k 的取值规模修正到 [3, 26]，咱们的算法也是建立的。

题解（贪心）

class Solution {
    fun smallestBeautifulString(s: String, k: Int): String {
        val n = s.length
        val U = 'a' + k
        val sArray = s.toCharArray()
        var pos = -1
        outer@ for (i in n - 1 downTo 0) {
            // 测验提高字母序
            for (c in sArray[i] + 1 until U) {
                // 验证有效性（只需求验证左面）
                if ((i > 0 && c == sArray[i - 1]) || (i > 1 && c == sArray[i - 2])) continue
                sArray[i] = c
                pos = i
                break@outer
            }
        }
        // 无法结构
        if (pos < 0) return ""
        for (i in pos + 1 until n) {
            for (c in 'a' until U) {
                // 验证有效性（只需求验证左面）
                if ((i > 0 && c == sArray[i - 1]) || (i > 1 && c == sArray[i - 2])) continue
                sArray[i] = c
                break
            }
        }
        return String(sArray)
    }
}

复杂度剖析：

  • 时刻复杂度：O(n)O(n) 其间 n 为字符串 s 的长度，每个方位最多被拜访 2 次，而每个方位的提高操作最多执行 2 次，下降操作最多执行 2 次；
  • 空间复杂度：O(1)O(1) 不考虑成果数组。

类似问题：

  • 31.下一个摆放
  • 647.回文子串