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

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

交换字符使得字符串相同【LC1247】

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

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

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

最后,请你返回使 s1s2 相同的最小交换次数,如果没有方法能够使得这两个字符串相同,则返回 -1

考完一门 下周还有一门 加油哇

  • 思路

    当两种字符串某个位置字符不同时,有两种情况:

    • 第一种情况为s1[i]xs2[i]y,记该种情况次数为nXy
    • 第二种情况为s1[i]ys2[i]X,记该种情况次数为nYx

    交换的方法有两种

    1. 通过一次交换(x<->y 或者y<->x )使nXy或者nYx减少2
    2. 通过两次交换(x<->x x<->y 或者y<->y y<->x)使nXynYx各减少1

    如果nXynYx有一个为奇数,那么无法使字符串相等。否则优先采取第一种交换方式【局部最优】,然后当都只剩下一个时,通过两次交换使字符串相等,交换次数为nXy/2+nYx/2+nXy%2+nYx%2nXy/2 + nYx/2+nXy\%2 + nYx\%2nXy/2+nYx/2+nXy%2+nYx%2

  • 实现

    class Solution {public int minimumSwap(String s1, String s2) {int nX = 0, nY = 0;int n = s1.length();for (int i = 0; i < n; i++){if (s1.charAt(i) != s2.charAt(i)){if (s1.charAt(i) == 'x'){nX++;}else{nY++;}}}int res = 0;res += nX / 2;if (nX % 2 == 1){res += 1;nY++;}if (nY % 2 == 1){return -1;}res += nY / 2;return res;}
    }
    
    • 复杂度
      • 时间复杂度:O(n)O(n)O(n)
      • 空间复杂度:O(1)O(1)O(1)

相关文章:

【每日一题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;对于每…...

URL介绍

前言Internet上的每一个网页都具有一个唯一的名称标识&#xff0c;通常称之为URL&#xff08;Uniform Resource Locator, 统一资源定位器&#xff09;。它是www的统一资源定位标志&#xff0c;简单地说URL就是web地址&#xff0c;俗称“网址”。一、URL概念URL是对互联网上得到…...

学习 Python 之 Pygame 开发魂斗罗(一)

学习 Python 之 Pygame 开发魂斗罗&#xff08;一&#xff09;Pygame回忆Pygame1. 使用pygame创建窗口2. 设置窗口背景颜色3. 获取窗口中的事件4. 在窗口中展示图片(1). pygame中的直角坐标系(2). 展示图片(3). 给部分区域设置颜色5. 在窗口中显示文字6. 播放音乐7. 图片翻转与…...

ARM uboot 源码分析8 - uboot的环境变量

一、uboot 的环境变量基础 1、环境变量的作用 (1) 让我们可以不用修改 uboot 的源代码&#xff0c;而是通过修改环境变量&#xff0c;来影响 uboot 运行时的一些数据和特性。譬如说&#xff0c;通过修改 bootdelay 环境变量&#xff0c;就可以更改系统开机自动启动时倒数的秒…...

【蓝牙mesh】Network协议层介绍

【蓝牙mesh】Network协议层介绍 Network层简介 上一章节我们讲解了蓝牙Mesh中Lower层的功能和数据格式。 Lower层的数据往下传输就到了网络层&#xff08;Network Layer&#xff09;。网络层定义了收到Lower层的数据后&#xff0c;如何对其进行判断、封装、加密、认证&#xf…...

