6.{
7.if（str[j]<='z'&&str[j]>='a'）
8.{
9.i++;
10.swap（str[i],str[j]）;
11.}
12.}
13.}
谷歌笔试题：
在重男轻女的国家里，男女的比例是多少？
在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。
这样的国家，男女比例会是多少？
还是1：
1。
在所有出生的第一个小孩中，男女比例是1：
1；在所有出生的第二个小孩中，男女比例是1：
1；....在所有出生的第n个小孩中，男女比例还是1：
1。
所以总的男女比例是1：
1。
谷歌笔试题：
如何拷贝特殊链表
有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand，如何拷贝这个特殊链表？
拷贝pNext指针非常容易，所以题目的难点是如何拷贝pRand指针。
假设原来链表为A1->A2->...->An，新拷贝链表是B1->B2->...->Bn。
为了能够快速的找到pRand指向的节点，并把对应的关系拷贝到B中。
我们可以将两个链表合并成
A1->B1->A2->B2->...->An->Bn。
从A1节点出发，很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx，将B1的pRand指向Bx也就完成了B1节点pRand的拷贝。
依次类推。
当所有节点的pRand都拷贝完成后，再将合并链表分成两个链表就可以了。
1.classListNode
2.{
3.intvalue;
4.ListNode*p_next;
5.ListNOde*p_rand;
6.publicListNode（intv,ListNode*next,ListNode*rand）:
value（v）,p_next（next）,p_rand（rand）
7.{
8.}
9.};
10.ListNode*copyList（ListNode*p）
11.{
12.if（p!
=null）
13.{
14./*构建交叉数组p0->q0->p1->q1->p2->q2...*/
15.ListNOde*ppre=p;
16.ListNode*post=->next;
17.while（pre!
=null）
18.{
19.pre->next=newListNode（pre->value,post,pre->p_rand->p_next）;
20.pre=last;
21.lastlast=last->p_next;
22.}
23./*拆分成被拷贝数组和拷贝数组p0->p1->p2....;q0->q1->q2....*/
24.ppre=p;
25.ListNode*res=p->p_next;
26.while（res->p_next!
=null）
27.{
28.p->p_next=res->p_next;
29.res->p_next=res->p_next->p_next;
30.}
31.returnres;
32.}else
33.{
34.returnp;
35.}
36.}
如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？
（假设为常概率条件下）
假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是（1-x）^3，也就是0.05。
所以得到方程（1-x）^3=0.05
解方程得到x大约是0.63。
谷歌笔试题：
从25匹马中找出最快的3匹
最少需要7次。
首先将马分成a,b,c,d,e5个组，每组5匹，每组单独比赛。
然后将每组的第一名放在一起比赛。
假设结果如下
a0,a1,a2,a3,a4
b0,b1,b2,b3,b4
c0,c1,c2,c3,c4
d0,d1,d2,d3,d4
e0,e1,e2,e3,e4
其中a,b,c,d,e小组都是按照名次排列（速度a0>a1>a2>a3>a4,b0>b1....）。
并第6次比赛的结果为a0>b0>c0>d0>e0。
那么第6次比赛结束后，我们知道最快的一匹为a0。
我们知道第2名的马一定是a1或者b0，所以在接下来的比赛中要包含这两匹马。
如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。
也就是说第2名和第3名一定在a1，a2，b0，b1和c0当中，所以在第7场比赛中包括这5匹马就可以得到第2名和第3名。
所以7次比赛就可以获得前3名的马。
谷歌笔试题：
海盗分金问题
有5个海盗，按照等级从5到1排列。
最大的海盗有权提议他们如何分享100枚金币。
但其他人要对此表决，如果多数（所有人中的多数）反对，那他就会被杀死。
他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？
分配方案是98，0，1，0，1。
5级海盗会不会被杀死，取决于5级海盗死后其他海盗是否会获得更多的利益。
如果可以获得更多的利益，则肯定会反对，如果会获得更少的利益，则肯定会支持，如果利益没有变化，则反对或支持都可以。
如果5级海盗死了，则有4级海盗分配，4级海盗面临同样的问题，需要看自己死后的利益分配变化。
然后是3级海盗，2级海盗。
2级海盗无论提出什么方案，都不会有多数人反对（自己支持，另一个人反对不能构成多数反对）。
所以2级海盗肯定会提出100，0的分配方案，自己独享所有金币。
猜到2级海盗的分配方案后，3级海盗会提出99，0，1的分配方案。
这样1级海盗因获得了比2级海盗方案中更多的金币，所以会支持3级海盗的方案。
猜到3级海盗的分配方案后，4级海盗会提出99，0，1，0的分配方案。
这样2级海盗获得了比3级海盗方案中更多的金币，所以会支持4级海盗的方案。
猜到4级海盗的分配方案后，5级海盗会提出98，0，1，0，1的分配方案。
这样1级海盗和3级海盗获得了比4级海盗方案中更多的金币，所以会支持5级海盗的方案。
谷歌笔试题：
4人过桥问题
4个人晚上要穿过一座索桥回到他们的营地。
可惜他们手上只有一支只能再坚持17分钟的手电筒。
通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。
这四个人过索桥的速度都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三个5分钟，最慢的那个要10分钟。
他们怎样才能在17分钟内全部走过索桥？
1）第一个和第二个一起过去，用掉2分钟；
2）第一个回来，用掉1分钟；
3）第三个和第四个一起过去，用掉10分钟；
4）第二个回来，用掉2分钟；
5）第一个和第二个一起过去，用掉2分钟。
总共用掉17分钟。
谷歌笔试题：
如何从8只球中找出比较重的一个
你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。
怎样能够用天平仅称两次将那个重一些的球找出来。
解答：
先取6个，天平上一边3个，同重则称剩余2个即可；不同重，则取重的3个中的2个来称。
分析：
此题可以通过倒推法来解决。
如果我们知道重球在某两个球中，则可以通过天平两边各放一个，比较重量发现重球。
如果我们知道重球在某三个球中，则可以通过天平两边各放一个，如果一样重，则第三个球是重球，否则天平上较重的即是重球。
如果我们知道重球在大于等于四个球中，则不能通过一次称重发现重球。
所以通过第一次称重，我们必须将重球限定在某两个或三个球当中。
另外，天平两端放的球数应该相等，否则结果基本没有意义。
满足两端球相等的所有可能的比较方法
左，右
1，1
2，2
3，3
4，4
再考虑到必须将重球限定在2或3个球中，第一次只能采取3，3的比较方法。
此题还可以扩展一下：
在m只大小相同的球中，m-1只重量相同，另外一只比较重。
问需要用天平称多少次才能将重球找出来？
从上面的分析中可以知道，称一次最多可以
-将重球从3个球中找出来。
-将重球从9个球中限定在3个球中。
-将重球从27个球中限定在9个球中。
.....
所以，称n次最多可以将重球从3^n中找出来。
倒推回去也就可以获得m个球需要称多少次。
或者
我们用i+表示第i个球比较重。
共有8种可能性：
1+;2+;3+;4+;5+;6+;7+;8+;
将123与456放在天秤上称，如果左边中，则可以将重球确定在123中，
即可能性为：
1+2+3+然后将1和2放在天秤两边称，如果左边重则重球为1，如果右边重，重球为2，如果平衡重球为3。
如果平衡：
7+8+将7和8放在天秤两边称，可以判断重球为7还是8
如果右边重：
4+5+6+同球123的情况。
【编辑推荐】
IT名企面试：
IBM笔试题
在IBM公司进行面试的时候，首先考察的则是基础知识。
那么下面就总结了一些IBM笔试题，以供大家参考。
IBM笔试题：
有一座山，山上有座庙，只有一条路可以从山上的庙到山脚，每周一早上8点，有一个聪明的小和尚去山下化缘，周二早上8点从山脚回山上的庙里，小和尚的上下山的速度是任意的，在每个往返中，他总是能在周一和周二的同一钟点到达山路上的同一点。
例如，有一次他发现星期一的8点30和星期二的8点30他都到了山路靠山脚的3/4的地方，问这是为什么？
答案一：
可以用画图法来解释：
在一个平面上，x轴代表从8点开始的时间，y轴代表距庙的距离。
那么从庙到山脚就是一条从左下到右上的一条曲线，从山脚到庙就是一条从左上到右下的一条曲线。
考虑到两条曲线的起始点和终点，两线必定交于一点。
答案二：
还有一种更简单的解释，是让两个人从山顶和山脚同时相向而行，一定有一个时刻相遇，这样就证明了。
IBM笔试题：
在一个平面上画1999条直线，最多能将这一平面划分成多少个部分？
没有直线时有一个空间；
（1）
1条直线时，这条这些可以将这个空间分成两个；（1+1）
2条直线时，第二条直线可以和第一条直线相交，这样第二条直线可以将两个空间分成四个；（1+1+2）
....
注意到画每条直线时能增加多少个空间，取决于此直线从多少个空间中通过。
而从多少个空间中通过，取决于和多少条直线相交。
例如，如果一条直线和其它5条直线相交，那么最大可以通过6个空间，此直线可以增加6个子空间。
画每条直线时，能相交的直线数为总的已经画过的直线。
所以总的空间数最多为
1+1+2+3+...+1999=1999001
IBM笔试题：
不均匀分布的香，每根香烧完的时间是一个小时，你能用什么方法来确定一段15分钟的时间？
第一根点燃两头，第二根只点一头。
当第一根烧完时，时间过去了30分钟，所以第二根还能烧30分钟。
这时点燃第二根的另外一头，第二根香还能烧的时间就是15分钟。
IBM笔试题：
有27个人去买矿泉水，商店正好在搞三个空矿泉水瓶可以换一瓶矿泉水的活动，他们至少要买几瓶矿泉水才能每人喝到一瓶矿泉水？
答案一：
如果开始买3瓶，那么可以四个人喝，并且还能剩一个空瓶。
如果开始买9瓶，可以13个人喝，最后还剩一个空瓶。
如果开始买18瓶，那么26个人喝，可以剩下两个空瓶。
如果开始买19瓶，那么27个人喝，最后剩下三个空瓶。
所以最少买19瓶。
如果可以向商店先欲借一个空瓶，那么买18瓶，最后一个人喝完再将空瓶还给商店。
那么买18瓶也可以满足要求。
答案二：
x+x/3+x/3^2+...=x/（1-1/3）=27
x=18;
IBM笔试题：
c++中引用和指针有什么不同？
指针加上什么限制等于引用？
引用不是一个变量，它只表示该引用名是目标变量名的一个别名，它本身不是一种数据类型，因此引用本身不占存储单元，系统也不给引用分配存储单元。
引用一经确定就不能修改。
指针是一个变量，需要在内存中分配空间，此空间中存储所指对象的地址。
由于指针是一个普通变量，所以其值还可以通过重新赋值来改变。
把指针定义为const后，其值就不能改变了，功能和引用类似，但有本质的区别。
IBM笔试题：
一普查员问一女人，“你有多少个孩子，他们多少岁？
”
女人回答：
“我有三个孩子，他们的岁数相乘是36，岁数相加就等于旁边屋的门牌号码。
“普查员立刻走到旁边屋，看了一看，回来说：
“我还需要多少资料。
”女人回答：
“我现在很忙，我最大的孩子正在楼
升级会员 