【LeetCode】1247. 交换字符使得字符串相同(超级简单的算法,击败100%)
有两个长度相同的字符串 s1 和 s2,且它们其中 只含有 字符 "x" 和 "y",你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候,你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间,绝对不能发生在同一个字符串内部。也就是说,我们可以交换 s1[i] 和 s2[j],但不能交换 s1[i] 和 s1[j]。
最后,请你返回使 s1 和 s2 相同的最小交换次数,如果没有方法能够使得这两个字符串相同,则返回 -1 。
示例 1:
输入:s1 = "xx", s2 = "yy" 输出:1 解释: 交换 s1[0] 和 s2[1],得到 s1 = "yx",s2 = "yx"。
示例 2:
输入:s1 = "xy", s2 = "yx" 输出:2 解释: 交换 s1[0] 和 s2[0],得到 s1 = "yy",s2 = "xx" 。 交换 s1[0] 和 s2[1],得到 s1 = "xy",s2 = "xy" 。 注意,你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx",因为我们只能交换属于两个不同字符串的字符。
示例 3:
输入:s1 = "xx", s2 = "xy" 输出:-1
示例 4:
输入:s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx" 输出:4
提示:
1 <= s1.length, s2.length <= 1000s1, s2只包含'x'或'y'。
思路:
当你s1和s2不等时,无非就是yx或者xy,要获得最小交换次数,那么我们在此次交换最好解决下次的交换问题。如果有x0个xy,且x0为偶数,则xy的交换次数为x02。如果有y0个xy,且y为偶数,则xy的交换次数为y0/2。如果两者同时为奇数,则只需要记录(x0-1+y0-1)/2+2次交换。xy奇偶不同,则必不可能相同,直接返回-1。
class Solution {
public:int minimumSwap(string s1, string s2) {//两个都不相同换or贪心 int size = s1.size();int x = 0, y = 0;for(int i = 0;i<size;i++){if(s1[i]=='x'&&s2[i]=='y') x++;if(s1[i]=='y'&&s2[i]=='x') y++;}if(!(x%2)&&!(y%2)) return (x+y)/2;else if(x%2&&y%2) return(x+y)/2+1;return -1;}
};
相关文章:
【LeetCode】1247. 交换字符使得字符串相同(超级简单的算法,击败100%)
有两个长度相同的字符串 s1 和 s2,且它们其中 只含有 字符 "x" 和 "y",你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时候,你都可以在两个字符串中各选一个字符进行交换。 交换只能发生在两个…...
23. 合并K个升序链表
解题思路:两种解法,一种优先级队列,一种分治优先级队列解法:以节点中存储的值进行排序依次遍历所有的链表,把链表中的节点加入到优先级队列中依次从优先级队列的弹出并删除最小的元素加入到新的链表中,直到…...
软中断与tasklet简介
一、软中断 1.1 何为软中断? Linux 系统为了解决中断处理程序执行过长的问题,将中断过程分成了两个阶段,分别是「上半部(Top Half)和下半部分(Bottom Half)」。 上半部用来快速处理中断。一…...
JUC 之 线程阻塞工具 LockSupport
——LockSupport 与 线程中断 线程中断机制 一个线程不应该由其他线程来强制中断或停止,而是应该由线程自己自行停止,所以,Thread.stop,Thread.suspend,Thread.resume 都已经被废弃 在 Java 中没有办法立即停止一条线…...
常用数据结构总结-Java版
常用数据结构总结(Java版) C/Java/Python 数据结构大比较 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Dokzp1HQ-1677329125447)(assets/image-20220116142815859.png)] array 同一种类型数据的集合,其实数组…...
【基础算法】二分例题(我在哪?)
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
怕上当?来看这份网络钓鱼和诈骗技术趋势
网络钓鱼和诈骗:当前的欺诈类型 网络钓鱼 钓鱼者可以攻击任何在线服务——银行、社交网络、政府门户网站、在线商店、邮件服务、快递公司等——中的证书。但是,顶级品牌的客户往往面临更大风险,因为相比小品牌,人们更喜欢使用和…...
2023年全国最新保安员精选真题及答案6
百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 61.关于保安员职业资格条件说法正确的是()。 A:必须考试合格…...
unity热更新新方案,ILRuntime
ILRuntime 是一个独立的、跨平台的 .NET Runtime,可用于在 Unity 中实现热更功能。使用 ILRuntime,您可以在游戏运行时加载和执行 C# 脚本,而不需要重新编译整个项目。 以下是一些使用 ILRuntime 的基本步骤: 在 Unity Asset St…...
【J1】【队列】报数游戏
题目描述 有 n 个小朋友围成一圈玩游戏,小朋友从 1 至 n 编号,2 号小朋友坐在 1 号小朋友的顺时针方向,3 号小朋友坐在 2 号小朋友的顺时针方向,……,1 号小朋友坐在 n 号小朋友的顺时针方向。 游戏开始,…...
《程序员的自我修养》阅读笔记
文章目录【第2部分】静态链接1 编译过程2 编辑器的工作流程3 链接——模块的拼接4 目标文件目标文件中的段(section)ELF文件结构5 静态链接1 空间与地址分配2 符号解析与重定位【第3部分】装载与动态链接1 装载的方式2 进程的启动3 为什么需要动态链接&a…...
【跟着ChatGPT学深度学习】ChatGPT带我入门深度学习
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...
软工2023个人作业一——阅读和提问
项目内容这个作业属于哪个课程2023年北航敏捷软件工程这个作业的要求在哪里个人作业-阅读和提问我在这个课程的目标是学习并掌握现代软件开发和项目管理技术,体验敏捷开发工作流程这个作业在哪个具体方面帮助我实现目标通读《构建之法》,了解软件工程中基…...
【Redis】线程模型:Redis是单线程还是多线程?
【Redis】线程模型:Redis是单线程还是多线程? 文章目录【Redis】线程模型:Redis是单线程还是多线程?Redis 是单线程吗?Redis 单线程模式是怎样的?Redis 采用单线程为什么还这么快?Redis 6.0 之前…...
FSM(有限状态机)
FSM有限状态机FSM创建控制有限状态机的脚本设置FSM状态机下的各个状态添加测试类FSM的优点FSM 虽然Unity已经有了动画状态机,但是为了代码的开放封闭原则,这时FSM有限状态机的作用就凸显了出来。 创建控制有限状态机的脚本 先创建一个脚本用来控制有限…...
奇妙的background-clip:text
我们在学习CSS3时,一个背景属性background-clip用来对背景进行裁剪,即指定背景绘制的区域,通常我们使用的几个属性如下:值说明border-box默认值。背景绘制在边框方框内(剪切成边框方框)。padding-box背景绘…...
Vmware虚拟机无法联通主机解决方法二
昨天在遇到了VMware 虚拟机无法联通主机,导致我在CentOS-7 搭建的伪Hadoop3 服务,无法访问管理平台,使用将网络编辑器修改为“桥接”模式解决。今天在学习HBase 时,昨天的问题又重新了,我通过SSH 工具MobaXterm 都无法…...
Boost资料整理备忘
Boost资料整理备忘 网络资源 书籍: The Boost C Libraries官方文档 Boost Library Documentation random boost.randomBoost随机库的简单使用:Boost.Random(STL通用)tutorialstd::random boost::asio Boost.Asio 网络编程 - 基本原理Boost.Asio DocBoost定时器 网…...
规则引擎与风控系统01:新问题,新挑战
如果说在支付系统中使用设计模式,以及开发自定义协议的物联网这两类应用还不够酷的话,那么接下来,咱们就来学一点高逼格的技术吧。 在互联网已经日益普遍的时代,不管是开发2C应用还是2B应用,相信大部分的开发者都有过处理复杂业务逻辑的经历,比如电商、社交、电子政务、O…...
Oracle-00-卸载篇
这里给出企业级的Oracle 10g的卸教程,新安装的19c并没有正经去做卸载的操作,为了后面教程的进度,这里就先借用下10g,如果有需要会重新更新19c的卸载教程 windows服务中将Oracle所有服务全部停掉 选中Oracle - OraDb10g_home2->Oracle Installation Products->Univers…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...
