第一个回帖能不能给个礼物啊 ^_^
1
把两个单向链表都反转，然后从头遍历反转后的两个单向链表，发现相同位置出现值相同的节点即为所求节点
可以用原链表保存反转的链表，因此空间复杂度为O(1)
时间复杂度是O(n)
方法有些笨，不知道有没有更好时间复杂度的方法

2
红为0，蓝为1
则10010111为一种染法
应该不是唯一的

3
首先用该数N的个位是0，1，4，5，6，9判断一下
然后根据N的位数估算它的平方根的位数范围，然后用二分法查找这个位数范围的数

4
这个我是想不出最好的办法，
只是见过：常数时间，常数空间
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u
– ((u >> 1) & 033333333333)
– ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;
}

5
int n = 0;
for(p=log_start; p!=NULL;p=log_next){
int t=rand() % ++n;
if (t

———————
部分解答一下:

1. 有更好的不反转链表的方法 (切忌在面试中假设你可以修改给出的数据结构). 而且反转的时候第一个节点要被反转成两个往外的链接(他们是共享这个节点的, 因此, 我觉得此法不可行)

2. 对的

3. 没有唯一解, 假如满分10分, 可以给你打7.5了

4. 说了不许用 mask 了, 您还是用了. (&一个常数　叫做使用 mask)

5. 被WP 截掉了, 能否说一下你的方法思路

1
先求出两个链表的长度n1,n2，相差c=abs(n2-n1)
然后先遍历长链表c个元素，然后两个链表一对一遍历，碰到相同值的就是所求节点这样虽然好些，但时间复杂度还是O(n)，只是n的系数小些了

开始反转那个，我也考虑到反转会修改原数据结构了，只是想想反转完在反转回去就等于没破坏原结构，这样复杂度还是O(n)，就是系数要乘个1.x :(

另外你说“反转的时候第一个节点要被反转成两个往外的链接，他们是共享这个节点的“，我反转时第一个节点就指向NULL了，这样不行吗？

3
期待你最后的10分解 :)

4
int BitCount(unsigned int u)
{
unsigned int uCount=u;
do
{
u=u>>1;
uCount -= u;
}
while(u);
}

5
先初始化这些东西
用wanted[100]来保存所选记录
n=0表示记录序号
k=0表示当前要给wanted的第k个元素赋值了（如果k==100了，就k=0）

然后从头遍历记录:{用rand()生成一个随机数r，求r对++n的余数，如果余数小于100，就把当前记录放到wanted[k++]里}
遍历完记录，wanted里就是所选的100条记录

1, 你现在的解法是自然的, 最好的. 改变数据结构呀这些都不是好方法.

3, 我也在想

5. 看上去和正确答案很相似了, 但不对. 想想你是等概率取的么, 不是. 第一个元素被取到的概率居然是1/2, 往后越来越小.

5
从头遍历记录:{求n++对100的商m以及余数re，用rand()生成一个随机数r，如果r整除(m+1)，就把当前记录放到wanted[re]里}
遍历完记录，wanted里就是所选的100条记录
思路是：把记录按照记录号对100的余数等分成100份，遍历时从每份中等概率的选一个记录出来。
对于记录号为0,100,200,300…100*(N-1)这份记录中，选取k*100号记录的概率是：
(1/(k+1))*(1-1/(k+2))*(1-1/(k+3))*(1-1/(k+4))…=1/N，是等概率的

3难道还有更好的解法？
4应该是这样吧
int BitCount(unsigned int u)
{
int uCount=0;
while(u)
{
u=u>>1;
uCount++;
}
return uCount;
}

我也被问过

很多情况下,判定不一定要比求解容易,但是对于一个n位二进制整数,请问有无判断它是否为平方数的O(n)算法(仅用到二进制加,减和移位)?

但不知道怎么做。

最后一个的第二个不太懂，根据什么东西估算？

zeaster, 你的那个解法还是有问题的, 全局的等概率不代表就是关于100同余后余数各不相同, 而且, 从概率上说, 各不相同的概率还比较小 (生日悖论).

@zhang,
还是用概率的方法, 每来一个PV, 按照概率为1/500 ++我的计数器

4 has more neat solution: @
http://infolab.stanford.edu/~manku/bitcount/bitcount.html