2023-02-25力扣每日一题

news/2024/3/29 15:08:42/文章来源:https://blog.csdn.net/Fei_WuYan/article/details/129216004

链接:

https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal/

题意:

给定字符串s1,s2,仅由x,y组成

每次可以在两边各挑一个字符交换

求让s1等于s2的最小步骤

解:

1000啊1000,双指针贪一下就过了

优先选择xx组合yy,只需要一步,然后处理xy和yx

然后发现好像太敷衍了,又想了想

在预先处理掉不需要考虑的位置(原来就相同的位置)情况下

可以发现,剩下的如果是偶数位,一定可以换完,因为任意两位一定含有2x2y,因为s1[i]!=s2[i]

所以判断一下新字符串长度,得出是否为-1

然后算一下每位上xy和yx的数量,因为花费一步可以解决两个xy或者两个yx,花费两步就是解决一个xy+yx,优先做费用一步的操作,数量为xy/2+yx/2

然后做费用两步的操作,由于总数为偶数,所以用xy%2*2,如果有剩余的xy就一定会有对应的yx

ans为xy/2+yx/2+xy%2*2

实际代码:

贪:

#include<iostream>
using namespace std;
int solve(string s1, string s2)
{int ans=0;int lg1=s1.length(),lg2=-1;string t1,t2;for(int i=0;i<lg1;i++){if(s1[i]!=s2[i]){t1+=s1[i];t2+=s2[i];}}lg2=t1.length();//处理掉不需要处理的位置 //cout<<t1<<" and "<<t2<<endl;for(int i=0;i<lg2;i++){if(t1[i]=='-' || t2[i]=='-') continue;for(int j=i+1;j<lg2;j++){if(t1[j]=='-' || t2[j]=='-') continue;string temp1,temp2;temp1=temp1+t1[i]+t1[j];temp2=temp2+t2[i]+t2[j];cout<<temp1<<" "<<temp2<<endl;if((temp1=="xx" && temp2=="yy")||(temp1=="yy" && temp2=="xx")){ans+=1;t1[i]=t1[j]=t2[i]=t2[j]='-';}}}//步骤一 处理所有一步的移动 //cout<<"step1 done!"<<endl;//cout<<t1<<" "<<t2<<endl;for(int i=0;i<lg2;i++){if(t1[i]=='-' || t2[i]=='-') continue;for(int j=i+1;j<lg2;j++){if(t1[j]=='-' || t2[j]=='-') continue;string temp1,temp2;temp1=temp1+t1[i]+t1[j];temp2=temp2+t2[i]+t2[j];cout<<temp1<<" "<<temp2<<endl;if((temp1=="xy" && temp2=="yx")||(temp1=="yx" && temp2=="xy")){ans+=2;t1[i]=t1[j]=t2[i]=t2[j]='-';}}}//步骤二 处理所有两步的移动 //cout<<"step2 done!"<<endl;//cout<<t1<<" "<<t2<<endl;for(int i=0;i<lg2;i++){if(t1[i]!='-'||t2[i]!='-'){ans=-1;break;}}//步骤三 检查是否全部处理完毕 //cout<<"step3 done!"<<endl;return ans;
}
int main()
{string s1,s2;cin>>s1>>s2;int ans=solve(s1,s2);cout<<ans<<endl;
}

改:

#include<iostream>
using namespace std;
int solve(string s1, string s2)
{int ans=0;int lg1=s1.length(),lg2=-1;string t1,t2;for(int i=0;i<lg1;i++){if(s1[i]!=s2[i]){t1+=s1[i];t2+=s2[i];}}lg2=t1.length();//处理掉不需要处理的位置 //cout<<t1<<" and "<<t2<<endl;int xy=0,yx=0;for(int i=0;i<lg2;i++){if(t1[i]=='x' && t2[i]=='y'){xy++;}else yx++;}//已知去除了不需要处理的位置//任意两位上都是2x2y不会出现处理不了的问题//判断是否是奇数位需要处理,即会剩下一个xy//if((xy+yx)%2==1) return -1;//奇数位?奇数位! if(lg2%2==1) return -1;return xy/2+yx/2+xy%2*2;
}
int main()
{string s1,s2;cin>>s1>>s2;int ans=solve(s1,s2);cout<<ans<<endl;
}

