Posted by: sharkmao | 九月 9, 2011

Links

Advertisements
Posted by: sharkmao | 八月 23, 2011

Copy List

public Node CopyList(Node srcHeader)
{
    Node tarHeader, tar, src = null;

    //create target list
    src = srcHeader;
    while (src != null)
    {
        tar = new Node();
        tar.Next = src.Next;
        tar.Random = src.Random;
        src.Next = tar;
        
        //move foward
        src = tar.Next;
    }

    //set target list header
    tarHeader = srcHeader.Next;

    //adjust target list RANDOM pointer
    tar = tarHeader;
    while (tar != null)
    {
        tar.Random = tar.Random.Next;
        
        //move foward
        tar = tar.Next;
        if (tar != null)
            tar = tar.Next;
    }

    //adjust source & target list NEXT pointer
    src = srcHeader;
    while (src != null)
    {
        tar = src.Next;
        src.Next = src.Next.Next;
        tar.Next = tar.Next;
        if (tar.Next != null)
            tar.Next = tar.Next;

        //move foward
        src = src.Next;
    }

    return tarHeader;
}
Posted by: sharkmao | 八月 15, 2011

Remove successive duplicate words


//Given a char array to represent sentence, there is a space between each word as a separator.
//Remove successive duplicate words.
//Minimize time and space complexity.
//No need to support mutiple successive blanks case.
//Sample input: this is is is an apple
//Sample output: this is an apple
void RemoveSuccessiveDuplicateWords(char[] input)
{
    if (input.Length == 0)
        return;

    int p1 = 0;                 //previous word
    int p2 = 0;                 //latter word
    while (input[p2++] != ' ' && p2 < input.Length) ;
    int pp = p2;                //override point

    bool compare = true;
    int tp1 = p1;               //p1 backup
    int tpp = pp;               //pp backup
    while (p2 < input.Length)
    {
        //copy and compare two words
        compare &= (input[p1++] == (input[pp++] = input[p2++]));

        //finish copying latter word
        if (input[p2 - 1] == ' ' || p2 == input.Length)
        {
            if (compare)
            {
                p1 = tp1;          //p1 move backward
                pp = tpp;          //pp move backward
            }
            else
            {
                tp1 = p1 = tpp;    //p1 move foward
                tpp = pp; 
            }
            compare = true;
        }
    }

    //hack tail symbol '\0' for c/c++, '$' for other
    if (pp < input.Length)
    {
        if (input[pp - 1] == ' ')
            input[pp - 1] = '$';
        else
            input[pp] = '$';
    }
}
Posted by: sharkmao | 五月 2, 2011

随大流

一个公司里有 n 个员工,其中某些员工之间有“好友”的关系(这是一个对称的关系)。每天早晨来到公司,员工们都会从茶和咖啡中选择一样作为早饮。此时,每个员工都会观察自己的朋友们都在喝啥:如果超过一半的人都在喝茶,第二天他自己也会跟着喝茶;如果超过一半的人都在喝咖啡,第二天他自己就会跟着喝咖啡;如果喝茶喝咖啡的人数各占一半(仅当他有偶数个朋友时才会发生这种情况),则第二天他的决策不变,继续喝自己今天喝的东西。
由于 n 个员工一共只能产生 2n 种不同的早饮组合,因此总有一天大家喝的东西会和过去的某一天一模一样,从而产生循环。证明:循环的长度不超过 2 。

From http://www.matrix67.com/blog/archives/4270#more-4270

Posted by: sharkmao | 五月 2, 2011

Binary Logarithm

http://en.wikipedia.org/wiki/Binary_logarithm

Posted by: sharkmao | 四月 22, 2011

生孩子

在一个重男轻女的国家里,每个家庭都想生男孩,如果他们生的孩子是女孩,就再生一个,直到生下的是男孩为止。这样的国家,男女比例会是多少?

Posted by: sharkmao | 四月 21, 2011

囚徒开灯

有100个无期囚徒,被关在100个独立的小房间,互相无法通信。 每天会有一个囚徒被完全随机地抽出来放风。放风的地方有一盏灯,囚徒可以打开或者关上,除囚徒外,没有别人会去动这个灯。每个人除非出来防风,是看不到这个灯的。 一天,全体囚徒大会,国王大赦,给大家一个机会:如果某一天,某个囚徒能够明确表示,所有的囚徒都已经被放过风了,而且的确如此,那么所有囚徒释放;如果仍有囚徒未被放过风,那么所有的囚徒一起处死! 囚徒大会后给大家20分钟时间讨论,囚徒们能找到方法么?

Q1. 假设所有人都知道灯的初始状态

Q2. 假设所有人都不知道灯得初始状态

Q3. 假如去掉条件每天会有一个囚徒被完全随机地抽出来放风,改成每天有若干个囚徒被完全随机抽出来放风

Posted by: sharkmao | 四月 20, 2011

囚徒手套

典狱长要和 100 个囚犯玩这么一个游戏。典狱长给每个囚犯发两个手套,一个黑色的,一个白色的。之后,每个囚犯的额头上都会写上一个实数,所有这 100 个实数互不相同。每个囚犯都能看到其他 99 个囚犯前额上所写的数,但不能看到自己的数。接下来,每个囚犯必须独立地决定把哪个手套戴在哪只手上。等到所有囚犯都戴好了手套,典狱长会把他们按照前额上所写的数从小到大地排好,并要求他们手牵着手站成一横排。如果每两只握在一起的手都戴着相同颜色的手套,那么所有 100 个囚犯都可以被释放。
在游戏开始前,他们可以聚在一起,商量一个对策。游戏开始后,囚犯与囚犯之间不允许有任何交流。囚犯们能够保证全部释放吗?

From http://www.matrix67.com/blog/archives/3771

Posted by: sharkmao | 四月 19, 2011

赛马

一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问,最少得比多少场才能知道跑得最快的5匹马?(不能使用撞大运的算法

只需要知道最快的5匹马,不需要知道这5匹马的名次

Posted by: sharkmao | 四月 18, 2011

运煤

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

From http://coolshell.cn/articles/4429.html

Older Posts »

分类