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

Leetcode.1247 交换字符使得字符串相同

题目链接

Leetcode.1247 交换字符使得字符串相同 Rating : 1597

题目描述

有两个长度相同的字符串 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<=10001 <= s1.length, s2.length <= 10001<=s1.length,s2.length<=1000
  • s1, s2只包含 'x''y'

分析:

我们只需要讨论 s1[i] != s2[i],即不匹配的情况。

我们用 k表示不能匹配的数量。

我们发现当 k是奇数时,无论怎么也不能让 s1 == s2

在这里插入图片描述
只有当 k是偶数时,才能通过交换让 s1 == s2

示例已经给出了 交换 的两种形式。

在这里插入图片描述
所以为了让操作次数最少,我们应该尽量用第一种交换方式。

xy的数量都是偶数时:

在这里插入图片描述
xy的数量都是奇数时:

在这里插入图片描述

时间复杂度:O(n)O(n)O(n)

C++代码:

class Solution {
public:int minimumSwap(string s1, string s2) {int n = s1.size();unordered_map<char,int> cnt;int k = 0;for(int i = 0;i < n;i++){if(s1[i] != s2[i]){k++;cnt[s1[i]]++;}}if(k % 2) return -1;return k / 2 + cnt['x'] % 2;}
};

Java代码:

