Chinaunix首页 | 论坛 | 认证专区 | 博客 登录 | 注册

freearth\'s blog: 系统技术与分布式计算freearth.blog.chinaunix.net

如果你是个木匠,正在打造一个漂亮的五斗柜,你是不会在柜子后面用三合板的,哪怕那一面对着墙,永远没人看到它。你知道它在那里,所以即使是柜子后面,你也会用上好的木材。为了能在晚上睡个好觉,你会在审美和质量上自始至终争取做到最好。

  • 博客访问: 719983
  • 博文数量: 129
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1867
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(129)

文章存档

2013年(1)

2012年(9)

2011年(43)

2010年(3)

2009年(4)

2008年(51)

2007年(18)

微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题
Even-Odd Partition 2012-05-05 20:27:38

分类: Python/Ruby

另一个简单的题目from planet scheme.

I’m not sure where this problem comes from; it’s either homework or an interview question. Nonetheless, it is simple and fun:

Take an array of integers and partition it so that all the even integers in the array precede all the odd integers in the array. Your solution must take linear time in the size of the array and operate in-place with only a constant amount of extra space.

Your task is to write the indicated function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


我的代码如下:


点击(此处)折叠或打开

  1. #lang racket

  2. ;; find the first element satisfied pred?
  3. (define (find-next pred? vec start)
  4.   (let loop ((index start))
  5.     (if (or (>= index (vector-length vec))
  6.             (pred? (vector-ref vec index)))
  7.         index
  8.         (loop (+ index 1)))))

  9. ;; find the previous element statisfied pred?, exclude start
  10. (define (find-prev pred? vec start)
  11.   (let loop ((index (- start 1)))
  12.     (if (or (< index 0)
  13.             (pred? (vector-ref vec index)))
  14.         index
  15.         (loop (- index 1)))))

  16. (define (eo-partition vec)
  17.   (let loop ((start 0) (end (vector-length vec)))
  18.     (define left (find-next odd? vec start))
  19.     (define right (find-prev even? vec end))
  20.     (if (>= left right)
  21.         vec
  22.         (let ((tmp (vector-ref vec left))
  23.               (nstart (+ left 1))
  24.               (nend (- right 1)))
  25.           (vector-set! vec left (vector-ref vec right))
  26.           (vector-set! vec right tmp)
  27.           (loop nstart nend)))))

阅读(6089) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册