算法求教,ACM 题目指导

题目:要求对任意一个字符串,通过加入若干字符使其对称
如abcda至少要插入两个字符,两个一下无法使其对称abdcdba,adbcdba
请求出需要插入的最少字符数


希望大家能给我出出主意,给点解决这个题目的思路!感激

7个回答

[code="java"]
public static int symmetry(String source) {
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i <= compareIndex; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
}
}
return count;
}
[/code]
循环的地方改成:
for(int i = 0; i <= compareIndex; i++)
就可以满足了

zhang583740618
rjbusiness 如果要记录所加入的字符,并且打印最后最短对称字符串的结果了?
6 年多之前 回复

这个问题灰常简单:我们不知道该字符串的对称序号位于字符串的第几个字符,也就没有办法从中间字符一次对比来增加字符,换个思路,我们可以从开头和末尾来对比,倒数第一正数第一相同,依次对比倒数第二个和正数第二个;倒数第一正数第一不同则在开头或者末尾增加字符,然后再对比倒数第二个正数第二个......

我的理解是递归做
abcda
1、首先判断第一个和最后一个是否一样
2、如果不一样 分两种情况 --> 最前 最后 插入字符 然后再递归(带上当前的插入的数量) 找下去 找到最后即可 这样就找到每种情况

3、优化 可以把找完的存到一个位置 然后其他递归每次找时和之前找到的进行匹配 如果大于就提前终止 不再找了

[code="java"]
public static int symmetry(String source) {
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i < length; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
}
}
if(count % 2 == 1) {
count--;
}
return count;
}
[/code]
粗略的写了个,你测试下,与你的目标算法可有出入。我测试几个,基本上是正确的。

Dead_Knight
Dead_Knight 请求出需要插入的最少字符数。肯定是从两边开始比较的。
6 年多之前 回复

[code="java"]
public static int symmetry(String source) {
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i < length; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
}
}
return count;
}
[/code]
测试了一下,觉得有些小问题,就是判断个数是否为奇数,如果奇数,count--。这个思路不对,应该去掉,并且用新的办法重新计算,等中午有空,再改造下

提示:
定义一个计数的number=0。
然后一定是进行首尾比较。
做两个下标变量i,j.首是:i=0,尾是:j=n.
如果相等;i++,j--,判断条件是j>i
如果不等.i++,number++,j不变.
最终number应该就是最少字符数了吧.

