html5网站建设 教程视频,公司注册网站及流程,公司网站SEO优化哪个做得好,深圳app建设公司⭐️ 本文已收录到 AndroidFamily#xff0c;技术和职场问题#xff0c;请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架#xff0c;你的思考越抽象#xff0c;它能覆盖的问题域就越广#xff0c;理解难度… ⭐️ 本文已收录到 AndroidFamily技术和职场问题请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架你的思考越抽象它能覆盖的问题域就越广理解难度也更复杂。在这个专栏里小彭与你分享每场 LeetCode 周赛的解题报告一起体会上分之旅。 本文是 LeetCode 上分之旅系列的第 37 篇文章往期回顾请移步到文章末尾~ 周赛 357
T1. 故障键盘Easy
标签模拟、字符串
T2. 判断是否能拆分数组Medium
标签思维
T3. 找出最安全路径Medium
标签BFS、连通性、分层并查集、极大化极小、二分查找
T4. 子序列最大优雅度Hard
标签贪心、排序、堆 T1. 故障键盘Easy
https://leetcode.cn/problems/faulty-keyboard/题解模拟
简单模拟题。
在遇到 i 字符时对已填入字符进行反转时间复杂度是 O(n^2)使用队列和标记位可以优化时间复杂度在遇到 i 时修改标记位和写入方向在最后输出时根据标记位输出避免中间的反转操作。
class Solution {
public:string finalString(string s) {vectorchar dst;for (auto c : s) {if (c i) {reverse(dst.begin(), dst.end());} else {dst.push_back(c);}}return string(dst.begin(), dst.end());}
};class Solution {
public:string finalString(string s) {dequechar dst;bool rear true;for (auto c : s) {if (c i) {rear !rear;} else {if (rear) {dst.push_back(c);} else {dst.push_front(c);}}}return rear ? string(dst.begin(), dst.end()) : string(dst.rbegin(), dst.rend());}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 线性遍历和输出时间空间复杂度 O ( n ) O(n) O(n) 临时字符串空间。 T2. 判断是否能拆分数组Medium
https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/题解思维题
思维题主要题目的两个条件只要满足其中一个即可
条件 1子数组的长度为 1 ⇒ 说明数组长度小于等于 2 的时候一定可以满足子数组的长度不大于 1条件 2子数组元素之和大于或等于 m ⇒ 需满足子数组 {a1, a2, a3} 与 {a4, a5, a6} 的子数组和均大于等于 m。
结合两个条件如果我们能找到两个相邻的元素之和大于等于 m那么总可以通过消除 1 个元素的方式完成题目要求。
例如在示例 3 [2, 3, 3, 2, 3] 中我们以 [3,3] 为起点倒推
[3, 3][2, 3, 3] 消除 2[2, 3, 3, 2] 消除 2[2, 3, 3, 2, 3] 消除 3
class Solution {
public:bool canSplitArray(vectorint nums, int m) {// 2 | 3, 3 | 2 | 3// 1, 3, 2, 2, 3// 1, 1, 1, 3, 3if (nums.size() 2) return true;for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1] m) return true;}return false;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 线性遍历时间空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。 T3. 找出最安全路径Medium
https://leetcode.cn/problems/find-the-safest-path-in-a-grid/题解一多源 BFS 二分答案
根据题目描述每个节点的安全系数定位为该节点到「小偷」节点的最小曼哈顿距离而题目要求是寻找从 [0][0] 到 [n-1][n-1] 的最大安全系数。「使得最小曼哈顿距离最大」暗示可能是需要使用二分答案的极大化极小问题。
多源 BFS 预处理 先从每个「小偷」节点开始走 BFS 更新相邻节点的最小曼哈顿距离单次 BFS 的时间复杂度是 O(n^2)虽然我们可以用剪枝优化但整体的时间复杂度上界是 O(n^4)。为了优化时间复杂度我们使用多源 BFS也可以理解为拓扑排序每次弹出的节点的曼哈顿距离最小整体的时间仅为 O(n^2)二分答案 安全系数与路径可达性存在单调性 当安全系数越大时越不容易可达当安全系数越小时越容易可达。安全系数的下界为 0上界为 n * 2 - 1通过二分答案寻找满足可达性的最大安全系数
class Solution {fun maximumSafenessFactor(grid: ListListInt): Int {val INF Integer.MAX_VALUEval directions arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))val n grid.size// 特判if (grid[0][0] 1 || grid[n - 1][n - 1] 1) return 0// 多源 BFS拓扑排序val safe Array(n) { IntArray(n) { -1 }}var queue LinkedListIntArray()for (r in 0 until n) {for (c in 0 until n) {if (grid[r][c] 1) {queue.offer(intArrayOf(r, c))safe[r][c] 0}}}while (!queue.isEmpty()) {val temp LinkedListIntArray()for (node in queue) {for (direction in directions) {val newX node[0] direction[0]val newY node[1] direction[1]if (newX 0 || newX n || newY 0 || newY n || safe[newX][newY] ! -1) continuetemp.offer(intArrayOf(newX, newY))safe[newX][newY] safe[node[0]][node[1]] 1}}queue temp}// for (row in safe) println(row.joinToString())// BFS检查只通过大于等于 limit 的格子能否到达终点fun check(limit: Int) : Boolean {val visit Array(n) { BooleanArray(n) }var queue LinkedListIntArray()queue.offer(intArrayOf(0, 0))visit[0][0] truewhile (!queue.isEmpty()) {val temp LinkedListIntArray()for (node in queue) {// 终止条件if (node[0] n - 1 node[1] n - 1) return truefor (direction in directions) {val newX node[0] direction[0]val newY node[1] direction[1]if (newX 0 || newX n || newY 0 || newY n || visit[newX][newY] || safe[newX][newY] limit) continuetemp.offer(intArrayOf(newX, newY))visit[newX][newY] true}}queue temp}return false}// 二分查找var left 0var right Math.min(safe[0][0], safe[n - 1][n - 1])while (left right) {val mid (left right 1) ushr 1if (!check(mid)) {right mid - 1} else {left mid}}return left}
}复杂度分析
时间复杂度 O ( n 2 ⋅ l g n 2 ) O(n^2·lgn^2) O(n2⋅lgn2) 其中 多源 BFS 时间为 O ( n 2 ) O(n^2) O(n2)单次检查的 BFS 时间复杂度为 O ( n 2 ) O(n^2) O(n2)二分的次数为 l g n 2 lgn^2 lgn2整体时间复杂度是 O ( n 2 ⋅ l g n 2 ) O(n^2·lgn^2) O(n2⋅lgn2)空间复杂度 O ( n 2 ) O(n^2) O(n2) safe 安全系数矩阵空间。
题解二多源 BFS 堆
思路参考雪景式的题解。
在题解一预处理的基础上同样走一次 BFS 也能够算出最大安全系数思路类似于 Dijkstra 最最短路算法中使用当前最短路最短的节点去松弛相邻边我们优先让当前曼哈顿距离最大的节点去松弛相邻节点以保证每个节点都能够从较大的路径转移过来。
class Solution {fun maximumSafenessFactor(grid: ListListInt): Int {...// 类最短路使用曼哈顿距离最大的节点去松弛相邻边val heap PriorityQueueIntArray() { e1, e2 -e2[0] - e1[0]}heap.offer(intArrayOf(safe[0][0], 0, 0))val visit Array(n) { BooleanArray(n) }visit[0][0] truewhile (!heap.isEmpty()) {val node heap.poll()if (node[1] n - 1 node[2] n - 1) return node[0]for (direction in directions) {val newX node[1] direction[0]val newY node[2] direction[1]if (newX 0 || newX n || newY 0 || newY n || visit[newX][newY]) continue// 松弛相邻边heap.offer(intArrayOf(Math.min(node[0], safe[newX][newY]), newX, newY))visit[newX][newY] true}}return 0}
}复杂度分析
时间复杂度 O ( n 2 ⋅ l g n 2 ) O(n^2·lgn^2) O(n2⋅lgn2) 其中 多源 BFS 时间为 O ( n 2 ) O(n^2) O(n2)基于堆的 BFS 的时间复杂度为 O ( n 2 ⋅ l g n 2 ) O(n^2·lgn^2) O(n2⋅lgn2)空间复杂度 O ( n 2 ) O(n^2) O(n2) safe 安全系数矩阵空间。
题解三多源 BFS 分层并查集
思路参考灵神的题解。
其实求从 [0][0] 到 [n - 1][n - 1] 的最大安全系数也相当于连通性问题的变形而连通性问题有并查集的解法。为了求得最大安全系数我们使用分层并查集
首先在预处理阶段求出每个节点的最小曼哈顿距离并将节点按照曼哈顿距离分类其次我们从最大的曼哈顿距离开始逆序合并当 [0][0] 和 [n - 1][n - 1] 连通时返回结果。
class Solution {fun maximumSafenessFactor(grid: ListListInt): Int {val directions arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))val n grid.size// 特判if (grid[0][0] 1 || grid[n - 1][n - 1] 1) return 0// 多源 BFS拓扑排序val safe Array(n) { IntArray(n) { -1 }}// 分层val groups LinkedListLinkedListIntArray()var queue LinkedListIntArray()for (r in 0 until n) {for (c in 0 until n) {if (grid[r][c] 1) {queue.offer(intArrayOf(r, c))safe[r][c] 0}}}groups.add(queue)while (!queue.isEmpty()) {val temp LinkedListIntArray()for (node in queue) {for (direction in directions) {val newX node[0] direction[0]val newY node[1] direction[1]if (newX 0 || newX n || newY 0 || newY n || safe[newX][newY] ! -1) continuetemp.offer(intArrayOf(newX, newY))safe[newX][newY] safe[node[0]][node[1]] 1}}queue tempif (!queue.isEmpty()) groups.add(queue)}// for (row in safe) println(row.joinToString())// for (row in groups) println(row.joinToString())val helper UnionFind(n)// 逆序合并for (i in groups.size - 1 downTo 0) {for (node in groups[i]) {val x node[0]val y node[1]for (direction in directions) {val newX x direction[0]val newY y direction[1]// 合并曼哈顿距离大于等于当前层的节点if (newX 0 || newX n || newY 0 || newY n || safe[newX][newY] i) continuehelper.union(x * n y, newX * n newY)}}if (helper.find(0) helper.find(n * n - 1)) return i}return 0}class UnionFind(private val n: Int) {private val parents IntArray(n * n) { it }private val ranks IntArray(n * n)fun find(x: Int): Int {var cur xwhile (cur ! parents[cur]) {parents[cur] parents[parents[cur]]cur parents[cur]}return cur}fun union(x: Int, y: Int) {val rootX find(x)val rootY find(y)if (ranks[rootX] ranks[rootY]) {parents[rootX] rootY} else if (ranks[rootX] ranks[rootY]){parents[rootY] rootX} else {parents[rootY] rootXranks[rootX]}}}
}复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2) 其中 多源 BFS 时间为 O ( n 2 ) O(n^2) O(n2)基于路径压缩和按秩合并的并查集时间复杂度为 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( n 2 ) O(n^2) O(n2) safe 安全系数矩阵空间。 T4. 子序列最大优雅度Hard
https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/题解反悔贪心 堆
固定一个维度 题目定义的优雅度 total_profit distinct_categories^2 存在两个维度的变量我们考虑固定其中一个维度来简化问题讨论 对所有节点按照利润从大到小逆序排列并选择前 k 个节点此时的 total_profit 是最大的在此基础上我们继续遍历剩余的 n - k 个节点并考虑替换前 k 个节点中的某个节点由于已经选择的节点 total_profit 是最大的因此需要让替换后的类目数变多。 分类讨论替换哪个 1、如果某个已选节点与第 i 个节点的类目相同那么替换后不会让类目数变大不可能让优雅度变大2、如果某个已选节点与第 i 个节点的类目不同但只出现一次那么替换出不会让类目变大不可能让优雅度变大。否则如果出现多次替换后类目数变大有可能让优雅度变大3、为了让优雅度尽可能大我们期望替换后的 total_profit 的减少量尽可能小同时数目类别应该增大否则无法获得更大的优雅度。为了让替换后的 total_profit 的减少量尽可能小我们应该替换已选列表中利润最小同时重复的节点。 怎么高效替换 使用堆维护利润最小同时重复的元素由于我们是从大到小线性枚举的因此直接使用线性表模拟堆的能力新替换进去的不会被替换出去想想为什么。
class Solution {fun findMaximumElegance(items: ArrayIntArray, k: Int): Long {Arrays.sort(items) { e1, e2 -e2[0] - e1[0]}var ret 0Lvar totalProfit 0L// duplicate小顶堆val duplicate LinkedListInt()// categorySet类目表val categorySet HashSetInt()for ((i, item) in items.withIndex()) {val profit item[0]val category item[1]if (i k) {totalProfit item[0]// 记录重复节点if (categorySet.contains(category)) {duplicate.add(profit)}categorySet.add(category)} else if (!duplicate.isEmpty() !categorySet.contains(category)){// 替换totalProfit profit - duplicate.pollLast()categorySet.add(category)} else {// 不会让类目数量变大}// println(duplicate.joinToString())ret Math.max(ret, totalProfit 1L * categorySet.size * categorySet.size)}return ret}
}复杂度分析
时间复杂度 O ( n l g n ) O(nlgn) O(nlgn) 瓶颈在排序空间复杂度 O ( n ) O(n) O(n) 堆空间。 推荐阅读 LeetCode 上分之旅系列往期回顾 LeetCode 单周赛第 356 场 · KMP 字符串匹配殊途同归LeetCode 单周赛第 355 场 · 两题坐牢菜鸡现出原形LeetCode 双周赛第 109 场 · 按部就班地解决动态规划问题LeetCode 双周赛第 107 场 · 很有意思的 T2 题 ⭐️ 永远相信美好的事情即将发生欢迎加入小彭的 Android 交流社群~