限制:

  • 1 <= s1.length, s2.length <= 1000
  • s1, s2 只包含 'x''y'

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_74030.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

直接在ide启动mitmproxy监听,脱离命令行启动,懒人福音

前言 本文解决了只能通过命令行启动 mitmproxy 的痛点。 在使用 mitmproxy 时候存在这样一个问题&#xff0c;就是每次启动它时候都需要通过命令行启动。 加上最近有位读者向我提问&#xff08;以前也有读者提问该问题&#xff09;&#xff1a;不通过命令行如何启动 mitmproxy监…

XML调用 CAPL Test Function

&#x1f345; 我是蚂蚁小兵&#xff0c;专注于车载诊断领域&#xff0c;尤其擅长于对CANoe工具的使用&#x1f345; 寻找组织 &#xff0c;答疑解惑&#xff0c;摸鱼聊天&#xff0c;博客源码&#xff0c;点击加入&#x1f449;【相亲相爱一家人】&#x1f345; 玩转CANoe&…

阿里限量出产Elasticsearch学习手册,确定不心动?

前言只有光头才能变强。不知道大家的公司用Elasticsearch多不多&#xff0c;反正我公司的是有在用的。平时听同事们聊天肯定避免不了不认识的技术栈&#xff0c;例如说&#xff1a;把数据放在引擎&#xff0c;从引擎取出数据等等。如果对引擎不了解的同学&#xff0c;就压根听不…

九龙证券|阿里+鸿蒙+人工智能+元宇宙概念热度爆棚,“会说话的猫”亮了!

近一周组织调研个股数量有240多只&#xff0c;汤姆猫成为调研组织数量最多的股票。 证券时报数据宝统计&#xff0c;近一周组织调研公司数量有240多家。从调研组织类型来看&#xff0c;证券公司调研相对最广泛&#xff0c;调研230多家公司。 “会说话的猫”亮了 汤姆猫成为近…

Flink高手之路1一Flink的简介

文章目录一、Flink简介1. Fink的引入2.Flink简介3.支持的编程语言4.Flink的特性5.Flink四大基石6.批处理和流处理二、Flink的架构1.Flink的角色2.编程模型一、Flink简介 1. Fink的引入 大数据的计算引擎&#xff0c;发展过程有四个阶段 第一代&#xff1a;Hadoop的MapReduce…

二叉搜索树中的众数Java解法

给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root &#xff0c;找出并返回 BST 中的所有 众数&#xff08;即&#xff0c;出现频率最高的元素&#xff09;。 如果树中有不止一个众数&#xff0c;可以按 任意顺序 返回。 假定 BST 满足如下定义&#xf…

【Web逆向】万方数据平台正文的逆向分析(上篇--加密发送请求)—— 逆向protobuf

【Web逆向】万方数据平台正文的逆向分析&#xff08;上篇--加密发送请求&#xff09;—— 逆向protobuf声明一、了解protobuf协议&#xff1a;二、前期准备&#xff1a;二、目标网站&#xff1a;三、开始分析&#xff1a;我们一句句分析&#xff1a;先for循环部分&#xff1a;后…

【算法】最短路算法

&#x1f600;大家好&#xff0c;我是白晨&#xff0c;一个不是很能熬夜&#x1f62b;&#xff0c;但是也想日更的人✈。如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff0c;关注一下&#x1f440;白晨吧&#xff01;你的支持就是我最大的动力&#xff01;&#x1f4…

电子技术——输出阶类型

电子技术——输出阶类型 输出阶作为放大器的最后一阶&#xff0c;其必须有较低的阻抗来保证较小的增益损失。作为放大器的最后一阶&#xff0c;输出阶需要处理大信号类型&#xff0c;因此小信号估计模型不适用于输出阶。尽管如此&#xff0c;输出阶的线性也非常重要。实际上&a…

