LeetCode346场周赛

news/2024/4/18 19:31:25

2023.5.21LeetCode346场周赛

A. 删除子串后的字符串最小长度

思路

使用栈模拟,每当遇到AB和CD时出栈

代码

class Solution {
public:int minLength(string s) {string res = s.substr(0, 1);for (int i = 1; i < s.size(); i ++ ) {res += s[i];int n = res.size();while (n > 1) {if (res[n - 1] == 'B' && res[n - 2] == 'A' || res[n - 1] == 'D' && res[n - 2] == 'C') {res.pop_back();res.pop_back();}else break;}}return res.size();}
};

B. 字典序最小回文串

思路

双指针,优先选择字典序小的

代码

class Solution {
public:string makeSmallestPalindrome(string s) {int i = 0, j = s.size() - 1;string ans;int n = s.size();while (i < j) {if (s[i] <= s[j]) ans += s[i];else ans += s[j];i ++ , j -- ;}string t = ans;reverse(t.begin(), t.end());if (n % 2)ans += s[i] + t;elseans += t;return ans;}
};

C. 求一个整数的惩罚数

思路

枚举所有数,搜索 i ∗ i i*i ii所有可能的分割情况

代码

class Solution {
public:bool dfs(int u, int num, int cur, int sum, string s) {if (cur > sum) return false;if (u == s.size()) {if (cur + num == sum)return true;return false;}if (dfs(u + 1, s[u] - '0', cur + num, sum, s)) return true;if (dfs(u + 1, num * 10 + s[u] - '0', cur, sum, s)) return true;return false;}int punishmentNumber(int n) {int ans = 0;for (int i = 1; i <= n; i ++ )if (dfs(0, 0, 0, i, to_string(i * i)))ans += i * i;return ans;}
};

D. 修改图中的边权

思路

转载自https://leetcode.cn/problems/modify-graph-edge-weights/solution/xiang-xi-fen-xi-liang-ci-dijkstrachou-mi-gv1m/

代码

