posts - 274,  comments - 1258,  trackbacks - 0
今日某ACM群上某君出了一道颇不寻常的题:“如何写一个递归函数reverse(char* s)来使s倒序?”
  不寻常的题自然应该用不寻常的解法,我即兴写了一个:
char* reverse(char* s,int i=0){
  
char c=s[i];
  
return c ? &(*reverse(s,i+1)=c)+1 : s;
}

两行“搞掂”,是不是很好玩呢? 你有没有更简洁或者更特别的算法?欢迎一齐探计~~
P.S.:本人觉得唯一的美中不足是它虽然可以按reverse(char* s)来调用,但毕竟实际上的原型是char* reverse(char* s,int i=0),不过我基本可以肯定不可能使用单形参在O(n)时间内解决本问题。
posted on 2007-01-01 01:17 踏雪赤兔 阅读(1149) 评论(9)  编辑 收藏 引用 所属分类: 玩转编程

FeedBack:
# re: 递归实现倒序?
2007-11-21 15:23 | berry
/* reverse: reverse string s in place; exercise 4-13 */
我是这样想这个递归的
1、首先把s分为s[0]和rest
2、把rest reverse
3、交换s[0]和rest
的确很难在O(n)时间解决

void reverse(char s[])
{
char c;
int i;

if (s[0] == '\0' || s[1] == '\0')
return;
c = s[0];
reverse(s + 1);
for (i = 1; s[i] != '\0'; i++)
s[i - 1] = s[i];
s[i - 1] = c;
}  回复  更多评论
  
# re: 递归实现倒序?
2007-11-23 18:14 | 踏雪赤兔
@berry
你的解法很有意思哦~
不过我想了一下,原来是可以O(n)解决的,不过需要三行:
char* reverse(char* s){
    
static int i=0;
    
char c=s[i++];
    
return c ? &(*reverse(s)=c)+1 : (i=0,s);
}
大家看得明我的算法吗?
  回复  更多评论
  
# re: 递归实现倒序?
2008-03-04 20:14 | 鹤峰
看看这个怎么样?
-----------------------------------
void reverse(const char* const sPtr)
{
if(sPtr[0]=='\0')
return;
else
reverse(&sPtr[1]);
}
-----------------------------------


  回复  更多评论
  
# re: 递归实现倒序?
2008-03-04 22:10 | 踏雪赤兔
楼上的不行吧……你都没有对字符串进行写操作,又怎样倒序呢?  回复  更多评论
  
# re: 递归实现倒序?
2008-03-05 11:38 | 鹤峰
一本书上这么写的,
我也是感到纳闷呢,
所以抄下来,给大家看下。  回复  更多评论
  
# re: 递归实现倒序?
2008-03-05 12:11 | 踏雪赤兔
呵呵~尽信书不如无书啊~  回复  更多评论
  
# re: 递归实现倒序?
2008-03-06 17:28 | richardxx
其实完全有办法只传一个参数在O(n)解决。

用一个queue T;

void reverse( char* s )
{
if ( *s == 0 ) return;

push_queue(*s, T )
reverse( s + 1 );
*s = pop_queue( T );
}
  回复  更多评论
  
# re: 递归实现倒序?
2008-03-06 17:30 | richardxx
ms 我方法犯规了....
不用理我  回复  更多评论
  
# re: 递归实现倒序?
2012-11-30 19:24 | 求答案
我说大哥,我就一大一的水平耶!看不懂,能用最笨的方法不?@踏雪赤兔
  回复  更多评论
  
只有注册用户登录后才能发表评论。

百度空间| 见闻日记| 编程感悟
我的twitter


LOGO

自我介绍:百度厂基础平台车间的一名挨踢民工。擅长C++、算法、语言设计、分布式计算,也用过Java,Python, PHP,JS/AS等语言开发。请关注我的twitter (免翻墙版) 发QQ消息


添加到收藏夹 Locations of visitors to this page

常用链接

随笔分类(300)

随笔档案(274)

文章分类(38)

相册

收藏夹(54)

与博主互动

博客手拉手

搜索

  •  

积分与排名

  • 积分 - 321181
  • 排名 - 9

最新评论

阅读排行榜

评论排行榜