当前位置: 首页 > news >正文

【1247. 交换字符使得字符串相同】

来源:力扣(LeetCode)

描述:

有两个长度相同的字符串 s1s2,且它们其中 只含有 字符 "x""y",你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候,你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间,绝对不能发生在同一个字符串内部。也就是说,我们可以交换 s1[i]s2[j],但不能交换 s1[i]s1[j]

最后,请你返回使 s1s2 相同的最小交换次数,如果没有方法能够使得这两个字符串相同,则返回 -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 <= 1000
  • s1, s2 只包含 ‘x’ 或 ‘y’。

方法:贪心

思路

同时遍历两个字符串,比较相同下标下,两个字符串的字符,如果相同,则该下标的字符不需要进行交换。如果不相同,则有两种情况,一是 s1[i] 为 “x”,s2[i] 为 “y”,用 xy 表示这种情况出现的次数。另一种情况是 s1[i] 为 “y”,s2[i] 为 “x”,用 yx 表示这种情况出现的次数。现在需要通过最少次数的交换,使得 xy 和 yx 都为 0。交换的方法有两种:

  • 示例 1:可以通过一次交换,使得 xy yx 的值减少 2。
  • 示例 2:可以通过两次交换,使得 xy yx 的值各减少 1。

为了使用尽可能少的交换次数,需要从以下顺序考虑:

  1. 第一种交换方式更有效率,应该尽可能采用第一种交换方式。
  2. 如果还未能使 xy 和 yx 都为 0,则应该采用第二种交换方式。
  3. 如果 xy 和 yx 都为 1,则可以通过两次第二种交换,来使得 xy 和 yx 都为 0,否则不能使 xy 和 yx 都为 0。这里也可以预先判断,如果 xy 和 yx 之和为奇数,则没有方法能够使得字符串相等。

代码:

class Solution {
public:int minimumSwap(string s1, string s2) {int xy = 0, yx = 0;int n = s1.size();for (int i = 0; i < n; i++) {char a = s1[i], b = s2[i];if (a == 'x' and b == 'y') {xy++;}if (a == 'y' and b == 'x') {yx++;}}if ((xy + yx) % 2 == 1) {return -1;}return xy / 2 + yx / 2 + xy % 2 + yx % 2;}
};

执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:6 MB, 在所有 C++ 提交中击败了93.67%的用户
复杂度分析
时间复杂度:O(n),其中 n 是字符串的长度。需要遍历两个字符串一遍。
空间复杂度:O(1),只需要常数空间。
author:LeetCode-Solution

相关文章:

【1247. 交换字符使得字符串相同】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 有两个长度相同的字符串 s1 和 s2&#xff0c;且它们其中 只含有 字符 "x" 和 "y"&#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时候&…...

【一天一门编程语言】Lisp 语言程序设计极简教程

Lisp 语言程序设计极简教程 Lisp 是一种古老的编程语言,它的特点是拥有很高的表示能力和灵活的可扩展性,拥有大量的现成函数库,同时也是一种动态类型的语言,十分适合用来实现大规模软件系统。本文介绍了 Lisp 程序设计的基本知识,帮助读者快速上手。 一、Lisp 简介 Lis…...

全后端交互数据加密

前后端交互 通信请求使用https对请求参数进行签名&#xff0c;防止数据篡改对请求参数以及响应数据进行加解密app中使用ssl pinning防止抓包操作 https协议 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-78n9M2PH-1677252127361)(安全.assets/ht…...

稀疏特征和密集特征

在机器学习中&#xff0c;特征是指对象、人或现象的可测量和可量化的属性或特征。特征可以大致分为两类&#xff1a;稀疏特征和密集特征。 稀疏特征 稀疏特征是那些在数据集中不连续出现的特征&#xff0c;并且大多数值为零。稀疏特征的示例包括文本文档中特定单词的存在或不存…...

Linux网络TCP sticky分析工具

1 TCP粘包 - TCP_NODELAY TCP粘包&#xff08;sticky&#xff09;的表现是TCP nagle算法将应用层发送的多个包进行合并后&#xff0c;再发送&#xff0c;很容易出现burst导致bcm89230丢包。由于OABR不支持流控&#xff0c;所以需要使用Linux tc对对应的TCP port进行流量整形。 …...

华为OD机试题,用 Java 解【DNA 序列】问题

最近更新的博客 华为OD机试 - 猴子爬山 | 机试题算法思路 【2023】华为OD机试 - 分糖果(Java) | 机试题算法思路 【2023】华为OD机试 - 非严格递增连续数字序列 | 机试题算法思路 【2023】华为OD机试 - 消消乐游戏(Java) | 机试题算法思路 【2023】华为OD机试 - 组成最大数…...

python的所有知识点+代码+注释,不看就亏死了

目录 简介 特点 搭建开发环境 版本 hello world 注释 文件类型 变量 常量 数据类型 运算符和表达式 控制语句 数组相关 函数相关 字符串相关 文件处理 对象和类&#xff0c;注&#xff1a;不是那个对象&#xff01;&#xff01;&#xff01;&#xff01;&…...

