【力扣周赛】第 357 场周赛(⭐反悔贪心)
文章目录
- 竞赛链接
- Q1:6925. 故障键盘
- 解法1——直接模拟
- 解法2——双端队列
- Q2:6953. 判断是否能拆分数组(贪心)
- Q3:2812. 找出最安全路径⭐
- 解法1——多源BFS+瓶颈路模型?
- 解法2——多源BFS + 倒序枚举答案 + 并查集(TODO)
- Q4:2813. 子序列最大优雅度⭐⭐⭐⭐⭐(反悔贪心)
- 思路——反悔贪心
- 代码
- 相似题目列表
- LCP 30. 魔塔游戏(堆+贪心)
- 871. 最低加油次数(堆+贪心)
- 成绩记录
竞赛链接
Q1:6925. 故障键盘
https://leetcode.cn/problems/faulty-keyboard/

提示:
1 <= s.length <= 100
s 由小写英文字母组成
s[0] != 'i'
解法1——直接模拟
遇到 ‘i’ 翻转已有的字符串,其它字符直接添加即可。
class Solution {public String finalString(String s) {StringBuilder ans = new StringBuilder();for (char ch: s.toCharArray()) {if (ch != 'i') ans.append(ch);else ans.reverse();}return ans.toString();}
}
解法2——双端队列
用一个变量维护当前翻转了几次,来决定新来的字符添加在开头还是结尾。
class Solution {public String finalString(String s) {int f = 0;Deque<Character> dq = new ArrayDeque<>();for (char ch: s.toCharArray()) {if (ch == 'i') f++;else {if (f % 2 == 0) dq.offerLast(ch);else dq.offerFirst(ch);}}StringBuilder ans = new StringBuilder();for (char ch: dq) ans.append(ch);if (f % 2 == 1) ans.reverse();return ans.toString();}
}
Q2:6953. 判断是否能拆分数组(贪心)
https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/

提示:
1 <= n == nums.length <= 100
1 <= nums[i] <= 100
1 <= m <= 200

class Solution {public boolean canSplitArray(List<Integer> nums, int m) {int n = nums.size();if (n == 1 || n == 2) return true;for (int i = 0; i < n - 1; ++i) {if (nums.get(i) + nums.get(i + 1) >= m) return true;}return false;}
}
Q3:2812. 找出最安全路径⭐
https://leetcode.cn/problems/find-the-safest-path-in-a-grid/

提示:
1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] 为 0 或 1
grid 至少存在一个小偷
解法1——多源BFS+瓶颈路模型?
第一遍 bfs 求出各个位置的安全系数。
第二遍 bfs,将各个位置的安全系数更新为从终点开始的路径上的较小值。
class Solution {int[] dx = new int[]{-1, 0, 1, 0}, dy = new int[]{0, -1, 0, 1};public int maximumSafenessFactor(List<List<Integer>> grid) {int n = grid.size();if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) return 0;int[][] g = new int[n][n], safe = new int[n][n];Queue<int[]> q = new LinkedList<>();// 第一遍多源bfs 求出各个位置的安全系数for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (grid.get(i).get(j) == 1) {g[i][j] = 1;q.offer(new int[]{i, j});}}}while (!q.isEmpty()) {int sz = q.size();for (int i = 0; i < sz; ++i) {int[] cur = q.poll();int x = cur[0], y = cur[1];for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && ny >= 0 && nx < n && ny < n && g[nx][ny] == 0) {q.offer(new int[]{nx, ny});g[nx][ny] = g[x][y] + 1;}}}}// 第二遍bfs 从终点出发,求出各个路径的最小安全系数q.offer(new int[]{n - 1, n - 1});safe[n - 1][n - 1] = g[n - 1][n - 1];while (!q.isEmpty()) {int[] cur = q.poll();int x = cur[0], y = cur[1];for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && ny >= 0 && nx < n && ny < n) {int nsafe = Math.min(g[nx][ny], safe[x][y]);if (nsafe > safe[nx][ny]) {safe[nx][ny] = nsafe;q.offer(new int[]{nx, ny});}}}}return safe[0][0] - 1;}
}
解法2——多源BFS + 倒序枚举答案 + 并查集(TODO)
https://leetcode.cn/problems/find-the-safest-path-in-a-grid/solutions/2375565/jie-jin-on2-de-zuo-fa-duo-yuan-bfsdao-xu-r5um/
在这里插入代码片
Q4:2813. 子序列最大优雅度⭐⭐⭐⭐⭐(反悔贪心)
https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/

提示:
1 <= items.length == n <= 10^5
items[i].length == 2
items[i][0] == profiti
items[i][1] == categoryi
1 <= profiti <= 10^9
1 <= categoryi <= n
1 <= k <= n
思路——反悔贪心
https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/solutions/2375128/fan-hui-tan-xin-pythonjavacgo-by-endless-v2w1/