class Solution {public int minimumSwap(String s1, String s2) {int n = s1.length();int[] cnt = new int[2];int k = 0;for(int i = 0;i < n;i++){if(s1.charAt(i) != s2.charAt(i)){k++;//'x' - 'x'= 0 , 'y' - 'x' = 1cnt[s1.charAt(i) - 'x']++;}}if(k % 2 == 1) return -1;return k/2 + cnt[0] % 2;}
}

相关文章:

Leetcode.1247 交换字符使得字符串相同

题目链接 Leetcode.1247 交换字符使得字符串相同 Rating &#xff1a; 1597 题目描述 有两个长度相同的字符串 s1和 s2&#xff0c;且它们其中 只含有 字符 "x"和 "y"&#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时…...

python语音识别whisper

一、背景 最近想提取一些视频的字幕&#xff0c;语音文案&#xff0c;研究了一波 二、whisper语音识别 Whisper 是一种通用的语音识别模型。它在不同音频的大型数据集上进行训练&#xff0c;也是一个多任务模型&#xff0c;可以执行多语言语音识别以及语音翻译和语言识别。 …...

Prometheus -- 浅谈Exporter

Prometheus系统 – Exporter原理 为什么我们需要Exporter&#xff1f; 广义上讲所有可以向Prometheus提供监控样本数据的程序都可以被称为一个Exporter。而Exporter的一个实例称为target&#xff0c;如下所示&#xff0c;Prometheus通过轮询的方式定期从这些target中获取样本…...

如何确定RocketMQ中消费者的线程大小

背景 随着物联网行业的发展、智能设备数量越来越多&#xff0c;随着设备活跃量过大&#xff0c;常常存在一些高并发的请求&#xff0c;形成了流量尖峰&#xff0c;过多的请求会压垮服务器&#xff0c;影响其他服务运行。因此&#xff0c;为了保护云端服务&#xff0c;需要对请求…...

OpenAPI SDK组件之Spring Aop源码拓展

Spring Aop 看这个分享的应该都用过Spring Aop&#xff0c;这里就不再过多介绍了它是什么了。 我抽取了Spring Aop的部分源码&#xff0c;通过它实现请求参数可变拦截&#xff0c;同时apisdk离开Spring框架&#xff0c;仍然可以正常运行。 讲拦截也好&#xff0c;通知也罢&a…...

蓝桥杯C/C++VIP试题每日一练之龟兔赛跑预测

&#x1f49b;作者主页&#xff1a;静Yu &#x1f9e1;简介&#xff1a;CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家&#xff0c;前端知识交流社区创建者 &#x1f49b;社区地址&#xff1a;前端知识交流社区 &#x1f9e1;博主的个人博客&#xff1a;静Yu的个人博客…...

为你的Vue2.x老项目安装Vite发动机吧

天下苦webpack久矣&#xff0c;相信作为前端开发者一定经历过在项目迭代时间较长的时候经历漫长等待的这一过程&#xff0c;每一次保存都会浪费掉大量时间&#xff0c;这是webpack这种机制所带来的问题。 于是&#xff0c;尤大为我们带来了新一代前端构建工具&#xff1a;vite…...

ZCMU--5012: 铺设道路(差分思路)

Description 春春是一名道路工程师&#xff0c;负责铺设一条长度为 n 的道路。 铺设道路的主要工作是填平下陷的地表。 整段道路可以看作是 n 块首尾相连的区域&#xff0c;一开始&#xff0c;第 i 块区域下陷的深度为 di。  春春每天可以选择一段连续区间 [L,R]&…...

算法模板总结(自用)

算法模板总结滑动窗口双指针算法数组相关合并两个有序数组左右指针技巧快慢指针技巧字符串相关左右指针反转字符串问题快慢指针替换空格字符问题链表相关快慢双指针删除链表的倒数第N个节点链表相交环形链表链表操作几数之和两数之和四个数组的四数之和三数之和同一数组中四数之…...

【架构师】零基础到精通——架构发展

博客昵称&#xff1a;架构师Cool 最喜欢的座右铭&#xff1a;一以贯之的努力&#xff0c;不得懈怠的人生。 作者简介&#xff1a;一名Coder&#xff0c;软件设计师/鸿蒙高级工程师认证&#xff0c;在备战高级架构师/系统分析师&#xff0c;欢迎关注小弟&#xff01; 博主小留言…...

C++(20):三路比较运算符

C20增加了三路比较运算符<>&#xff08;戏称航天飞机运算符&#xff09;&#xff0c;用于对类的比较运算符进行统一的设计。有两种使用方式&#xff1a;默认比较对于某些类&#xff0c;如果按照其成员逐一比较即可决定比较运算符的值&#xff0c;那么可以使用默认的三路运…...

MySQL workbench 字符集、字符序的概念与联系

在数据的存储上&#xff0c;MySQL提供了不同的字符集支持。而在数据的对比操作上&#xff0c;则提供了不同的字符序支持。 MySQL提供了不同级别的设置&#xff0c;包括server级、database级、table级、column级&#xff0c;可以提供非常精准的设置。 什么是字符集、字符序&am…...

DBA之路---数据库启动与关闭过程

DBA之路—数据库启动与关闭过程 1、启动过程 oracle启动的四个状态 shutdown、就是数据库关闭状态。 nomount模式 #启动instance &#xff0c;读取参数文件、分配sga空间启动后台进程&#xff0c;打开alter日志和其他trace文件startup nomount #该模式下只会创建实例并不加…...

Shell文件包含

和其他语言一样&#xff0c;Shell 也可以包含外部脚本。这样可以很方便的封装一些公用的代码作为一个独立的文件。 一、语法格式 Shell 文件包含的语法格式如下&#xff1a; . filename # 注意点号(.)和文件名中间有一空格 或 source filename 在当前bash环境下读取并执行file…...

计算机网络(六): HTTP,HTTPS,DNS,网页解析全过程

文章目录一、HTTP头部包含的信息通用头部请求头部响应头部实体头部二、Keep-Alive和非Keep-Alive的区别三、HTTP的方法四、HTTP和HTTPS建立连接的过程4.1 HTTP4.2 HTTPS五、HTTP和HTTPS的区别六、HTTPS的加密方式七、cookie和sessionsessioncookie八、HTTP状态码状态码200&…...

Android仿京东金融的数值滚动尺功能

自定义数值滚动尺,这个用的还是挺多的&#xff0c;例如京东金融的通过滚动尺选择金额等,而这次就是高仿京东金融的数值滚动尺。首先看看下效果图&#xff0c;如下&#xff1a;首先先给你们各个变量的含义&#xff0c;以免在后面的讲解中不知变量的意思&#xff0c;代码如下://最…...

Nginx 和 Tomcat 实现负载均衡

Nginx 和 tomcat 实现负载均衡 &#x1f3c6;荣誉认证&#xff1a;51CTO博客专家博主、TOP红人、明日之星&#xff1b;阿里云开发者社区专家博主、技术博主、星级博主。 &#x1f4bb;微信公众号&#xff1a;微笑的段嘉许 &#x1f4cc;本文由微笑的段嘉许原创&#xff01; &am…...

【万能排序之qsort、b_sort 、s_sort】

文章目录前言:star:qsort函数函数参数qsort函数的使用:star:模拟实现万冒泡排序函数参数模拟实现b_sort注意点:star:模拟实现万能选择排序函数参数模拟实现s_sort最后前言 我们所熟悉的冒泡排序&#xff0c;选择排序&#xff0c;插入排序&#xff0c;二分排序等都是基于给定的一…...

利用InceptionV3实现图像分类

最近在做一个机审的项目&#xff0c;初步希望实现图像的四分类&#xff0c;即&#xff1a;正常&#xff08;neutral&#xff09;、涉政&#xff08;political&#xff09;、涉黄&#xff08;porn&#xff09;、涉恐&#xff08;terrorism&#xff09;。有朋友给推荐了个github上…...

【Java】CAS锁

一、什么是CAS机制&#xff08;compare and swap&#xff09; 1.概述 CAS的全称为Compare-And-Swap&#xff0c;直译就是对比交换。是一条CPU的原子指令&#xff0c;其作用是让CPU先进行比较两个值是否相等&#xff0c;然后原子地更新某个位置的值。经过调查发现&#xff0c;…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

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

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

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...