读懂分布式事务

一、概述 1.1 什么是分布式事务 事务我们都很熟悉&#xff0c;事务提供一种机制将一个活动涉及的所有操作纳入到一个不可分割的执行单元&#xff0c;组成这组操作的各个单元&#xff0c;要么全部成功&#xff0c;要么全部失败。 事务有四大特性&#xff1a; Atomic&#xf…...

多目标粒子群算法求解帕累托前沿Pareto,Pareto的原理,测试函数100种求解之21

目录 背影 parte前沿的定义 注意事项 基于多目标粒子群的帕累托前沿求解 主要参数 MATLAB代码 效果图 结果分析 展望 背影 在目标优化过程种,很多时候都两个或者多个目标,并且目标函数不能同时达到最优,鱼与熊掌不可兼得,这个时候可以通过求解帕累托前沿,通过帕累托前沿…...

数组:二分查找、移除数组等经典数组题

二分查找&#xff1a;相关题目链接&#xff1a;https://leetcode.cn/problems/binary-search/题目重现&#xff1a;给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值…...

负责任动物纤维标准RAF

【负责任动物纤维标准RAF】RAF-Responsible Animal Fiber, 中文翻译为负责任动物纤维标准。RAF标准包含了三个子标准&#xff0c;即RWS&#xff08;责任羊毛标准&#xff09;、RMS&#xff08;责任马海毛标准&#xff09;和RAS&#xff08;责任羊驼毛标准&#xff09;。RWS&…...

storybook使用info插件报错

报错内容: RangeErrorMaximum call stack size exceededCall StackprettyPrintvendors-node_modules_pmmmwh_react-refresh-webpack-plugin_lib_runtime_RefreshUtils_js-node_mod-4ff2dd.iframe.bundle.js:160:27undefinedvendors-node_modules_pmmmwh_react-refresh-webpack-…...

【每日一题Day129】LC1247交换字符使得字符串相同 | 贪心

交换字符使得字符串相同【LC1247】 有两个长度相同的字符串 s1 和 s2&#xff0c;且它们其中 只含有 字符 "x" 和 "y"&#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时候&#xff0c;你都可以在两个字符串中各选一个字…...

性能优化之node中间件耗时

背景 中间件在node框架中是很基本的套件&#xff0c;使用不当很容易对页面性能造成影响。除了node服务端外&#xff0c;前端做的SSR项目也要特别重视这块 哪些场景会造成中间件耗时特别严重&#xff1f; 罪魁祸首是&#xff1a;await阻塞 举个例子&#xff1a; 1.如何得到 …...

3-1 图文并茂说明raid0,raid1, raid10, raid01, raid5等原理

文章目录简介RAID类型RAID0RAID1RAID5RAID6RAID10RAID01RAID对比图简介 一、RAID 是什么&#xff1f; RAID &#xff08; Redundant Array of Independent Disks &#xff09;即独立磁盘冗余阵列&#xff0c;简称为「磁盘阵列」&#xff0c;其实就是用多个独立的磁盘组成在一起…...

西北工业大学大学物理(I)下2019-2020选填考题解析

单选题12个&#xff0c;24分。1量子数考查前三个量子数由薛定谔方程决定&#xff0c;最后一个关于自旋的由狄拉克方程决定由这些量子数可以给出原子的壳层结构。考试其实考的不深&#xff0c;记住这个表就够了。2 书上18、19章量子物理的著名实验&#xff1a;光电效应&#xff…...

自动化测试selenium

目录 一、为什么引入自动化测试&#xff1f; 二、为什么选择selenium作为自动化测试工具&#xff1f; 三、环境部署 四、什么是驱动&#xff1f;驱动的工作原理&#xff1f; 五、selenium的基础语法 元素定位 元素操作 点击元素 模拟键盘输入 清除对象输入的文本…...

熟悉GC常用算法,熟悉常见垃圾收集器,具有实际JVM调优实战经验

程序的栈和堆 栈先进后出&#xff0c;且里面的数据自动释放&#xff0c; 堆内的空间则需要手动释放 java python go 只管创建&#xff0c;不用像c,c需要手动释放空间&#xff0c; 因为他们都会开一个进程GC&#xff08;Garbage Collector&#xff09;&#xff0c;由垃圾回收…...

常量和变量——“Python”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰的内容是Python的一些基础语法噢&#xff0c;会讲解一些常量和变量的知识点&#xff0c;那么&#xff0c;现在就让我们进入Python的世界吧 常量和表达式 变量和类型 变量是什么 变量的语法 变量的类型 常量和表达式 …...

《蓝桥杯每日一题》KMP算法·AcWing 141. 周期

1.题目描述一个字符串的前缀是从第一个字符开始的连续若干个字符&#xff0c;例如 abaab 共有 55 个前缀&#xff0c;分别是 a&#xff0c;ab&#xff0c;aba&#xff0c;abaa&#xff0c;abaab。我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。换言之&#xff0c;对于每…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...

Linux基础开发工具——vim工具

文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...