求助几道面试题

1.写一个宏   判断a和b的大小，不能有大于，小于和if语句

2.数组有1000个元素，里面应该存在1-1000的不重复值，但是现在有一个值重复了，只扫描数组一遍，找出那个重复的

3.如何最快的逆序一个链表呢？

4.给一个unsigned int的值，求该值二进制位中有几个1.

37 个解决方案

#1

1.不用XXX实现XXX，都是下身作痛题不解释，网上搜去，很多

2.全部累加，看和标准不重复的相差多少，就知道重复的是那个，时间复杂度O(n)，空间复杂度O(1)。

3.把所有的next指针反向即可

4.unsigned int只有32位，不需要什么技巧，直接草稿纸写一遍都花不了多少时间

#2

1. a,b int 32

#define XXOO(a,b) (b-a)&0x8000

#3

来学习的。。。

#4

1.写一个宏 判断a和b的大小，不能有大于，小于和if语句
#define max(a, b) \
((((a) - (b)) & (1 << ((sizeof(a) << 3) - 1))) ? (b) : (a))

2.数组有1000个元素，里面应该存在1-1000的不重复值，但是现在有一个值重复了，只扫描数组一遍，找出那个重复的
注意，这里有个重复必然会有个缺少的，所以使用求和再相减并不合适
unsigned char table[1001] = {0};

for (i = 0; i < size; ++i)
{
    if (2 == ++table[src[i]])
        return src[i];
}



3.如何最快的逆序一个链表呢？
一般逆序链表就是使用三个指针，遍历一遍就可以了
node *p1 = head;
node *p2 = p1->next;
node *p3 = p2->next;

p1->next = NULL;
while (p3 != NULL)
{ 
    p2->next = p1;
    p1 = p2;
    p2 = p3;
    p3 = p3->next;
}
p2->next = p1;

return p2;


如果链表的数据比较小，也可以使用vector存放链表中的数据
然后直接修改链表数据达到逆序效果。



4.给一个unsigned int的值，求该值二进制位中有几个1. 
int func(unsigned int val)
{
    int res = 0;
    
    while (val)
    {
        val &= (val - 1);
        ++res;
    }
    
    return res;
}

#5

4题：
c/c++:
 unsigned int GetBitNumOfOne_ByLoop3(unsigned int nValue)
 {
  unsigned int nBitNum = 0;
  while(0 < nValue)
  {
   nValue &=(nValue - 1);
   nBitNum++;
  }
  return nBitNum;
}

#6

引用 2 楼 txdgtwpv 的回复:

1. a,b int 32

#define XXOO(a,b) (b-a)&amp;0x8000

哈哈，XXOO，面试官看到这个就喷了

#7

引用 1 楼 jackyjkchen 的回复:

1.不用XXX实现XXX，都是下身作痛题不解释，网上搜去，很多

2.全部累加，看和标准不重复的相差多少，就知道重复的是那个，时间复杂度O(n)，空间复杂度O(1)。

3.把所有的next指针反向即可

4.unsigned int只有32位，不需要什么技巧，直接草稿纸写一遍都花不了多少时间

-----
第二题我想过   但是只是知道重复的那个值比缺少的那个值的差值，并不能准确知道是谁重复呢

#8

第二个。。。

int array[1000];//原数组
int index[1000];
int rst = 0;//重复值
memset(index, 0, sizeof(int)*1000);
for(int i = 0; i < 1000; i++)
{
  index[array[i]]++;
  if(index[array[i]] == 2)
  {
     rst = array[i];
     break;
  }
}

#9

1 #define MAX(a,b) ((a+b)+abs(a-b))/2;
2 数组遍历一遍，同时保存数据，没到一个数据和保存的数据比较。时间复杂度O(n2)空间复杂度O(n);
3 从头遍历一遍链表，同时新建链表。每次在表头插入。
4 
  int sum=0;
  int a=0x0001;
  for(i=1;i<=16;i++)
  {
     if(data&a)
        sum++;
      a<<1;
  }

#10

引用 4 楼 we_sky2008 的回复:

1.写一个宏 判断a和b的大小，不能有大于，小于和if语句
#define max(a, b) \
((((a) - (b)) &amp; (1 << ((sizeof(a) << 3) - 1))) ? (b) : (a))

2.数组有1000个元素，里面应该存在1-1000的不重复值，但是现在有一个值重复了，只扫描数组一遍，找出那个重复的
注意，这里有个重复必然会有个缺少的，所以使……

++

#11

学习学习学习学习学习..........

#12

mark!

引用 8 楼 lanxue_1988 的回复:

第二个。。。

C/C++ code