[code="java"]
public static int symmetry(String source) {
StringBuffer target = new StringBuffer(source);
int length = source.length();
int count = 0;
int compareIndex = length - 1;
for(int i = 0; i <= compareIndex; i++) {
char c = source.charAt(i);
char end = source.charAt(compareIndex);
if(c == end) {
compareIndex--;
continue;
} else {
count++;
target.insert(compareIndex + 1, c);
}
}
System.out.println(target.toString());
return count;
}
[/code]

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
怎么理解kmp算法,acm中有没有和kmp相关的例题?
-
Count primes ---ACM 题目
-
求解acm题目,一直时间超限,求更优的算法
-
怎么评价算法导论这本书在acm竞赛中的指导意义啊?
-
好像不难的算法题acm求解答
-
求教acm题,急~~~~~
-
问一道开关电灯的acm题目
-
Acm题目,求大神给代码
-
问一道acm题目,下楼梯递归的
-
一道acm题目,刚入门小鸟求帮助!请使用c++语言
-
请教各位算法大神,acm一道题:赋权无向图的最小权值遍历用什么算法(存在负权值)?
-
ACM题目 求思路 枚举超时·
-
一个acm题目问下,应该不会很难,但是么做出来
-
ACM题目(倒蛇阵填数)求java解法
-
ACM题目(互质)(求c或c++解决)
-
求助,杭电ACM题求平均成绩
-
acm题目(求c或c++解决)
-
Selecting Problems 思路和做法
-
如题~一道水的ACM题目
-
Linux文件操作高频使用命令
文章目录0.新建操作:1.查看操作2.删除操作3.复制操作4.移动操作:5.重命名操作:6.解压压缩操作 0.新建操作: mkdir abc #新建一个文件夹 touch abc.sh #新建一个文件 1.查看操作 查看目录: ll #显示目录文件详细信息 查看文件内容: cat|head|tail命令 cat abc.txt #查看abc的内容 head -5 abc.txt #...
程序员实用工具网站
目录 1、搜索引擎 2、PPT 3、图片操作 4、文件共享 5、应届生招聘 6、程序员面试题库 7、办公、开发软件 8、高清图片、视频素材网站 9、项目开源 10、在线工具宝典大全 程序员开发需要具备良好的信息检索能力,为了备忘(收藏夹真是满了),将开发过程中常用的网站进行整理。 1、搜索引擎 1.1、秘迹搜索 一款无敌有良心、无敌安全的搜索引擎,不会收集私人信息,保...
LeetCode解题汇总目录
此篇为LeetCode刷题的汇总目录,方便大家查找,一起刷题,一起PK交流! 已解题目 考点 LeetCode 1. 两数之和(哈希) LeetCode 2. 两数相加(单链表反转) LeetCode 9. 回文数 LeetCode 11. 盛最多水的容器(双指针) LeetCode 15. 三数之和 LeetCode 17. 电话号码的字母组合(回溯...
全球最厉害的 14 位程序员!
来源 | ITWorld 整理自网络全球最厉害的 14 位程序员是谁?今天就让我们一起来了解一下吧,排名不分先后。01. Jon Skeet个人名望:程序技术问答网站 S...
从入门到精通,Java学习路线导航
引言 最近也有很多人来向我"请教",他们大都是一些刚入门的新手,还不了解这个行业,也不知道从何学起,开始的时候非常迷茫,实在是每天回复很多人也很麻烦,所以在这里统一作个回复吧。 Java学习路线 当然,这里我只是说Java学习路线,因为自己就是学Java的,对Java理当很熟悉,对于其它方面,我也不是很了解。 基础阶段 首先是基础阶段,在基础阶段,我们必须掌握Java基础,Mysql数据库,Ora...
二十出头,老气横秋
有的时候,我们希望年轻人成熟一点,不要巨婴,不要总是等着别人来解救,要自立,要有担当。但有时候吧,发现有些年轻人,似乎过于成熟了,二十来岁的人,感觉怎么就老气横秋的。1、...
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
起因 又到深夜了,我按照以往在csdn和公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满! 而女朋友时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个迷宫小游戏啥的! 当我码完字准备睡觉时:写不好别睡觉! 分析 如果用数据结构与算法造出东西来呢? ...
五分钟小知识:为什么说 ++i 的效率比 i++ 高?
点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | 守望先生来源 | 编程珠玑前言不知道你是否听说过 ++i 比 i++ 快的说法,真...
什么是大公司病(太形象了)
点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | 南之鱼来源 | 芝麻观点(chinamkt)所谓大企业病,一般都具有机构臃肿、多重...
代码整洁 vs 代码肮脏
写出整洁的代码,是每个程序员的追求。《clean code》指出,要想写出好的代码,首先得知道什么是肮脏代码、什么是整洁代码;然后通过大量的刻意练习,才能真正写出整洁的代码。 WTF/min是衡量代码质量的唯一标准,Uncle Bob在书中称糟糕的代码为沼泽(wading),这只突出了我们是糟糕代码的受害者。国内有一个更适合的词汇:屎山,虽然不是很文雅但是更加客观,程序员既是受害者也是加害者。 对...
让程序员崩溃的瞬间(非程序员勿入)
今天给大家带来点快乐,程序员才能看懂。 来源:https://zhuanlan.zhihu.com/p/47066521 1. 公司实习生找 Bug 2.在调试时,将断点设置在错误的位置 3.当我有一个很棒的调试想法时 4.偶然间看到自己多年前写的代码 5.当我第一次启动我的单元测试时 ...
Git 天天用 但是 Git 原理你了解吗?
Git 原理 做技术一定要知其然知其所以然,意思就是:知道它是这样的,更知道它为什么是这样的。我主要通过4块内容来简单介绍 Git 是原理是什么样的。这4块内容如下: Git 存储目录结构介绍 Git 是如何存储的 Git 的对象 Git引用 当然 Git 原理不仅仅包含这些,想要更深入了解请查看官方教程 https://git-scm.com/book/zh/v2/。 本文内容是我在 Git...
为什么面向对象糟透了?
又是周末,编程语言“三巨头”Java, Lisp 和C语言在Hello World咖啡馆聚会。服务员送来咖啡的同时还带来了一张今天的报纸, 三人寒暄了几句, C语言翻开了...
Java 每日算法,三个线程按顺序打印
关于多线程的基础知识,可点击下面链接进行学习。 JAVA\Android 多线程实现方式及并发与同步 题目1 启动3个线程A、B、C,使A打印0,然后B打印1,然后C打印2,A打印3,B打印4,C打印5,依次类推。 public class PrintSequenceThread implements Runnable { private static final Ob...
分享靠写代码赚钱的一些门路
作者 mezod,译者 josephchang10如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。今天给大家分享一个精彩...
对计算机专业来说学历真的重要吗?
我本科学校是渣渣二本,研究生学校是985,现在毕业五年,校招笔试、面试,社招面试参加了两年了,就我个人的经历来说下这个问题。 这篇文章很长,但绝对是精华,相信我,读完以后,你会知道学历不好的解决方案,记得帮我点赞哦。 先说结论,无论赞不赞同,它本质就是这样:对于技术类工作而言,学历五年以内非常重要,但有办法弥补。五年以后,不重要。 目录: 张雪峰讲述的事实 我看到的事实 为什么会这样 ...
技术人员要拿百万年薪,必须要经历这9个段位
很多人都问,技术人员如何成长,每个阶段又是怎样的,如何才能走出当前的迷茫,实现自我的突破。所以我结合我自己10多年的从业经验,总结了技术人员成长的9个段位,希望对大家的职...
8000字干货:那些很厉害的人是怎么构建知识体系的
本文约8000字,正常阅读需要15~20分钟。读完本文可以获得如下收益: 分辨知识和知识体系的差别 理解如何用八大问发现知识的连接点; 掌握致用类知识体系的构建方法; 能够应用甜蜜区模型找到特定领域来构建知识体系。 1. 知识体系?有必要吗? 小张准备通过跑步锻炼身体,可因为之前听说过小腿变粗、膝盖受伤、猝死等等与跑步有关的意外状况,有点担心自己会掉进各种坑里,就在微信上问朋友圈一直晒跑步...
nginx学习,看这一篇就够了:下载、安装。使用:正向代理、反向代理、负载均衡。常用命令和配置文件
文章目录前言一、nginx简介1. 什么是 nginx 和可以做什么事情2.Nginx 作为 web 服务器3. 正向代理4. 反向代理5. 动静分离6.动静分离二、Nginx 的安装三、 Nginx 的常用命令和配置文件四、 Nginx 配置实例 1 反向代理五、 Nginx 配置实例 2 负载均衡六、 Nginx 配置实例 3 动静分离七、 Nginx 的高可用集群 前言 一、nginx简介...
500行代码,教你用python写个微信飞机大战
这几天在重温微信小游戏的飞机大战,玩着玩着就在思考人生了,这飞机大战怎么就可以做的那么好,操作简单,简单上手。 帮助蹲厕族、YP族、饭圈女孩在无聊之余可以有一样东西让他们振作起来!让他们的左手 / 右手有节奏有韵律的朝着同一个方向来回移动起来! 这是史诗级的发明,是浓墨重彩的一笔,是…… 在一阵抽搐后,我结束了游戏,瞬时觉得一切都索然无味,正在我进入贤者模式时,突然想到,如果我可以让更多人已不同的方式体会到这种美轮美奂的感觉岂不美哉? 所以我打开电脑,创建了一个 `plan_game.py`……
2019诺贝尔经济学奖得主:贫穷的本质是什么?
2019年诺贝尔经济学奖,颁给了来自麻省理工学院的 阿巴希·巴纳吉(Abhijit Vinayak Banerjee)、艾丝特·杜芙若(Esther Duflo)夫妇和哈...
相关热词 c#该名称在封闭局部范围 c#泛型 排序 c# 测试连接mysql c# 多线程 调用界面值 c# gdi unity c#反射构造带参对象 一起自学c# c#工厂方法 c# 对象属性保存xml u3d用c#写拾取物品