算法智力题

Published: 19 Oct 2015 Category: algorithm

1、关于飞机绕地球飞行一圈的加油问题

每个飞机只有一个油箱,飞机之间可以相互加油,注意是相互,没有加油机,一箱油可供一架飞机绕地球飞半圈。

问题:

为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?

A:所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场

B:所有飞机从同一机场,同一方向起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场

2、1的个数:数字x的个数

题目是这样的:

给定一个十进制的正整数N,写下从1开始,到N的所有整数,然后数一下其中出现的所有”1”的个数。

例如:

N=2,写下1,2。这样只出现了1个”1”。

N=12,我们会写下1,2,3,4,5,6,7,8,9,10,11,12。这样1的个数是5.

问题是:

写出一个函数f(N),返回1到N之间出现”1”的个数,比如f(12)=5 在32为整数范围内,满足条件”f(N)=N”的最大的N是多少?

3、一个数在数组里面重复出现次数超过一半,求这个数。

1,最容易想到的就是将这个数组排序,然后取出中间的数。最好的排序算法的时间复杂度是O(nlogn).这显然不符合某些公司的要求。

2,遍历一遍数组即找出我们所求的数。在遍历的过程中如果每次删除两个不同的数,那么,在剩下的数的列表中,我们所求的这个数的数量仍然超过总数的一半。

int Find(int arr[], int N)
{
    int candidate;
    int nTimes, i;
    for(i = 0; i < N; i++)
    {
        if(nTimes == 0)
        {
            candidate = arr[i];
            nTimes++;
        }
        else
        {
              if(candidate == arr[i])
                    nTimes++;
              else
                    nTime--;
         }
    }

    return candidate;
}

3,两个指针,每次取最前面的两个,如果相等,就保留,一个指针后移1位,不同,就同时抛出。最后剩下的数组都是一样的,即所求。