Re 求助:5道算法题.

http://www.newsmth.net/frames.html

发信人: cutepig (cutepig), 信区: Algorithm
标  题: 求助:5道算法题
发信站: 水木社区 (Sat Nov 10 18:25:06 2007), 站内


1)given a integer, output its previous and next neighbor number which has the same number of bit 1 in their binary representation.
(1)只想到一种很笨的方法,就是将这个数递增或者递减,直到找到一个和它1的位数一样多的为止,应该有更好的方法
(2)
满足条件的比这个数大的数应该是这个数从最低位开始,找到的第一个的01组合对调。
满足条件的比这个数小的数应该是这个数从最低位开始,找到的第一个的10组合对调。

2) Given 1 GB memory, input a file which contians 4 billion integers, output one integer that is not in the file. What if you have only 10 MB memory?
这个如果用一位表示一个数的存在与否的话,需要2^32bits=2^32/8bytes=2^29=512MB内存,用10M的话似乎只能读多次文件,每次判断某一部分数存在与否,有没有更好的办法?

3) how to divide an integer array into 2 sub-arrays and make their averages equal? e.g. a[left_portion]/left_portion_num == a[right_portion]/right_portion_num.

4)Given n unsigned integer, output 2 integers which has the maximum result after XOR.
莫非要遍历所有可能的组合?

5)Input an integer array of size n and an integer k (k<=n), output all subsets of size k.
(1)这个类似于全排列的生成算法吧,想出一个递归的回溯方法
array,n:数组和数组大小
k:子数列大小
void output(int *array,int n,int k)
{
   static int used[n];//这个静态数组记录是否该元素已经输出了,初始化为0
   static int outdata[k];//记录已经输出的元素
   if k<=0 ,return;
   对于array的每一个未输出的元素array[i]
  {
     将该元素放到outdata中,标记used[i]=1;
     如果满k个了,则输出outdata的数据
     否则,递归调用output(array,n,k-1)
     回溯,令used[i]=0;
  }
}
(2)或者写一个Next函数用来计算当前排列的下一个排列
BOOL Next(int *data,int nmax,int k)
{
int i;
#define MyMax(i) (nmax-k+i)
for (i=k-1;i>=0 ;i--)//从后向前找到第一个可以增加的数
{
ASSERT(data[i]
>=0 && data[i]<=MyMax(i));
if(data[i]<MyMax(i))
{
break;
}
}
if(i>=0)//将该位++,后面各位递增
{
data[i]
++;
for (int j=i+1;j<k;j++)
{
data[j]
=data[j-1]+1;
ASSERT(data[j]
<=MyMax(j))
}
return TRUE;
}
else
return FALSE;

}

初始化data={0,...,k-1},再一直调用Next就可以得到所有的排列
发信人: scottfield (金蛇郎君), 信区: Algorithm
标  题: Re: 求助:5道算法题
发信站: 水木社区 (Sat Nov 10 20:18:14 2007), 站内

第三个,可以参考CLRS,可以线性时间求得,是weighted-select problem
把值看成权就行了。

发信人: scottfield (金蛇郎君), 信区: Algorithm
标  题: Re: 求助:5道算法题
发信站: 水木社区 (Sat Nov 10 20:24:24 2007), 站内

第四题,XOR是 00->1 11->1是不?

则只要找出两个最高位相同的倍数最多的不就行了?

用Significant-bit Radix Sort 


发信人: ttl (小驴|主ID), 信区: Algorithm
标  题: Re: 求助:5道算法题
发信站: 水木社区 (Sat Nov 10 20:36:27 2007), 站内

【 在 wlalbert (找个打我球的女朋友) 的大作中提到: 】
如何用c++实现?
【 在 cutepig (cutepig) 的大作中提到: 】
: 似乎真的是这样呀
: 满足条件的比这个数大的数应该是这个数从最低位开始,找到的第一个的01组合对调。
: 满足条件的比这个数小的数应该是这个数从最低位开始,找到的第一个的10组合对调。
: ...................

void find(int i)
{
        int f = 3; // 11
        int pf = 2; // 10
        int nf = 1; // 01

        int p = 0; // 小
        int n = 0; // 大

        while (f < 4 * i)
        {
                int tmp = f & i;
                if (!p)
                {
                        if (0 == (tmp ^ pf))
                                p = i ^ f;
                }
                if (!n)
                {
                        if (0 == (tmp ^ nf))
                                n = i ^ f;
                }

                f  <<= 1;
                pf <<= 1;
                nf <<= 1;
        }

        cout << p << endl;
        cout << n << endl;
}
发信人: zgx03 (时间旅客), 信区: Algorithm
标  题: Re: 求助:5道算法题
发信站: 水木社区 (Sat Nov 10 21:07:26 2007), 站内

第4题这么做,
设原数组为A,里面的元素取反后形成第二个数组B,把这两个数组合起来形成数组C。
把C排一下序,找C的相邻两个分别属于A和B且二进制最高几位连续相同最多的,即可。
复杂度NlogN。

Powered by Jekyll and Theme by solid

本站总访问量