typedef pair<int, int> PII;class Solution {
public:vector<vector<int>> d, edges;vector<vector<PII>> g;int n, destination;int delta = 0;void dijkstra(int k) {vector<int> st(n);while (true) {int t = -1;// 找出最近的点for (int i = 0; i < n; i ++ ) {if (!st[i]&& (t == -1 || d[i][k] < d[t][k]))t = i;}if (t == destination)return;st[t] = 1;for (auto [x, y] : g[t]) {int wt = edges[y][2];if (wt == -1)wt = 1;if (k == 1 && edges[y][2] == -1) { // 可变且要修改int w = delta + d[x][0] - d[t][1]; // 要修改成的权值if (w > wt)edges[y][2] = wt = w;}d[x][k] = min(d[x][k], d[t][k] + wt);}}}vector<vector<int>> modifiedGraphEdges(int _n, vector<vector<int>>& _edges, int source, int _destination, int target) {destination = _destination;edges = _edges;n = _n;g.resize(n);d.resize(n, vector<int>(2, 1e9));for (int i = 0; i < edges.size(); i ++ ) {int a = edges[i][0], b = edges[i][1];g[a].push_back({b, i}); // 记录的是edge数组中的下标g[b].push_back({a, i});}d[source][0] = d[source][1] = 0;dijkstra(0); // 把所有-1当做1计算delta = target - d[destination][0]; // 最短路最小的情况下还比target大if (delta < 0) return {};dijkstra(1); // 重新dijkstra增大权值,计算要更改的权值,按照dijkstra的顺序去修改权值,不会影响其他的最短路if (d[destination][1] < target) return {}; // 最短路无法达到targetfor (auto& e : edges)if (e[2] == -1)e[2] = 1;return edges;}
};

http://www.ppmy.cn/news/73352.html

相关文章

选择性搜索算法(Selective Search )——SS算法

文章目录 一、前言二、object Detection VS object Recognition&#xff08;Selective Search的提出&#xff09;2.1object recognition与object detection的关系2.2滑动窗口方法的局限性2.3Selective search算法的提出 三、Selective Search算法3.1什么是Selective Search&…

基于yolov3训练自己的数据集

训练数据集的教学视频链接 42. 第六章&#xff1a;基于YOLO-V3训练自己的数据集与任务_哔哩哔哩_bilibili 数据打标签 下载labelme标注工具 通过pip install labelme下载&#xff0c;打开anaconda prompt&#xff0c;切换到下载labelme的环境&#xff08;我的是pytorch&…

异步线程:CompletableFuture、@Async

区别: 1.CompletableFuture是java中提供的一个异步执行类&#xff0c;Async是Spring提供的异步执行方法&#xff0c;当调用方法单独开启一个线程进行调用。 2.Async通常指定一个方法使用的异步方法调用&#xff0c;而CompletableFuture可以一个方法体内对请求体进行排序组合成…

yolov5剪枝与知识蒸馏【附代码】

剪枝和知识蒸馏均属于模型轻量化设计&#xff0c;剪枝是将已有网络通过剪枝的手段得到轻量化网络&#xff0c;可分为非结构化剪枝和结构化剪&#xff0c;该技术可以免去人为设计轻量网络&#xff0c;而是通过计算各个权重或者通道的贡献度大小&#xff0c;剪去贡献度小的权重或…

面了个 Java 实习生,小伙很优秀!

大家好&#xff0c;我是鱼皮&#xff0c;前几天给自己的公司面试了一位 Java 暑期实习生&#xff0c;候选人目前是大三。 整个过程我都录屏了&#xff0c;并且在征得候选人的同意后&#xff0c;把面试过程分享出来。一方面是希望对其他在学编程找工作的小伙伴有一些启发和参考…

思迈特软件Smartbi荣登“2023未来银行科技服务商100强”

近日&#xff0c;中国科学院《互联网周刊》、eNet研究院联合发布了“2023未来银行科技服务商100强”企业榜单。思迈特软件以“商业智能BI产品”凭借在金融科技创新的独特优势及在银行数字化转型实践中的卓越成就荣耀上榜。 据了解&#xff0c;“未来银行科技服务商100强”榜单&…

Spring IOC 的理解

IoC容器是什么&#xff1f; IoC文英全称Inversion of Control&#xff0c;即控制反转&#xff0c;我么可以这么理解IoC容器&#xff1a; “把某些业务对象的的控制权交给一个平台或者框架来同一管理&#xff0c;这个同一管理的平台可以称为IoC 容器。” 我们刚开始学习…

Java读取txt文件:TSP问题测试算例att48.txt

目录 1读取文件1.1 JDK1.5的Scanner类读取1.2 JDK8的Files.linesStream流按行读取&#xff08;推荐&#xff09;1.3 JDK11提供的Files.readString()1.4 FileInputStreamInputStreamReaderBufferedReader按行读取1.5 经典管道流方式&#xff08;推荐&#xff09; 2 JAVA快速统计…

GEE遥感云大数据林业应用典型案例及GPT模型

详情点击链接&#xff1a;GEE遥感云大数据林业应用典型案例及GPT模型 一&#xff1a;平台及基础开发平台 GEE平台及典型应用案例&#xff1b;GEE开发环境及常用数据资源&#xff1b;ChatGPT、文心一言等GPT模型、帐号申请及林业遥感JavaScript基础&#xff1b;GEE遥感云重要概…

FLEXPART--空气块轨迹-扩散模式

模式简介&#xff1a; FLEXPART(Flexible Particle Dispersion Model)模式是由挪威大气研究所(Norwegian Institute for Air Research)和德国慕尼黑工业大学(Technical University of Munich)联合开发的空气块轨迹&#xff0d;扩散模式, 其通过计算区域内所有气块的运动轨迹进…

[CTF/网络安全] 攻防世界 backup 解题详析

[CTF/网络安全] 攻防世界 backup 解题详析 PHP备份文件名备份文件漏洞成因备份文件名常用后缀姿势总结 题目描述&#xff1a;X老师忘记删除备份文件&#xff0c;他派小宁同学去把备份文件找出来,一起来帮小宁同学吧&#xff01; PHP备份文件名 PHP 脚本文件的备份文件名&#…

(C语言版)力扣(LeetCode)+牛客网(nowcoder)二叉树基础oj练习

二叉树基础oj练习 965. 单值二叉树题目解法 100. 相同的树题目解法 101. 对称二叉树题目解法 144. 二叉树的前序遍历题目解法 94. 二叉树的中序遍历题目解法 145. 二叉树的后序遍历题目解法 572. 另一棵树的子树题目解法 KY11 二叉树遍历题目解法 结语 965. 单值二叉树 题目 …

springboot+java超市收银管理系统idea

考虑到实际生活中在超市 POS 收银管理方面的需要以及对该系统认真的分析&#xff0c;将系统权限按管理员和员工这两类涉及用户划分。 Spring Boot 是 Spring 家族中的一个全新的框架&#xff0c;它用来简化Spring应用程序的创建和开发过程。也可以说 Spring Boot 能简化我们之…

UML类图画法及其关系

UML类图画法及其关系 本文主要是介绍 UML类图画法及其关系&#xff0c;方便今后温习&#xff01;&#xff01;&#xff01; 一、类之间的关系汇总 泛化&#xff08;Generalization&#xff09;实现&#xff08;Realization&#xff09;关联&#xff08;Association&#xff…

Linux 学习笔记(七):时间片

一、时间片概念 时间片&#xff08;timeslice&#xff09;又称为 “量子”&#xff08;quantum&#xff09;或 “处理器片”&#xff08;processor slice&#xff09;&#xff0c;是分时操作系统分配给每个正在运行的进程微观上的一段 CPU 时间&#xff08;在抢占内核中是&…

将有序数组转换为二叉树

md这个破CSDN模板怎么没了&#xff0c;编辑器也死难用&#xff0c;气死 1、题目 给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不…

异地研发团队都使用哪些研发协同工具?盘点7类最主流的研发管理协同软件

产品研发场景下好用的协同办公软件有哪些&#xff1f;分享7类研发过程中主流的协同办公软件&#xff0c;比如项目管理协作与问题跟踪工具PingCode、代码托管与版本控制平台github、持续集成与持续部署&#xff08;CI/CD&#xff09;工具jinkens、文档协作与知识管理工具conflue…

Node开发Web后台服务

简介 Node.js 是一个基于Google Chrome V8 引擎的 JavaScript 运行环境。Node.js 使用了一个事件驱动、非阻塞式 I/O 的模型&#xff0c;使其轻量又高效。Node.js 的包管理器 npm&#xff0c;是全球最大的开源库生态系统。 能方便地搭建响应速度快、易于扩展的网络应用&#…

支付宝沙箱支付(java电脑版)

目录 下载支付demo配置环境AlipayConfig 下载支付demo 网址&#xff1a;https://open.alipay.com/ 下载并打开项目发现无法运行&#xff1a; 手动转化项目&#xff1a; 等待下载整理一下maven pom 通过tomat部署运行测试。 导入阿里支付的pom依赖 <dependency> &l…

《计算机网络—自顶向下方法》 Wireshark实验(十):NAT 协议分析

NAT&#xff08;Network Address Translation&#xff09;网络地址转换&#xff0c;即在私有地址和全局地址之间转换的协议。私有地址是不能用在 Internet 上(路由器将丢弃寻址这种地址的包)的内部地址。这些地址是不能够在公网上面用的&#xff0c;只能用在局域网的内部。私有…