基于遗传算法的配电网故障定位(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

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…...

革新性Koikatu体验增强工具:KK-HF_Patch效率提升指南

革新性Koikatu体验增强工具&#xff1a;KK-HF_Patch效率提升指南 【免费下载链接】KK-HF_Patch Automatically translate, uncensor and update Koikatu! and Koikatsu Party! 项目地址: https://gitcode.com/gh_mirrors/kk/KK-HF_Patch 你是否曾在《Koikatu》游戏中遇到…...

163MusicLyrics:开源高效歌词获取与管理解决方案

163MusicLyrics&#xff1a;开源高效歌词获取与管理解决方案 【免费下载链接】163MusicLyrics Windows 云音乐歌词获取【网易云、QQ音乐】 项目地址: https://gitcode.com/GitHub_Trending/16/163MusicLyrics 在数字音乐时代&#xff0c;歌词已成为音乐体验不可或缺的一…...

数字孪生通信层开发:C#实现OPC UA到Unity3D的实时数据映射(2026年工业级实战指南)

引言&#xff1a;通信层不是“锦上添花”&#xff0c;而是“数字孪生的血脉” 在2026年的工业数字孪生战场上&#xff0c;OPC UA到Unity3D的数据映射延迟是决定孪生体“活”与“死”的关键。IDC 2026年工业物联网报告显示&#xff1a;76%的数字孪生项目因通信层延迟>100ms失…...

手把手教你用Arm Cortex-A715手册:从RAS到调试,一份给芯片设计者的实战笔记

Cortex-A715实战指南&#xff1a;芯片设计者的RAS与调试技术精要 在当今高性能计算领域&#xff0c;Arm Cortex-A715处理器核心凭借其卓越的能效比和性能表现&#xff0c;已成为众多芯片设计项目的首选。本文将从工程实践角度&#xff0c;深入剖析Cortex-A715的两个关键子系统&…...

RTL8201F PHY芯片替换调试:从时钟异常到Ping通实战

1. 低成本PHY芯片替换的背景与挑战 最近接手了一个嵌入式以太网项目&#xff0c;甲方对成本控制非常严格&#xff0c;要求我们把原本使用的LAN8742 PHY芯片替换成更便宜的RTL8201F。这个需求听起来简单&#xff0c;但实际操作起来却遇到了不少坑。RTL8201F确实便宜不少&#xf…...

Go 协程池任务调度架构

Go 协程池任务调度架构&#xff1a;高并发任务的智慧引擎 在现代高并发编程中&#xff0c;Go语言的协程&#xff08;goroutine&#xff09;以其轻量级和高效性成为开发者的首选。无限制地创建协程可能导致资源耗尽&#xff0c;而协程池&#xff08;goroutine pool&#xff09;…...

如何快速配置NoteGen快捷键:从新手到效率高手的完整指南

如何快速配置NoteGen快捷键&#xff1a;从新手到效率高手的完整指南 【免费下载链接】note-gen 一款专注于记录和写作的跨端 AI 笔记应用。 项目地址: https://gitcode.com/GitHub_Trending/no/note-gen 你是否曾经在使用笔记应用时&#xff0c;频繁切换鼠标点击菜单&am…...

从‘虚拟’到‘物理’:程序员视角下的内存块、页框与页到底是怎么协作的?

从‘虚拟’到‘物理’&#xff1a;程序员视角下的内存块、页框与页到底是怎么协作的&#xff1f; 当你调试程序时遇到"Segmentation fault"或"Page fault"错误&#xff0c;是否好奇这些术语背后究竟发生了什么&#xff1f;作为开发者&#xff0c;我们每天都…...

程序员必看!用UML类图破解Spring Boot领域模型设计难题

程序员必看&#xff01;用UML类图破解Spring Boot领域模型设计难题 在Spring Boot项目中&#xff0c;领域模型设计往往是决定系统可维护性和扩展性的关键。许多Java开发者虽然熟练使用JPA和MyBatis&#xff0c;但当面对复杂的业务逻辑时&#xff0c;却常常陷入"贫血模型&q…...

3步完成系统深度净化:Win11Debloat工具让旧电脑性能提升60%

3步完成系统深度净化&#xff1a;Win11Debloat工具让旧电脑性能提升60% 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本&#xff0c;用于从Windows中移除预装的无用软件&#xff0c;禁用遥测&#xff0c;从Windows搜索中移除Bing&#xff0c;以及执行各种其他更改以简…...