2.给定一个32bit的数值，如果输出比特位反转后的值，如对于4bit的二进制值1011，翻转后为1101。要求复杂度O(lgn),n
为比特位数
31 个解决方案
#1
第一个指针走k步时第二个指针开始走
两指针同步向前
当第一个走到尾节点时
第二个指针即为所求
两指针同步向前
当第一个走到尾节点时
第二个指针即为所求
#2
第二题
unsigned int reverse_32bit(register unsigned int x) {
register unsigned int y = 0x55555555;
x = (((x >> 1) & y) | ((x & y) << 1));
y = 0x33333333;
x = (((x >> 2) & y) | ((x & y) << 2));
y = 0x0f0f0f0f;
x = (((x >> 4) & y) | ((x & y) << 4));
y = 0x00ff00ff;
x = (((x >> 8) & y) | ((x & y) << 8));
return((x >> 16) | (x << 16));
}
#3
先说个普通的思路吧！
第一题
从头开始找，每找到下一个，计数+1，在不足k次时，一直记录第一个元素的指针，当计数大于k 等于 k + 1时，根据第一个元素的指针找到第二个元素的指针。
此后每次计数+1，均根据记录的指针找到下一个指针，一直到结尾。
也可以定义一个长度为k的指针数组T，再定义一个指向指针数组元素的指针p，这个指针指向的范围在T[0]和T[k - 1]之间循环，每次找到下一节点时，将该节点的指针赋值给p所指向的元素T[i],
一直到结尾。p下一个所指向的T[i],就是要找的元素。（相比上一种方法，空间浪费了，但不用每次都找下一个元素，可以快一点点）
第二题
不过未能达到O(lgn)的要求。
第一题
从头开始找，每找到下一个，计数+1，在不足k次时，一直记录第一个元素的指针，当计数大于k 等于 k + 1时，根据第一个元素的指针找到第二个元素的指针。
此后每次计数+1，均根据记录的指针找到下一个指针，一直到结尾。
也可以定义一个长度为k的指针数组T，再定义一个指向指针数组元素的指针p，这个指针指向的范围在T[0]和T[k - 1]之间循环，每次找到下一节点时，将该节点的指针赋值给p所指向的元素T[i],
一直到结尾。p下一个所指向的T[i],就是要找的元素。（相比上一种方法，空间浪费了，但不用每次都找下一个元素，可以快一点点）
第二题
public int GetInverse(int source)
{
int target = 0;
while (source > 0)
{
target = (target << 1) | (source & 0x01);
source = source >> 1;
}
return target;
}
不过未能达到O(lgn)的要求。
#4
没想到，这么晚了还没抢到沙发，打字的功夫就被别人回答了，而且答案还比我的好！
挣点分真不容易！！！
挣点分真不容易！！！
#5
一楼的第一题的办法太好了!
#6
1楼高啊
#7
2楼的算法很赞……
#8
第一题：
用三个指针p1,p2,p3
p1,p2,p3先都指向head
1，先p1跑M步（M可以是k，如果k比较小，M可以是一个比k大的值），p2设置为p1
2，p1继续跑M步，如果p1没有到链表的尾，则p3设置为p2，p2设置为p1，继续第二步；
如果p1到了链表的尾，因为p1移动时记录了移动步数，所以从p3开始移动就可以到指定的节点。
这个方法如果链表比较长时比两个指针同时移动一步效率要高一些。
用三个指针p1,p2,p3
p1,p2,p3先都指向head
1，先p1跑M步（M可以是k，如果k比较小，M可以是一个比k大的值），p2设置为p1
2，p1继续跑M步，如果p1没有到链表的尾，则p3设置为p2，p2设置为p1，继续第二步；
如果p1到了链表的尾，因为p1移动时记录了移动步数，所以从p3开始移动就可以到指定的节点。
这个方法如果链表比较长时比两个指针同时移动一步效率要高一些。
#9
顶一个，算法真是一个有魅力的东西！
#10
第2题用查表法（256个字节的查表法，然后再组合在一起），O（1）的时间复杂度即可。
#11
能解释下为什么效率要高些吗
#12
是32bit 4个字节 表要4G内存
#13
第一题,我终于看到经典的算法了,不错.
#14
1楼的,思路不错.
#15
学习
#16
我认为一楼的答案即简洁又高效
#17
mark
#18
第二题的一个简便做法是利用补码：
unsigned int reverse_32bit(unsigned int n)
{
int k = n;
k = -k - 1;
unsigned int m = k;
return m;
}
另：我觉得题目的说法“要求复杂度O(lgn),n 为比特位数”有问题. 在此题中比特位数就是一个常数32, 怎么能以它规定复杂度?
unsigned int reverse_32bit(unsigned int n)
{
int k = n;
k = -k - 1;
unsigned int m = k;
return m;
}
另：我觉得题目的说法“要求复杂度O(lgn),n 为比特位数”有问题. 在此题中比特位数就是一个常数32, 怎么能以它规定复杂度?
#19
2题
依照题目意图
使用分治法
1.首先 将高n/2位与低n/2位交换
2.然后分治处理高n/2位,和低n/2位
3.分治中的原子操作是将x位数，其高x/2位于低x/2位交换
最终算法的时间复杂度为O(lgn)
依照题目意图
使用分治法
1.首先 将高n/2位与低n/2位交换
2.然后分治处理高n/2位,和低n/2位
3.分治中的原子操作是将x位数，其高x/2位于低x/2位交换
最终算法的时间复杂度为O(lgn)
#20
18楼给的结果是m+n=2^32-1,不符合要求啊
#21
19楼的解法复杂度O(nlogn),你这样的话交换太多次了,还不如直接第i位和n+1-i位直接交换,每两个位只需要进行1次交换操作,O(n)
如果基于交换的话绝对不会低于O(n),因为每位都得进行交换才能到达它应该待的位置
如果基于交换的话绝对不会低于O(n),因为每位都得进行交换才能到达它应该待的位置
#22
１８楼的同学提醒了我，可以用异或：ｎ︿０ｘＦＦＦＦＦＦＦＦ
#23
n^FFFF FFFF只是各位取非吧
#24
抱歉，我在18楼的解答误解题意了，此"反转"非彼"反转"。谢谢指正。
#25
阿2果然是牛人啊，实在是佩服
第二个题看来好半天才看懂啊
第二个题看来好半天才看懂啊
#26
不知第一题的高效指的是时间效率还是包括空间效率？
如果两者都包括，那么1楼确实是很好的算法，时间复杂度是f(n)=2n-k；如果只是时间效率的话，那么可以损失空间的话可以达到f(n)=n的时间复杂度。
如果两者都包括，那么1楼确实是很好的算法，时间复杂度是f(n)=2n-k；如果只是时间效率的话，那么可以损失空间的话可以达到f(n)=n的时间复杂度。
#27
第一题程序员面试宝典里有详细介绍
#28
第二个算法在FFT里就有用哎！很实用啊！
#29
参考8楼的思想，完成的程序.
有什么问题，大家多提下！
/////////////////////////////////////////////////////////////////////
struct node
{
int data;
node *next;
};
node *findK(node *head,int k)
{
node *p1,*p2,*p3;
int i,tmpk=1,scancount;
if (head==NULL) return NULL;
p1=head;
p2=p1;
scancount=k; //可K太小的话可以改大
while((p1=p1->next)!=NULL)
{
if (tmpk++==scancount)
{
tmpk=1;
p3=p2;
p2=p1;
}
}
if (tmpk<k)
{
for(i=0;i<tmpk+1;i++)
p3=p3->next;
return p3;
}
else if (tmpk>k)
{
for(i=0;i<tmpk-k+1;i++)
p2=p2->next;
return p2;
}
else return p2;
}
/////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
node *head=new node;
head->data=1;
head->next=NULL;
node *node1=head;
for (int i=2;i<100;i++)
{
node1->next=new node;
node1->next->data=i;
node1=node1->next;
}
node1->next=NULL;
node *ret=findK(head,1);
cout<<ret->data<<endl;
}
有什么问题，大家多提下！
/////////////////////////////////////////////////////////////////////
struct node
{
int data;
node *next;
};
node *findK(node *head,int k)
{
node *p1,*p2,*p3;
int i,tmpk=1,scancount;
if (head==NULL) return NULL;
p1=head;
p2=p1;
scancount=k; //可K太小的话可以改大
while((p1=p1->next)!=NULL)
{
if (tmpk++==scancount)
{
tmpk=1;
p3=p2;
p2=p1;
}
}
if (tmpk<k)
{
for(i=0;i<tmpk+1;i++)
p3=p3->next;
return p3;
}
else if (tmpk>k)
{
for(i=0;i<tmpk-k+1;i++)
p2=p2->next;
return p2;
}
else return p2;
}
/////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
node *head=new node;
head->data=1;
head->next=NULL;
node *node1=head;
for (int i=2;i<100;i++)
{
node1->next=new node;
node1->next->data=i;
node1=node1->next;
}
node1->next=NULL;
node *ret=findK(head,1);
cout<<ret->data<<endl;
}
#30
我认为一楼的答案即简洁又高效
#31
第二个问题可做如下解答
int convert_32bit(int n)
{
int i,j,k,ret=0,m=0x1;
for(i=1;i<=16,i*=2)
{
k=(n>>i)&m;//把高i位移到低位
j=m|n;
k^=j;
j^=k;
k^=j;//位异或运算，把k和n的值交换，实际交换的是n的低i位。
m=(m<<i)|m;
ret=(ret<<(i*2))|((k<<i)|j);
}
return ret;//右移位低位置0，与n位或
}
1 2 4 8 16
O（5*7）
int convert_32bit(int n)
{
int i,j,k,ret=0,m=0x1;
for(i=1;i<=16,i*=2)
{
k=(n>>i)&m;//把高i位移到低位
j=m|n;
k^=j;
j^=k;
k^=j;//位异或运算，把k和n的值交换，实际交换的是n的低i位。
m=(m<<i)|m;
ret=(ret<<(i*2))|((k<<i)|j);
}
return ret;//右移位低位置0，与n位或
}
1 2 4 8 16
O（5*7）
#1
第一个指针走k步时第二个指针开始走
两指针同步向前
当第一个走到尾节点时
第二个指针即为所求
两指针同步向前
当第一个走到尾节点时
第二个指针即为所求
#2
第二题
unsigned int reverse_32bit(register unsigned int x) {
register unsigned int y = 0x55555555;
x = (((x >> 1) & y) | ((x & y) << 1));
y = 0x33333333;
x = (((x >> 2) & y) | ((x & y) << 2));
y = 0x0f0f0f0f;
x = (((x >> 4) & y) | ((x & y) << 4));
y = 0x00ff00ff;
x = (((x >> 8) & y) | ((x & y) << 8));
return((x >> 16) | (x << 16));
}
#3
先说个普通的思路吧！
第一题
从头开始找，每找到下一个，计数+1，在不足k次时，一直记录第一个元素的指针，当计数大于k 等于 k + 1时，根据第一个元素的指针找到第二个元素的指针。
此后每次计数+1，均根据记录的指针找到下一个指针，一直到结尾。
也可以定义一个长度为k的指针数组T，再定义一个指向指针数组元素的指针p，这个指针指向的范围在T[0]和T[k - 1]之间循环，每次找到下一节点时，将该节点的指针赋值给p所指向的元素T[i],
一直到结尾。p下一个所指向的T[i],就是要找的元素。（相比上一种方法，空间浪费了，但不用每次都找下一个元素，可以快一点点）
第二题
不过未能达到O(lgn)的要求。
第一题
从头开始找，每找到下一个，计数+1，在不足k次时，一直记录第一个元素的指针，当计数大于k 等于 k + 1时，根据第一个元素的指针找到第二个元素的指针。
此后每次计数+1，均根据记录的指针找到下一个指针，一直到结尾。
也可以定义一个长度为k的指针数组T，再定义一个指向指针数组元素的指针p，这个指针指向的范围在T[0]和T[k - 1]之间循环，每次找到下一节点时，将该节点的指针赋值给p所指向的元素T[i],
一直到结尾。p下一个所指向的T[i],就是要找的元素。（相比上一种方法，空间浪费了，但不用每次都找下一个元素，可以快一点点）
第二题
public int GetInverse(int source)
{
int target = 0;
while (source > 0)
{
target = (target << 1) | (source & 0x01);
source = source >> 1;
}
return target;
}
不过未能达到O(lgn)的要求。
#4
没想到，这么晚了还没抢到沙发，打字的功夫就被别人回答了，而且答案还比我的好！
挣点分真不容易！！！
挣点分真不容易！！！
#5
一楼的第一题的办法太好了!
#6
1楼高啊
#7
2楼的算法很赞……
#8
第一题：
用三个指针p1,p2,p3
p1,p2,p3先都指向head
1，先p1跑M步（M可以是k，如果k比较小，M可以是一个比k大的值），p2设置为p1
2，p1继续跑M步，如果p1没有到链表的尾，则p3设置为p2，p2设置为p1，继续第二步；
如果p1到了链表的尾，因为p1移动时记录了移动步数，所以从p3开始移动就可以到指定的节点。
这个方法如果链表比较长时比两个指针同时移动一步效率要高一些。
用三个指针p1,p2,p3
p1,p2,p3先都指向head
1，先p1跑M步（M可以是k，如果k比较小，M可以是一个比k大的值），p2设置为p1
2，p1继续跑M步，如果p1没有到链表的尾，则p3设置为p2，p2设置为p1，继续第二步；
如果p1到了链表的尾，因为p1移动时记录了移动步数，所以从p3开始移动就可以到指定的节点。
这个方法如果链表比较长时比两个指针同时移动一步效率要高一些。
#9
顶一个，算法真是一个有魅力的东西！
#10
第2题用查表法（256个字节的查表法，然后再组合在一起），O（1）的时间复杂度即可。
#11
能解释下为什么效率要高些吗
#12
是32bit 4个字节 表要4G内存
#13
第一题,我终于看到经典的算法了,不错.
#14
1楼的,思路不错.
#15
学习
#16
我认为一楼的答案即简洁又高效
#17
mark
#18
第二题的一个简便做法是利用补码：
unsigned int reverse_32bit(unsigned int n)
{
int k = n;
k = -k - 1;
unsigned int m = k;
return m;
}
另：我觉得题目的说法“要求复杂度O(lgn),n 为比特位数”有问题. 在此题中比特位数就是一个常数32, 怎么能以它规定复杂度?
unsigned int reverse_32bit(unsigned int n)
{
int k = n;
k = -k - 1;
unsigned int m = k;
return m;
}
另：我觉得题目的说法“要求复杂度O(lgn),n 为比特位数”有问题. 在此题中比特位数就是一个常数32, 怎么能以它规定复杂度?
#19
2题
依照题目意图
使用分治法
1.首先 将高n/2位与低n/2位交换
2.然后分治处理高n/2位,和低n/2位
3.分治中的原子操作是将x位数，其高x/2位于低x/2位交换
最终算法的时间复杂度为O(lgn)
依照题目意图
使用分治法
1.首先 将高n/2位与低n/2位交换
2.然后分治处理高n/2位,和低n/2位
3.分治中的原子操作是将x位数，其高x/2位于低x/2位交换
最终算法的时间复杂度为O(lgn)
#20
18楼给的结果是m+n=2^32-1,不符合要求啊
#21
19楼的解法复杂度O(nlogn),你这样的话交换太多次了,还不如直接第i位和n+1-i位直接交换,每两个位只需要进行1次交换操作,O(n)
如果基于交换的话绝对不会低于O(n),因为每位都得进行交换才能到达它应该待的位置
如果基于交换的话绝对不会低于O(n),因为每位都得进行交换才能到达它应该待的位置
#22
１８楼的同学提醒了我，可以用异或：ｎ︿０ｘＦＦＦＦＦＦＦＦ
#23
n^FFFF FFFF只是各位取非吧
#24
抱歉，我在18楼的解答误解题意了，此"反转"非彼"反转"。谢谢指正。
#25
阿2果然是牛人啊，实在是佩服
第二个题看来好半天才看懂啊
第二个题看来好半天才看懂啊
#26
不知第一题的高效指的是时间效率还是包括空间效率？
如果两者都包括，那么1楼确实是很好的算法，时间复杂度是f(n)=2n-k；如果只是时间效率的话，那么可以损失空间的话可以达到f(n)=n的时间复杂度。
如果两者都包括，那么1楼确实是很好的算法，时间复杂度是f(n)=2n-k；如果只是时间效率的话，那么可以损失空间的话可以达到f(n)=n的时间复杂度。
#27
第一题程序员面试宝典里有详细介绍
#28
第二个算法在FFT里就有用哎！很实用啊！
#29
参考8楼的思想，完成的程序.
有什么问题，大家多提下！
/////////////////////////////////////////////////////////////////////
struct node
{
int data;
node *next;
};
node *findK(node *head,int k)
{
node *p1,*p2,*p3;
int i,tmpk=1,scancount;
if (head==NULL) return NULL;
p1=head;
p2=p1;
scancount=k; //可K太小的话可以改大
while((p1=p1->next)!=NULL)
{
if (tmpk++==scancount)
{
tmpk=1;
p3=p2;
p2=p1;
}
}
if (tmpk<k)
{
for(i=0;i<tmpk+1;i++)
p3=p3->next;
return p3;
}
else if (tmpk>k)
{
for(i=0;i<tmpk-k+1;i++)
p2=p2->next;
return p2;
}
else return p2;
}
/////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
node *head=new node;
head->data=1;
head->next=NULL;
node *node1=head;
for (int i=2;i<100;i++)
{
node1->next=new node;
node1->next->data=i;
node1=node1->next;
}
node1->next=NULL;
node *ret=findK(head,1);
cout<<ret->data<<endl;
}
有什么问题，大家多提下！
/////////////////////////////////////////////////////////////////////
struct node
{
int data;
node *next;
};
node *findK(node *head,int k)
{
node *p1,*p2,*p3;
int i,tmpk=1,scancount;
if (head==NULL) return NULL;
p1=head;
p2=p1;
scancount=k; //可K太小的话可以改大
while((p1=p1->next)!=NULL)
{
if (tmpk++==scancount)
{
tmpk=1;
p3=p2;
p2=p1;
}
}
if (tmpk<k)
{
for(i=0;i<tmpk+1;i++)
p3=p3->next;
return p3;
}
else if (tmpk>k)
{
for(i=0;i<tmpk-k+1;i++)
p2=p2->next;
return p2;
}
else return p2;
}
/////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
node *head=new node;
head->data=1;
head->next=NULL;
node *node1=head;
for (int i=2;i<100;i++)
{
node1->next=new node;
node1->next->data=i;
node1=node1->next;
}
node1->next=NULL;
node *ret=findK(head,1);
cout<<ret->data<<endl;
}
#30
我认为一楼的答案即简洁又高效
#31
第二个问题可做如下解答
int convert_32bit(int n)
{
int i,j,k,ret=0,m=0x1;
for(i=1;i<=16,i*=2)
{
k=(n>>i)&m;//把高i位移到低位
j=m|n;
k^=j;
j^=k;
k^=j;//位异或运算，把k和n的值交换，实际交换的是n的低i位。
m=(m<<i)|m;
ret=(ret<<(i*2))|((k<<i)|j);
}
return ret;//右移位低位置0，与n位或
}
1 2 4 8 16
O（5*7）
int convert_32bit(int n)
{
int i,j,k,ret=0,m=0x1;
for(i=1;i<=16,i*=2)
{
k=(n>>i)&m;//把高i位移到低位
j=m|n;
k^=j;
j^=k;
k^=j;//位异或运算，把k和n的值交换，实际交换的是n的低i位。
m=(m<<i)|m;
ret=(ret<<(i*2))|((k<<i)|j);
}
return ret;//右移位低位置0，与n位或
}
1 2 4 8 16
O（5*7）