一道超难的算法题-复制链表

Rui在参加面试后,给我分享了一道算法题。他在留言中说made me wanna kill myself when I knew the answer.

题目如下:

Given a Linked List of node structure asstruct Node { type element; Node *next; Node *arb;};You are asked to create an exact copy this linked list. Pointer arb points to an arbitrary node in the linked list.

先说说我的算法吧。我选择了一个超笨的方法完成:创建一个新的linked list存储原始链表每个节点的顺序号,然后复制链表的时候,通过顺序号,找到arb指针所指向的节点。算法很笨,无论是空间效率还是时间效率,都很差。不过好歹是完成了。

不过,在我看完答案之后,我也wanna kill myslef。太神奇了。

Read the rest of this entry »

Posted by Wei@11:14 16/16/2008 in Computer Science | Permalink | Trackback | 1 Comment.

快速平方根算法

Carmack在QUAKE3中使用了下面的算法,它第一次在公众场合出现的时候,几乎震住了所有的人。据说该算法其实并不是Carmack发明的,它真正的作者是Nvidia的Gary Tarolli(未经证实)。

今天看到一个快速平方根算法,很是巧妙。据称是Carmack在QUAKE3中使用了下面的算法,它第一次在公众场合出现的时候,几乎震住了所有的人。

  1. float InvSqrt(float x)
  2. {
  3.     float xhalf = 0.5f*x;
  4.     int i = *(int*)&x; // get bits for floating value
  5.     i = 0x5f3759df - (i>>1); // gives initial guess y0
  6.     x = *(float*)&i; // convert bits back to float
  7.     x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
  8.     return x;
  9. }

Chris Lomont写了篇论文,关于这个算法:
http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

Tags:
Posted by Wei@11:21 13/13/2007 in Computer Science | Permalink | Trackback | No comments.

推荐本算法书

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

用伪代码写的。

Table of contents

Preface

Chapter 0: Prologue
Chapter 1: Algorithms with numbers
Chapter 2: Divide-and-conquer algorithms
Chapter 3: Decompositions of graphs
Chapter 4: Paths in graphs
Chapter 5: Greedy algorithms
Chapter 6: Dynamic programming
Chapter 7: Linear programming
Chapter 8: NP-complete problems
Chapter 9: Coping with NP-completeness
Chapter 10: Quantum algorithms


Posted by Wei@1:29 12/12/2006 in Uncategorized | Permalink | Trackback | No comments.