笔试题目“翻转字符串”的Java实现

看到了这样一道笔试题:“写一个函数,将字符串翻转,翻转方式如下:“I am a student”反转成“student a am I”,不借助任何库函数。”

原文章作者使用C实现,我试着用Java实现一下。

参考:http://www.cnblogs.com/rond/archive/2012/05/17/2505997.html

 

一、解决

(1)简单的解决

想了一下,写了个简单版本:

TestReverse.java

运行结果为:

搞定之后爽了一下子,突然感觉不对。用split()方法(以空格为分隔获取单词数组)无疑是在偷懒,应该把split()的工作自己做了才对。

(2)稍微改进

作者提示了,解题思路是先反转整个字符串,然后再反转字串。譬如先将“I am a student”反转为“tneduts a ma I”,然后再对每个字符串(空格分割)反转一次。

TestReverse.java

运行结果为:

折腾了一会,终于拿出了这个改进型的版本。

那么问题又来了,这个append()方法看起来不太和谐,有没有什么方法可以把他替换掉(虽然纠结这种问题意义不大)?

(3)继续改进

我们可以这样思考:append是逐个逐个累加,如果我们使用char[]代替StringBuilder,就必须知道每个元素要放在char[]的哪个位置。我们每次往char[]插入数据,无论插入的是char还是空格,都要记录插入的位置,从而指导下一个元素插入。

在这段代码中,我们可以使用计数器lastModify(记录后一位元素应插入的位置)加上数组char[](结果的载体)把StringBuilder替换掉。

(从上面那段代码演变而来,所以比较好理解。如果直接看这段代码,可能会懵逼)

TestReverse.java

运行结果为:

那么问题又来了,这里使用了toCharArray()方法,把String转成了Char[]。能不能自己实现这个过程?

看了下toCharArray()方法的源码:

到arraycopy()方法为止,再往下的实现就看不到了…我也不知道是怎么实现的。

二、总结

很久不做算法题,复习一下。

发表评论

电子邮件地址不会被公开。 必填项已用*标注