NYOJ - -+-字符串(贪心)
发布日期:2021-07-01 00:14:54
浏览次数:2
分类:技术文章
本文共 1452 字,大约阅读时间需要 4 分钟。
- 内存限制:64MB 时间限制:1000ms
题目描述:
Shiva得到了两个只有加号和减号的字符串,字串长度相同。Shiva一次可以把一个加号和它相邻的减号交换。他想知道最少需要多少次操作才能把第一个字符串变换成第二个字符串。你现在要去帮助他完成那个这个问题。
输入描述:
多组测试数据每组数据有两行,每行包含一个由”+”和”-“最成的字符串。每个子符串长度不超过5000。
输出描述:
仅一个整数,输出最少需要操作的次数。如果答案不存在,输出-1。
样例输入:
++-+--+
-++--++
样例输出:
4
解题思路:
首先,字符串a,b的长度必须一致,否则return -1,然后就是字符串a,b的’+’个数必须一致,否则return -1。当以上条件满足时,就可以正式的比较a,b了。b的第一个’+’最后一定和a的第一个’+’匹配 , … … ,b的第i个’+’最后一定a的第i个’+’匹配 .因为是次数最少,那么a的第一个’+’离得最近的一定是b的第一个’+’ , 总不能够南辕北辙,把b的第2个加好拿去和a的第一个加号去比。那么我们让a不动,移动b的加号,且我们已经知道b的加号要移动到哪个位置。只需用 i 下标表示a的第k个加号,用 j 下标表示b的第k个加号,然后移动的距离就是 abs(j-i) .
#include#include using namespace std;int num(string a){ int ans = 0; for (int i = 0; i < a.length(); i++) if (!(a[i] - '+')) ans++; return ans;}int main(){ string stra, strb; int t, j, ans, lena, lenb; while (cin >> stra >> strb) { j = ans = 0; lena = stra.length(); lenb = strb.length(); if (lena != lenb || num(stra) != num(strb)) { puts("-1"); continue; } for (int i = 0; i < lena; i++) { if (!(stra[i] - '+')) { while (j < lenb) { j++; if (!(strb[j - 1] - '+')) { ans += abs(i - j + 1); break; } } } } cout << ans << endl; } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84073310 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月18日 10时10分55秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
一篇文章了解 Spark Shuffle 内存使用
2019-05-01
【免费下载】某平台3980元Hadoop大数据/机器学习全套视频,仅此1次
2019-05-01
Apache Hive 联邦查询(Query Federation)
2019-05-01
为什么说流处理即未来?
2019-05-01
Leetcode 剑指 Offer 39. 数组中出现次数超过一半的数字 c#
2019-05-01
Leetcode 35. 搜索插入位置 c#
2019-05-01
LeetCode64:最小路径和
2019-05-01
LeetCode931. 下降路径最小和
2019-05-01
LeetCode62. 不同路径
2019-05-01
记gdb调试一次报错:Missing separate debuginfos, use: zypper install glibc-32bit-debuginfo-2.22-15.3.x86_64
2019-05-01
LeetCode242. 有效的字母异位词
2019-05-01
LeetCode83. 删除排序链表中的重复元素
2019-05-01
关于301和302重定向的理解
2019-05-01
使用java代码和jmeter脚本批量造数
2019-05-01
[9] JMeter-常用函数的使用
2019-05-01
[10] JMeter-察看结果树,你知道都有哪些功能吗?
2019-05-01
[11] JMeter-结果分析之聚合报告
2019-05-01
[12] JMeter-结果分析之图形图表
2019-05-01
[13] JMeter-详解JMeter参数化之CSV Data Set Config
2019-05-01