为什么要用线程池?

1.降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。 2.提高响应速度。当任务到达时&#xff0c;任务可以不需要的等到线程创建就能立即执行。 3.提高线程的可管理性。线程是稀缺资源&#xff0c;如果无限制的创建&#xff0c;不仅会消耗系统资源&#…

Python实现贝叶斯优化器(Bayes_opt)优化支持向量机回归模型(SVR算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后获取。1.项目背景贝叶斯优化器 (BayesianOptimization) 是一种黑盒子优化器&#xff0c;用来寻找最优参数。贝叶斯优化器是…

AI_News周刊:第三期

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 2023.02.20—2023.02.25 News 1.OpenAI 现在正在帮助可口可乐改善其营销和运营 2023 年 2 月 21 日——贝恩公司今天宣布与 OpenAI 建立全球服务联盟&#xff0c;OpenAI 是人工智能系统 ChatGPT、DA…

java Spring JdbcTemplate配合mysql实现数据库表数据添加

本文为 java Spring JdbcTemplate 准备工作的续文 如果您还没有大家好JdbcTemplate 的基础环境 可以先查看前文 首先 之前数据库我们已经弄好了 然后 我们在下面创建一个表 我这里叫 user_list 每一个数据库表 要对应一个实体类 这里 我们打开上一文搭建的项目环境 src下创建…

【华为OD机试模拟题】用 C++ 实现 - 英文输入法(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 分积木(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 吃火锅(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - RSA 加密算法(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 构成的正方形数量(2023.Q1) 【华为OD机试模拟…

【原创】java+swing+mysql生肖星座查询系统设计与实现

今天我们来开发一个比较有趣的系统&#xff0c;根据生日查询生肖星座&#xff0c;输入生日&#xff0c;系统根据这个日期自动计算出生肖和星座信息反馈到界面。我们还是使用javaswingmysql去实现这样的一个系统。 功能分析&#xff1a; 生肖星座查询系统&#xff0c;顾名思义…

【CSS】CSS 层叠样式表 ① ( 简介 | CSS 引入方式 - 内联样式 | 内联样式语法 | 内联样式缺点 )

文章目录一、CSS 层叠样式表二、CSS 引入方式 - 内联样式1、内联样式语法2、内联样式缺点3、内联样式代码示例① 核心代码示例② 完整代码示例③ 执行结果一、CSS 层叠样式表 CSS 全称 Cascading Style Sheets , 层叠样式表 ; 作用如下 : 设置 HTML 页面 文本内容 的 字体 , 颜…

【华为OD机试模拟题】用 C++ 实现 - 最少停车数(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

绝对让你明明白白,脚把脚带你盯着 I2C 时序图将 I2C 程序给扣出来(基于STM32的模拟I2C)

目录前言一、关于STM32 I/O端口位的基本结构讲解二、模拟I2C编写前的需知道的知识1、I2C简介2、根据时序编写模拟I2C程序重要的两点Ⅰ、主机发送数据给从机时的时序控制Ⅱ、主机接收来自从机的数据时的时序控制Ⅲ、完整的I2C时序图&#xff08;按写程序的思想分割时序&#xff…

2023年湖北住建厅七大员建筑八大员怎么报考?启程别

2023年湖北住建厅七大员建筑八大员怎么报考&#xff1f;启程别 建筑施工企业关键技术岗位人员可以叫七大员也可以叫八大员&#xff0c;施工现场专业人员&#xff0c;从事相关岗位人员都应该持证上岗。 为什么有的叫七大员&#xff1f;有的叫八大员呢&#xff1f;甚至还有五大员…

sklearn学习-朴素贝叶斯(二)

文章目录一、概率类模型的评估指标1、布里尔分数Brier Score对数似然函数Log Loss二、calibration_curve&#xff1a;校准可靠性曲线三、多项式朴素贝叶斯以及其变化四、伯努利朴素贝叶斯五、改进多项式朴素贝叶斯&#xff1a;补集朴素贝叶斯ComplementNB六、文本分类案例TF-ID…