int array[1000];//原数组
int index[1000];
int rst = 0;//重复值
memset(index, 0, sizeof(int)*1000);
for(int i = 0; i < 1000; i++)
{
  index[array[i]]++;
  if(index[array[i]] ==……

#13

#define max(a, b) \
((((a) - (b)) &amp; (1 << ((sizeof(a) << 3) - 1))) ? (b) : (a))
这个是错误的,"error C2296: '&' : illegal, left operand has type 'double'"

#define MAX(a,b) ((a+b)+abs(a-b))/2;
这个也有问题,分号出现在这里不能够将宏应用在表达式里面;此宏不能判断double的数据类型,例如:double a=0.1, b=0.11; MAX(a,b)的结果是0.105既不是a也不是b.

#14

道理都被上面的各位占了，我只好在这里顶顶啦。

#15

#include "stdafx.h"
#include <iostream>
using namespace std;

int NumbersOf1(unsigned int n)
{
int res = 0;
int temp = 1;
int size = sizeof(unsigned) * 8;
for (int i = 0; i < size; ++i)
{
if (0 != ((1<<i)&n))
res++;
}
return res;
}
int main()
{
cout<<NumbersOf1(15)<<endl;
}

#16

看了前面大家的做法，发现第一个题的做法都是错误的，第一个题目不能直接上来就进行加法运算或者减法运算的，a、b的符号不知道，不能进行加、减操作的，贸然进行加、减操作就会溢出的，应该先判断a、b的符号是否相同，相同符号的符号才是可以相减的，否则就会溢出，符号不同的时候，直接判断最高位的符号位就可以比较a和b的大小了。。

#17

#define MIN(a,b) ((a>>31==0 && b>>31==1) | ((a>>31)^(b>>31)==0 && (a-b)>>31==0))?b:a

应该首先判断符号是否相同，然后在进行相减操作来判断符号位是0或1

#18

学习学习

#19

学习学习

#20

引用 8 楼 lanxue_1988 的回复:

第二个。。。
C/C++ code

int array[1000];//原数组
int index[1000];
int rst = 0;//重复值
memset(index, 0, sizeof(int)*1000);
for(int i = 0; i < 1000; i++)
{
  index[array[i]]++;
  if(index[array[i]] == 2)
  {
  ……

此处如果array[i]=1000的话index[1000]会越界，建议把index数组的大小设为1001

#21

学习来了

#22

引用 20 楼 yangling18 的回复:

引用 8 楼 lanxue_1988 的回复:
第二个。。。
C/C++ code

int array[1000];//原数组
int index[1000];
int rst = 0;//重复值
memset(index, 0, sizeof(int)*1000);
for(int i = 0; i < 1000; i++)
{
  index[array[i]]++;
……

++

#23

接分 回复内容太短了！

#24

该回复于2011-09-21 09:45:59被版主删除

#25

就喜欢考怪题

#26

第二题可以用异或，从第一个开始与后一个（设为n）做异或，判断结果，如果结果为0，则判断n为这个重复的数字，（因为相同的数字异或后为0）

#27

啊呀好难啊

#28

引用 26 楼 yanggenxing 的回复:

第二题可以用异或，从第一个开始与后一个（设为n）做异或，判断结果，如果结果为0，则判断n为这个重复的数字，（因为相同的数字异或后为0）

题目没说重复的两个数是相邻的。

#29

Integer[] num={1,2,3,4,5,6,7,8,9,10,3};
int repeat = 0;//记录上一个值
boolean flag = false;//是否重复
for(int n : num){
if(repeat == n){
flag = true;
break;
}else{
repeat = n;
}
}
if(flag)System.out.println(repeat);//输出重复值

#30

2. x1+x2+ ... + xn = A   正常情况A1
   x1*x1+x2*x2 + ... +xn*xn=B 正常情况B1

 a = (重复的)
 b =（缺少的）

a - b = A-A1
a*a - b*b = B- B1

解方程。

4.应用海明码，在log（length）时间复杂读解出。

引用 1 楼 jackyjkchen 的回复:

==========================================
1.不用XXX实现XXX，都是下身作痛题不解释，网上搜去，很多

2.全部累加，看和标准不重复的相差多少，就知道重复的是那个，时间复杂度O(n)，空间复杂度O(1)。

3.把所有的next指针反向即可

4.unsigned int只有32位，不需要什么技巧，直接草稿纸写一遍都花不了多少时间

#31

第二题：
void FindRepeat(int array[], int length)
{
    int index=array[length-1];
    while ( true )
    {
       if ( array[index]<0 )
           break;
       array[index]*=-1;
       index=array[index]*(-1);
    }
 
    cout<<"The repeat number is "<<index<<endl;
}

#32

mark

#33

2.直接用打点法
int Check(int[] objArray)
{
int[] tmp =new int[1000]
for(int i=0;i<1000;i++)
{
   if(tmp[objArray[i]-1]==1)
     return objArray[i];
   tmp[objArray[i]-1]==1;
}
}

#34

C# Code

#35

原来已经有人解答了 呵呵 卖弄了

#36

#define MAX(a,b) a>b?a:b

#37

引用 36 楼 wbhs2006 的回复:

#define MAX(a,b) a>b?a:b

不能用大于小于..