代码
核心的思想是:x + y^2,枚举 y^2的值,并使得 x 在该枚举值下的值最大,就得到了该枚举值下的最大值。比较得到的所有的最大值就是最终结果了。
class Solution {public long findMaximumElegance(int[][] items, int k) {// 把利润从大到小排序Arrays.sort(items, (a, b) -> b[0] - a[0]);long ans = 0, totalProfit = 0;Set<Integer> vis = new HashSet<>();Deque<Integer> duplicate = new ArrayDeque<>();for (int i = 0; i < items.length; ++i) {int profit = items[i][0], category = items[i][1];if (i < k) {totalProfit += profit;if (!vis.add(category)) {// 如果已经有这个类别了,就把当前的放在栈顶duplicate.push(profit);}} else if (!duplicate.isEmpty() && vis.add(category)) {// 如果当前栈不为空,且当前种类没有出现过totalProfit += profit - duplicate.pop(); // 修改利润}ans = Math.max(ans, totalProfit + (long) vis.size() * vis.size());}return ans;}
}
相似题目列表
做完之后感觉这两个题目更相似一些,但是和反悔贪心关系不是那么大。
LCP 30. 魔塔游戏(堆+贪心)
https://leetcode.cn/problems/p0NxJO/description/

提示:
1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5
先检查是否有答案存在。
如果有答案存在,就将已经枚举到的负值放入堆中,每次 s <= 0 时,就取出最小的那个负数移动到末尾即可。
class Solution {public int magicTower(int[] nums) {if (Arrays.stream(nums).sum() < 0) return -1;int ans = 0;// pq中存放目前遇到的负数PriorityQueue<Integer> pq = new PriorityQueue<>();long s = 1;for (int x: nums) {s += x;if (x < 0) pq.offer(x);while (s <= 0) {// 每次把最小的移动到最后面去s -= pq.poll();ans++;}}return ans;}
}
871. 最低加油次数(堆+贪心)
https://leetcode.cn/problems/minimum-number-of-refueling-stops/

提示:
1 <= target, startFuel <= 10^9
0 <= stations.length <= 500
1 <= positioni < positioni+1 < target
1 <= fueli < 10^9
用堆维护目前可以加的油,但是先不加,等到走不动了再一个个加。
class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {if (startFuel >= target) return 0;Arrays.sort(stations, (x, y) -> x[0] - y[0]); // 按照位置排序PriorityQueue<Integer> pq = new PriorityQueue<Integer>((x, y) -> y - x);int p = startFuel, ans = 0;for (int i = 0; i < stations.length; ++i) {while (p < stations[i][0] && !pq.isEmpty()) {p += pq.poll();ans++;}if (p < stations[i][0]) break;if (p >= target) return ans;pq.offer(stations[i][1]);}while (p < target && !pq.isEmpty()) {p += pq.poll();ans++;}return p < target? -1: ans;}
}
成绩记录

T3 借助了一些些外力。

上小分。
相关文章:
【力扣周赛】第 357 场周赛(⭐反悔贪心)
文章目录 竞赛链接Q1:6925. 故障键盘解法1——直接模拟解法2——双端队列 Q2:6953. 判断是否能拆分数组(贪心)Q3:2812. 找出最安全路径⭐解法1——多源BFS瓶颈路模型?解法2——多源BFS 倒序枚举答案 并查…...
css重置
css 重置 CSS 重置的主要目标是确保浏览器之间的一致性,并撤消所有默认样式,创建一个空白板。 如今,主流浏览器都实现了css规范,在布局或间距方面没有太大差异。但是通过自定义 CSS 重置,也可以改善用户体验和提高开…...
tcpdump相关
Linux内核角度分析tcpdump原理(一)Linux内核角度分析tcpdump原理(二)...
MFC新建内部消息
提示:记录一下MFC新建内部消息的成功过程 文章目录 前言一、pandas是什么?二、使用步骤 1.引入库2.读入数据总结 前言 先说一下基本情况,因为要在mapview上增加一个显示加载时间的功能。然后发现是要等加载完再显示时间,显示在主…...
linux查找目录
要在Linux中查找目录,可以使用find命令。下面是查询目录的几个示例: 1,查找当前目录下所有子目录: find . -type d 2,在指定路径下查找目录: find /path/to/directory -type d 3,查找以特定名称开头的目录: find . -t…...
机器学习:可解释学习
文章目录 可解释学习为什么需要可解释机器学习可解释还是强模型可解释学习的目标可解释机器学习Local ExplanationGlobal Explanation 可解释学习 神马汉斯,只有在有人看的时候能够答对。 为什么需要可解释机器学习 贷款,医疗需要给出理由,让…...
UE5- c++ websocket里实现调用player里的方法
# UGameInstance里直接调用 获取到引用了,就可以自然的调用。忽略 # UGameInstance里间接调用,通过代理调用 前置已经添加了websocket,具体步骤参考,链接在UWebSocketGameInstance.h里新增代理,并在链接成功后进行绑定。 #pragma…...
线性代数的学习和整理18:什么是维度,什么是秩?秩的各种定理秩的计算 (计算部分未完成)
目录 0 问题引出:什么是秩? 概念备注: 1 先厘清:什么是维数? 1.1 真实世界的维度数 1.2 向量空间的维数 1.2.1 向量空间,就是一组最大线性无关的向量组/基张成的空间 1.3 向量α的维数 1.3.1 向量的…...
Centos 6.5 升级到Centos7指导手册
一、背景 某业务系统因建设较早,使用的OS比较过时,还是centos6.5的系统,因国产化需要,需将该系统升级到BClinux 8.6,但官方显示不支持centos 6.x升级到8,需先将centos6.5升级到centos7的最新版,…...
详解python中的映射类型---字典
概述 映射类型是“键-值”数据项的组合,每个元素是一个键值对,即元素是(key,value),元素之间是无序的。键值对(key,value)是一种二元关系,源于属性和值的映射…...
gdal求矢量图形的形心
gdal求矢量图形的形心 #include "gdal_priv.h" #include "ogrsf_frmts.h"int main() {OGRRegisterAll();OGRPolygon* square_1 new OGRPolygon();OGRLinearRing* ring_1 new OGRLinearRing();// 添加 square_1 的点ring_1->addPoint(0, 0);ring_1-&g…...
<深度学习基础> Batch Normalization
Batch Normalization批归一化 BN优点 减少了人为选择参数。在某些情况下可以取消dropout和L2正则项参数,或者采取更小的L2正则项约束参数;减少了对学习率的要求。现在我们可以使用初始很大的学习率或者选择了较小的学习率,算法也能够快速训…...
Ubuntu yolov5 环境配置
查看Ubuntu版本 $ cat /proc/version Linux version 5.4.0-150-generic (builddbos03-amd64-012) (gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)) #167~18.04.1-Ubuntu SMP Wed May 24 00:51:42 UTC 2023虚拟机磁盘扩容 因为在环境搭建过程中遇到了磁盘空间不足的问题&a…...
【自执行闭包JS逆向】某网站登录MD5加密分析
文章目录 一、写在前面二、抓包分析三、加密函数分析 一、写在前面 最近工作比较忙,不过还是在督促自己利用有限的时间学习更新一些技术文章。互联网这个行业大家目前也都知道是非常内卷的,所有大家在工作之余养成良好的自主学习习惯是非常好的ÿ…...
Stable Diffuse 之 安装文件夹、以及操作界面 UI 、Prompt相关说明
Stable Diffuse 之 安装文件夹、以及操作界面 UI 、Prompt相关说明 目录 Stable Diffuse 之 安装文件夹、以及操作界面 UI 、Prompt相关说明 一、简单介绍 二、安装文件相关说明 三、界面的简单说明 四、prompt 的一些语法简单说明 1、Prompt :正向提示词 &am…...
【Linux】- 一文秒懂shell编程
shell编程 1.1 Shell 是什么1.2 Shell 脚本的执行方式1.3 编写第一个 Shell 脚本2.1 Shell 的变量2.2 shell 变量的定义2.3 设置环境变量3.1 位置参数变量3.2 预定义变量4.1 运算符4.2 条件判断5.1 流程控制5.2 case 语句5.3 for 循环5.4 while 循环5.5 read基本语法6.1函数6.2…...
CentOS下多网卡绑定多IP段时导致只有一个会通的问题解决
CentOS下多网卡绑定多IP段时导致只有一个会通的问题解决 虚拟机配置多个网络地址,结果同时只能有一个ip是通的, 原因:Linux默认开启了反向路由检查导致的,比如说外面访问eth0的网卡,而网关在eth1上,又或者从…...
关于实现 Vue 动态数据显示,比如数字 0 或 1 怎么显示为 男 或 女等等的动态显示实现方法
具体 Vue 代码演示: test.vue 文件演示: <template> <!-- 方法一 --> <div>{{ test.data 0 ? 男 : 女}}</div><!-- 方法二 --> <div>{{ test.data 0 ? 男 : }}{{ test.data 1 ? 女 : }}{{ test.d…...
mac制作ssl证书|生成自签名证书,nodejs+express在mac上搭建https+wss(websocket)服务器
注意 mac 自带 openssl 所以没必要像 windows 一样先安装 openssl,直接生成即可 生成 ssl/自签名 证书 生成 key # 生成rsa私钥,des3算法,server_ssl.key是秘钥文件名 1024位强度 openssl genrsa -des3 -out server_ssl.key 1024让输入两…...
Unix System V BSD POSIX 究竟是什么?
学习Linux系统,很多同学对这些单词概念很模糊、一脸懵逼! 黄老师觉得,了解了历史,才会真正明白这些单词的含义,坐稳、黄老师发车了!!! 首先介绍一下什么是Unix? UNIX(非复用信息和计算机服务,英语:Uniplexed Information and Computing Service,UnICS)取“UNI…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果