void quickSort(int* a, int start, int end)
{
if(start == end)
return;
int key = a[start];
int keyIndex = start;
int i = start, j = end;
int backward = 1;
int temp;
while(i != j)
{
if(backward)
{
for(; j > i; j--)
{
if(a[j] < key)
{
temp = a[j];
a[j] = a[i]; //a[i] == key
a[i] = temp;
keyIndex = j;
break;
}
}
backward = 0;
}
else
{
for(; i < j; i++)
{
if(a[i] > key)
{
temp = a[j]; //a[j] == key
a[j] = a[i];
a[i] = temp;
keyIndex = i;
break;
}
}
backward = 1;
}
}
quickSort(a, start, keyIndex);
if(keyIndex != end)
quickSort(a, keyIndex + 1, end);
}
2011年3月22日星期二
2011年2月19日星期六
Microsoft面试智力题
1.你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段 ，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费？
将金条切成1,2,4
day1：给1
day2：给2，工人归回1
day3：给1
day4：给4，工人归还1，2
day5：给1
day6：给2，工人归回1
day7：给1
2. 请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里还必须留有一份。
把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分给第8个人。
3.小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥？
1. 小明与弟弟过桥，小明回来，耗时4秒；
2. 小明与爸爸过河，弟弟回来，耗时9秒；
3. 妈妈与爷爷过河，小明回来，耗时13秒；
4. 小明与弟弟过河，耗时3秒，总共耗时29秒
4.一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑帽，依此类推，应该是关了几次灯，有几顶黑帽。
5. 烧一根不均匀的绳要用一个小时，如何用它来判断半个小时？如果有两根这样的绳子，如何判断45分钟。
1. 两边一起烧。烧绳子可理解为在单位时间内烧掉的绳子体积是一定的。两头点可理解为燃烧速度增加一倍，自然时间是原来的1/2。
2. 同时点燃其中一根绳子的两头和另一条绳子的一头。第一条燃尽的时候过去了半个小时。同时第二条绳子还能烧半个小时。此时马上点燃第二条绳子的另一头。燃尽时间为15分钟。相加为45分钟。
6. 有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约，另一辆火车以每小时20公里的速度从纽约开往洛杉矶。如果有一只鸟，以外30公里每小时的速度和两辆火车现时启动，从洛杉矶出发，碰到另辆车后返回，依次在两辆火车来回的飞行，直道两面辆火车相遇，请问，这只小鸟飞行了多长距离？
假设洛杉矶到纽约的距离为s
那小鸟飞行的距离就是(s/(15+20))*30。
7. U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同行则以较慢者的速度为准。Bono需花1分钟过桥，Edge需花2分钟过桥，Adam需花5分钟过桥，Larry需花10分钟过桥。他们要如何在17分钟内过桥呢？
1. 1和2过，1回，耗时3
2. 5和10过，2回，耗时12
3. 1和2过，耗时2。
总耗时17
8. 有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？
方法1:
1. 在天平一端2克砝码，将140克盐分成69和71克
2. 在天平一端7克砝码，将69克盐分成31克和38克
3.不放砝码，将38课盐平分
31+19 = 50
方法2
1. 先把2克和7克法码放一边,称出9克盐
2. 再把7克法码和9克盐放在一起,称出16克的盐
3. 再把9克盐和16克的盐放在左边,右边再称出25克盐
9+16+25 = 50
9. 你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了
1号罐取1个，2号罐取2个，3号罐取3个，4号罐取4个，称量该10个药丸，比正常重量重几就是几号罐的药有问题。
12. 对一批编号为1~100 全部开关朝上开的灯进行以下操作
凡是1 的倍数反方向拨一次开关2 的倍数反方向又拨一次开关3 的倍数反方向
又拨一次开关。问最后为关熄状态的灯的编号。
就某个亮着的灯而言，如果拨其开关的次数是奇数次，那么，结果它一定是关着的。根据题意可知，号码为N的灯，拨开关的次数等于N的约数（divisor）的个数，约数个数是奇数，则N一定是平方数。因为10的平方等于100，可知100以内共有10个平方数，即，最后关熄状态的灯共有10盏，编号为1、4、9、16、25、36、49、64、81、100。
13. 假设一张圆盘像唱机上的唱盘那样转动。这张盘一半是黑色，一半是白色
。假设你有数量不限的一些颜色传感器。要想确定圆盘转动的方向，你需要在它周
围摆多少个颜色传感器？它们应该被摆放在什么位置？
两个。可随意摆放，只要不同时放在圆的同一条直径上。根据变色顺序判断。
14. 假设时钟到了12点。注意时针和分针重叠在一起。在一天之中，时针和分
针共重叠多少次？你知道它们重叠时的具体时间吗？
23或22次(依据算不算24小时候的的12点整）。首先，将12小时划分成12个区间,[12, 1), [1,2)...[11, 12]。每个区间中都有一次相遇的时刻，其中在[12, 1)和[11, 12]相遇的时刻都是12点整。那么完成前半天12个小时就相遇了12次。在后12个小时中，由于起始的12点整已经被计算进入前12次中的一次，则后面只有11次相遇。所以总共23次。若不计算最后的那次12点整，则是22次（题目是一天之中，所以这个时候是第二天的开始）。
由于每次相遇到下一次相遇的时间是一定的，我们知道在12个小时内（包括12个小时) 相遇了12次, 又知道第一次和最后一次分别在这个时间段的起始和结束。那么可将这12个小时等分成11段，每一段的长度就是相遇的时间间隔。那么间隔 interval = 60*12 /11 = 720 / 11分钟。
知道间隔时间以后就可以从12点开始每次加上这个间隔时间算出每次相遇的时刻。
另一种方法是解方程。将时钟的一圈分成60个格子，设相遇时分针相对12点的时刻走了x个格子。我们知道分针每走一格，相当于时针走了1/12格。那么可根据指针重合条件列出方程。
假设我们要求[1, 2)区间内的相遇时刻，则有：
x / 12 = x - 5
类似的我们可以求出[2, 3), [3,4)...[11, 12]区间的相遇时刻([0, 1]和[11, 12]的相遇时刻相同)：
x / 12 = x - 10,
x / 12 = x - 15
...
x / 12 = x
15. 中间只隔一个数字的两个质数被称为质数对，比如17和19。证明质数对之
间的数字总能被6整除（假设这两个质数都大于6），并证明没有由三个质数组成
的质数对。
大于6的质数（prime number, 合数 composite number）都是奇数（只有2是唯一的偶质数）。所以质数对中间的数字一定是偶数，能被2整除（divisible）。由于在大于6的数中，任取三个连续的数字其中有且仅有一个数字能被3整除，而质数对的两个质数肯定不能被3整除（否则不是质数），则中间的那个数必定能被3整除。
一个数既能被2又能被3整除，则它能被6整除。
反证法（Reductio ad absurdum）：设x，x+2是一质数对，假设有连续三个质数组成的质数对，则x2+4或者x-2为质数。那么x-2，x和x+2，x+4是可能的两个质数对。则x-1或x+3应能被6整除。但是，由于x+1能被6整除，则x-1和x+3不可能被6整除。所以不存在三个质数组成的质数对。
16. 一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这 盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯。
同时开两盏，过一段时间关闭一盏。进门根据灯泡温度决定刚刚关掉的是哪一盏。
17. 假设你有8个球，其中一个略微重一些，但是找出这个球的惟一方法是将两个球放在天平上对比。最少要称多少次才能找出这个较重的球？
2次。
第一次分别取3个求放在天平两端，若不平横则重球在重的一端的三个球中。若不平衡，第二次任取两球放在天平两端，若不平衡则找到重球，若平横则剩下的一球为重球。
若第一次天平平衡。则重求在剩下的2个球中。第二次称量可直接找到重球。
18. 如果你有两个桶，一个装的是红色的颜料，另一个装的是蓝色的颜料。你从蓝色颜料桶里舀一杯，倒入红色颜料桶，再从红色颜料桶里舀一杯倒入蓝颜料桶。两个桶中红蓝颜料的比例哪个更高？通过算术的方式来证明这一点。
设两桶中红蓝颜料都是1。从红桶中舀去1/k。红桶中还有(k - 1)/k的红，蓝桶中有1的蓝和1/k的红。从蓝桶中舀去1/k。此1/k有(1/k) / (1+1/k) * 1 = 1/(k + 1)的蓝，和1/k - 1/k+1 = 1/(k*(k+1)的红。此时红桶中的红是 (k - 1)/k + 1/(k*(k+1) = k/(k + 1)。蓝桶中的蓝是1 - 1/(k + 1) = k/(k+1)。
比例相同。
将金条切成1,2,4
day1：给1
day2：给2，工人归回1
day3：给1
day4：给4，工人归还1，2
day5：给1
day6：给2，工人归回1
day7：给1
2. 请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里还必须留有一份。
把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分给第8个人。
3.小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥？
1. 小明与弟弟过桥，小明回来，耗时4秒；
2. 小明与爸爸过河，弟弟回来，耗时9秒；
3. 妈妈与爷爷过河，小明回来，耗时13秒；
4. 小明与弟弟过河，耗时3秒，总共耗时29秒
4.一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑帽，依此类推，应该是关了几次灯，有几顶黑帽。
5. 烧一根不均匀的绳要用一个小时，如何用它来判断半个小时？如果有两根这样的绳子，如何判断45分钟。
1. 两边一起烧。烧绳子可理解为在单位时间内烧掉的绳子体积是一定的。两头点可理解为燃烧速度增加一倍，自然时间是原来的1/2。
2. 同时点燃其中一根绳子的两头和另一条绳子的一头。第一条燃尽的时候过去了半个小时。同时第二条绳子还能烧半个小时。此时马上点燃第二条绳子的另一头。燃尽时间为15分钟。相加为45分钟。
6. 有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约，另一辆火车以每小时20公里的速度从纽约开往洛杉矶。如果有一只鸟，以外30公里每小时的速度和两辆火车现时启动，从洛杉矶出发，碰到另辆车后返回，依次在两辆火车来回的飞行，直道两面辆火车相遇，请问，这只小鸟飞行了多长距离？
假设洛杉矶到纽约的距离为s
那小鸟飞行的距离就是(s/(15+20))*30。
7. U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同行则以较慢者的速度为准。Bono需花1分钟过桥，Edge需花2分钟过桥，Adam需花5分钟过桥，Larry需花10分钟过桥。他们要如何在17分钟内过桥呢？
1. 1和2过，1回，耗时3
2. 5和10过，2回，耗时12
3. 1和2过，耗时2。
总耗时17
8. 有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？
方法1:
1. 在天平一端2克砝码，将140克盐分成69和71克
2. 在天平一端7克砝码，将69克盐分成31克和38克
3.不放砝码，将38课盐平分
31+19 = 50
方法2
1. 先把2克和7克法码放一边,称出9克盐
2. 再把7克法码和9克盐放在一起,称出16克的盐
3. 再把9克盐和16克的盐放在左边,右边再称出25克盐
9+16+25 = 50
9. 你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了
1号罐取1个，2号罐取2个，3号罐取3个，4号罐取4个，称量该10个药丸，比正常重量重几就是几号罐的药有问题。
10. 如果你有无穷多的水，一个3夸脱的和一个5夸脱的提桶，你如何准确称出4夸脱的水？
方法1
1. 加满3，倒入5
2. 加满3，倒入5直至其满，则3中剩1
3. 清空5，将3中的1倒入5
4. 加满3，倒入5，则5中为4
2. 加满3，倒入5直至其满，则3中剩1
3. 清空5，将3中的1倒入5
4. 加满3，倒入5，则5中为4
方法2
1. 加满5，倒入3加满
2. 清空3，将5中剩余的2倒入3
3. 加满5，倒入3加满，5中剩余的则为4
11. 你有一桶果冻，其中有黄色，绿色，红色三种，，闭上眼睛选出同样颜色的两个，抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
4个
11. 你有一桶果冻，其中有黄色，绿色，红色三种，，闭上眼睛选出同样颜色的两个，抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
4个
12. 对一批编号为1~100 全部开关朝上开的灯进行以下操作
凡是1 的倍数反方向拨一次开关2 的倍数反方向又拨一次开关3 的倍数反方向
又拨一次开关。问最后为关熄状态的灯的编号。
就某个亮着的灯而言，如果拨其开关的次数是奇数次，那么，结果它一定是关着的。根据题意可知，号码为N的灯，拨开关的次数等于N的约数（divisor）的个数，约数个数是奇数，则N一定是平方数。因为10的平方等于100，可知100以内共有10个平方数，即，最后关熄状态的灯共有10盏，编号为1、4、9、16、25、36、49、64、81、100。
13. 假设一张圆盘像唱机上的唱盘那样转动。这张盘一半是黑色，一半是白色
。假设你有数量不限的一些颜色传感器。要想确定圆盘转动的方向，你需要在它周
围摆多少个颜色传感器？它们应该被摆放在什么位置？
两个。可随意摆放，只要不同时放在圆的同一条直径上。根据变色顺序判断。
14. 假设时钟到了12点。注意时针和分针重叠在一起。在一天之中，时针和分
针共重叠多少次？你知道它们重叠时的具体时间吗？
23或22次(依据算不算24小时候的的12点整）。首先，将12小时划分成12个区间,[12, 1), [1,2)...[11, 12]。每个区间中都有一次相遇的时刻，其中在[12, 1)和[11, 12]相遇的时刻都是12点整。那么完成前半天12个小时就相遇了12次。在后12个小时中，由于起始的12点整已经被计算进入前12次中的一次，则后面只有11次相遇。所以总共23次。若不计算最后的那次12点整，则是22次（题目是一天之中，所以这个时候是第二天的开始）。
由于每次相遇到下一次相遇的时间是一定的，我们知道在12个小时内（包括12个小时) 相遇了12次, 又知道第一次和最后一次分别在这个时间段的起始和结束。那么可将这12个小时等分成11段，每一段的长度就是相遇的时间间隔。那么间隔 interval = 60*12 /11 = 720 / 11分钟。
知道间隔时间以后就可以从12点开始每次加上这个间隔时间算出每次相遇的时刻。
另一种方法是解方程。将时钟的一圈分成60个格子，设相遇时分针相对12点的时刻走了x个格子。我们知道分针每走一格，相当于时针走了1/12格。那么可根据指针重合条件列出方程。
假设我们要求[1, 2)区间内的相遇时刻，则有：
x / 12 = x - 5
类似的我们可以求出[2, 3), [3,4)...[11, 12]区间的相遇时刻([0, 1]和[11, 12]的相遇时刻相同)：
x / 12 = x - 10,
x / 12 = x - 15
...
x / 12 = x
15. 中间只隔一个数字的两个质数被称为质数对，比如17和19。证明质数对之
间的数字总能被6整除（假设这两个质数都大于6），并证明没有由三个质数组成
的质数对。
大于6的质数（prime number, 合数 composite number）都是奇数（只有2是唯一的偶质数）。所以质数对中间的数字一定是偶数，能被2整除（divisible）。由于在大于6的数中，任取三个连续的数字其中有且仅有一个数字能被3整除，而质数对的两个质数肯定不能被3整除（否则不是质数），则中间的那个数必定能被3整除。
一个数既能被2又能被3整除，则它能被6整除。
反证法（Reductio ad absurdum）：设x，x+2是一质数对，假设有连续三个质数组成的质数对，则x2+4或者x-2为质数。那么x-2，x和x+2，x+4是可能的两个质数对。则x-1或x+3应能被6整除。但是，由于x+1能被6整除，则x-1和x+3不可能被6整除。所以不存在三个质数组成的质数对。
16. 一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这 盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯。
同时开两盏，过一段时间关闭一盏。进门根据灯泡温度决定刚刚关掉的是哪一盏。
17. 假设你有8个球，其中一个略微重一些，但是找出这个球的惟一方法是将两个球放在天平上对比。最少要称多少次才能找出这个较重的球？
2次。
第一次分别取3个求放在天平两端，若不平横则重球在重的一端的三个球中。若不平衡，第二次任取两球放在天平两端，若不平衡则找到重球，若平横则剩下的一球为重球。
若第一次天平平衡。则重求在剩下的2个球中。第二次称量可直接找到重球。
18. 如果你有两个桶，一个装的是红色的颜料，另一个装的是蓝色的颜料。你从蓝色颜料桶里舀一杯，倒入红色颜料桶，再从红色颜料桶里舀一杯倒入蓝颜料桶。两个桶中红蓝颜料的比例哪个更高？通过算术的方式来证明这一点。
设两桶中红蓝颜料都是1。从红桶中舀去1/k。红桶中还有(k - 1)/k的红，蓝桶中有1的蓝和1/k的红。从蓝桶中舀去1/k。此1/k有(1/k) / (1+1/k) * 1 = 1/(k + 1)的蓝，和1/k - 1/k+1 = 1/(k*(k+1)的红。此时红桶中的红是 (k - 1)/k + 1/(k*(k+1) = k/(k + 1)。蓝桶中的蓝是1 - 1/(k + 1) = k/(k+1)。
比例相同。
递归求square root
设要求根的数为n, 定义f(x) = x^2 - n
应用Newton's Method估算 f(x) = 0 的正数解。首先猜测X[0] (X[0] > 0)为方程的解，之后根据recurrence relation: X[i] = X[i-1] - f(X[i-1]) / f''(X[i-1]) = (X[i-1] + n / X[i-1]) / 2 使X[i]不断逼近准确解。 当误差小于一定范围时，返回当前估算值。
double sqrtRecursive(double n, double guess)
{
if(abs(guess * guess - n) < 0.00001)
return guess;
else
return sqrtRecursive(n, (guess + n/guess)*0.5);
}
应用Newton's Method估算 f(x) = 0 的正数解。首先猜测X[0] (X[0] > 0)为方程的解，之后根据recurrence relation: X[i] = X[i-1] - f(X[i-1]) / f''(X[i-1]) = (X[i-1] + n / X[i-1]) / 2 使X[i]不断逼近准确解。 当误差小于一定范围时，返回当前估算值。
double sqrtRecursive(double n, double guess)
{
if(abs(guess * guess - n) < 0.00001)
return guess;
else
return sqrtRecursive(n, (guess + n/guess)*0.5);
}
2011年2月18日星期五
和为n连续正数序列
题目：输入一个正数n，输出所有和为n连续正数序列。不考虑一个数的序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
void CountinousSequenceSum_1(int n)
{
if(n < 3)
return;
int sum;
for(int i = 1; i < n/2 + 1; i++)
{
sum = i;
for(int j = i + 1; j < n/2 + 2; j++)
{
sum += j;
if(sum == n)
{
for(int k = i; k < j + 1; k++)
cout << k << " ";
cout << endl;
}
}
}
return;
}
否为N来得到这个序列。如果区间和大于n,small往前移动，如果小于 n,big往前移动，等于就输出
这个区间。时间复杂度是0(n)。
void CountinousSequenceSum_2(int n)
{
if(n < 3)
return;
int start = 1, end = 2;
int sum = start + end;
while(end < n/2 + 2)
{
if(sum == n)
{
for(int i = start; i < end + 1; i++)
cout << i << " ";
cout << endl;
end++;
sum += end;
}
else if(sum > n)
{
sum -= start;
start++;
}
else
{
sum += end + 1;
end++;
}
}
}
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
注意： 由于序列至少有两个元素且连续，所以序列起始元素最大不超过(int)(n/2), 结束元素最大不超过(int)(n/2) + 1, 因此无需遍历 1...n-1。
方法1.
使用枚举的方法，两个for循环可以搞定。时间复杂度O(n^2)。void CountinousSequenceSum_1(int n)
{
if(n < 3)
return;
int sum;
for(int i = 1; i < n/2 + 1; i++)
{
sum = i;
for(int j = i + 1; j < n/2 + 2; j++)
{
sum += j;
if(sum == n)
{
for(int k = i; k < j + 1; k++)
cout << k << " ";
cout << endl;
}
}
}
return;
}
方法2.
因为整数序列是有序的，可以设立两个游标small,big，通过判区间[small,big]的和是否为N来得到这个序列。如果区间和大于n,small往前移动，如果小于 n,big往前移动，等于就输出
这个区间。时间复杂度是0(n)。
void CountinousSequenceSum_2(int n)
{
if(n < 3)
return;
int start = 1, end = 2;
int sum = start + end;
while(end < n/2 + 2)
{
if(sum == n)
{
for(int i = start; i < end + 1; i++)
cout << i << " ";
cout << endl;
end++;
sum += end;
}
else if(sum > n)
{
sum -= start;
start++;
}
else
{
sum += end + 1;
end++;
}
}
}
递归法求字符串的全排列 (permutation)
每次递归调用，解决一个当前元素数量为n-k ( k = 0...n-1)的全排列，为解决当前当前排列, 又需要递归解决n-k个元素数量为n-k-1的全排列
举例：字符串abc, n = 3, []中的元素为需要计算排列的元素集，[]外的元素为已经确定排列顺序的元素
[abc]
/ | \
a[bc] b[ac] c[ba]
/ | / \ | \
ab[c] ac[b] ba[c] bc[a] cb[a] ca[b]
| | | | | |
abc acb bac bca cba cab
第一层：k = 0，1个全排列需解决，为此需解决3个元素数为2的全排列
第二层：k = 1，3个全排列需解决，解决每个全排列需要解决2个元素数为1的全排列
第三层：k = 2，6个全排列需解决，解决每个全排列需要解决2个元素数为0的全排列（说明当前层已解得所需的所有全排列）
第四层：k = 3， k等于n，到达递归底层，打印当前排列
static void RecursivePermute(char* str,int k)//递归函数
举例：字符串abc, n = 3, []中的元素为需要计算排列的元素集，[]外的元素为已经确定排列顺序的元素
[abc]
/ | \
a[bc] b[ac] c[ba]
/ | / \ | \
ab[c] ac[b] ba[c] bc[a] cb[a] ca[b]
| | | | | |
abc acb bac bca cba cab
第一层：k = 0，1个全排列需解决，为此需解决3个元素数为2的全排列
第二层：k = 1，3个全排列需解决，解决每个全排列需要解决2个元素数为1的全排列
第三层：k = 2，6个全排列需解决，解决每个全排列需要解决2个元素数为0的全排列（说明当前层已解得所需的所有全排列）
第四层：k = 3， k等于n，到达递归底层，打印当前排列
static void RecursivePermute(char* str,int k)//递归函数
{
int i;
if(k==strlen(str))
printf("%s\n",str);
else
{
for(i=k;i<strlen(str);i++)
{
ExchangeCharacters(str,k,i);
RecursivePermute(str,k+1);
ExchangeCharacters(str,k,i);
}
}
}
static void ExchangeCharacters(char* str, int p1,int p2)
{
char tmp;
tmp=str[p1];
str[p1]=str[p2];
str[p2]=tmp;
}
2011年2月16日星期三
最长公共子序列 (LCS = Longest Common Subsequence) 和最长公共子串 (LCS = Longest Common Substring)
两个序列a,b, L[i][j]为以a[i]和b[j]结尾的最长公共子序列的长度。a长度为m, b长度为n
Longest Common Subsequence (子序列无需连续）
Initial condition:
L[0][j] = (a[0] == b[j]) ? 1 : 0 j = 0...n
L[i][0] = (a[i] == b[0]) ? 1 : 0 i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j]) ? L[i-1][j-1] + 1 : max(L[i][j-1], L[i-1][j]) i = 1...m, j = 1...n
最后L[m][n]即为结果
Longest Common Substring（子串需要连续）
Initial condition:
a[0][j] = (a[0] == b[j]) ? 1 : 0 j = 0...n
a[i][0] = (a[i] == b[0]) ? 1 : 0 i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j]) ? L[i-1][j-1] + 1 : 0 i = 1...m, j = 1...n结果为计算过程中最大的L[i][j] (用一个max变量跟踪）
Longest Common Subsequence (子序列无需连续）
Initial condition:
L[0][j] = (a[0] == b[j]) ? 1 : 0 j = 0...n
L[i][0] = (a[i] == b[0]) ? 1 : 0 i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j]) ? L[i-1][j-1] + 1 : max(L[i][j-1], L[i-1][j]) i = 1...m, j = 1...n
最后L[m][n]即为结果
Longest Common Substring（子串需要连续）
Initial condition:
a[0][j] = (a[0] == b[j]) ? 1 : 0 j = 0...n
a[i][0] = (a[i] == b[0]) ? 1 : 0 i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j]) ? L[i-1][j-1] + 1 : 0 i = 1...m, j = 1...n结果为计算过程中最大的L[i][j] (用一个max变量跟踪）
最长单调递增子序列（LIS）
最长单调递增子 序列，就是在一个数列中最长的按单调递增的顺序排列的序列，该序列在原序列中可以不连续。
解法1:
设b[i]为截止到第i个数且以第i个数为结尾的最长单调递增子序列的长度，a为所给序列，则有：
Initial condittion:
b[0] = 1
Recurrence relation:
b[0] = 1
Recurrence relation:
b[ i ] = max( a[i] > a[j] ? b[j] + 1 : 1) j = 0...i-1
//return value: length of LIS
//aMax: LIS array
//a: original array
//b: b[i] stores the length of the local LIS with the last member a[i]
//p: p[i] stores the previous index of member of the local LIS with the last member a[i]
int LIS(int *a, int *b, int *p, int *aMax, int n)
{
int max = 0;
int maxIndex;
for(int i = 0; i < n; i++)
{
b[i] = 1;
for(int j = 0; j < i; j++)
{
if(a[i] > a[j] && b[i] < b[j] + 1)
{
b[i] = b[j] + 1;
p[i] = j;
}
}
if(b[i] > max)
{
max = b[i];
maxIndex = i;
}
}
for(int i = max -1; i > -1; i--)
{
aMax[i] = a[maxIndex];
maxIndex = p[maxIndex];
}
return max;
}
复杂度o(n2)
解法2:
解法2:
将原序列按升序排序，再对原序列和排序后的序列计算LCS(Longest Common Subsequence）的长度。
排序复杂度o(nlogn), LCS复杂度o(n2), 总复杂度o(n2)
最长连续数字序列， 计数并输出
int longestNumString(char *string, char *output)
{
int count = 0;
int max = 0;
char *start;
char *startMax;
while(true)
{
if(*string >= '0' && *string <= '9')
start = string;
while(*string >= '0' && *string <= '9' && *string)
{
string++;
count++;
}
if(count > max)
{
max = count;
startMax = start;
}
count = 0;
if(*string)
string++;
else
break;
}
for(int i = 0; i < max; i++)
{
*output = *startMax;
startMax++;
output++;
}
return max;
}
{
int count = 0;
int max = 0;
char *start;
char *startMax;
while(true)
{
if(*string >= '0' && *string <= '9')
start = string;
while(*string >= '0' && *string <= '9' && *string)
{
string++;
count++;
}
if(count > max)
{
max = count;
startMax = start;
}
count = 0;
if(*string)
string++;
else
break;
}
for(int i = 0; i < max; i++)
{
*output = *startMax;
startMax++;
output++;
}
return max;
}
2011年2月6日星期日
<转>Count the number of bits that are on in an unsigned integer（计算一个无符整数中1Bit的个数）
计算一个无符号整数中有多少的Bit为1
原创整理，转载请注明出处。
这是一个经常遇到的经典问题，这里分两个部分讲解和总结，首先对讲解现有的算法，然后再讲解一些改进算法。
1．循环法（Iterated Count）
循环的次数是常数（n的位数）。在1比较稀疏的时候效率低，可用方法2改进。
2．Bit1稀疏 Sparse Ones
理解这个算法的核心，只需理解2个操作：
1> 当一个数被减1时，他最右边的那个值为1的Bit将变为0，同时其右边的所有的Bit都会变成1。
2>“&=”，位与并赋值操作。去掉已经被计数过的1，并将改值重新设置给n.
这个算法循环的次数是bit位为一的个数。也就说有几个Bit为1，循环几次。对Bit为1比较稀疏的数来说，性能很好。如：0x1000 0000, 循环一次就可以。
3．密集1的算法 Dense Ones
原创整理，转载请注明出处。
这是一个经常遇到的经典问题，这里分两个部分讲解和总结，首先对讲解现有的算法，然后再讲解一些改进算法。
1．循环法（Iterated Count）
int bitcount (unsigned int n) {int count=0; while (n) { count += n & 0x1u ; n >>= 1 ; }return count ;}最容易理解和想到的方法。对每一位依次判断是否为1，如果是就在count上加1。循环的次数是常数（n的位数）。在1比较稀疏的时候效率低，可用方法2改进。
2．Bit1稀疏 Sparse Ones
int bitcount (unsigned int n) {int count=0 ; while (n) { count++ ; n &= (n - 1) ; } return count ;}理解这个算法的核心，只需理解2个操作：
1> 当一个数被减1时，他最右边的那个值为1的Bit将变为0，同时其右边的所有的Bit都会变成1。
2>“&=”，位与并赋值操作。去掉已经被计数过的1，并将改值重新设置给n.
这个算法循环的次数是bit位为一的个数。也就说有几个Bit为1，循环几次。对Bit为1比较稀疏的数来说，性能很好。如：0x1000 0000, 循环一次就可以。
3．密集1的算法 Dense Ones
int bitcount (unsigned int n)
{
int count = 8 * sizeof(int) ;
n ^= (unsigned int) -1 ;
while (n)
{
count-- ;
n &= (n - 1) ;
}
return count ;
}
4．8bit静态表查找法 Precompute_8bit
static int bits_in_char [256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
6, 7, 6, 7, 7, 8
};
int bitcount (unsigned int n) { int count = 8 * sizeof(int) ; n ^= (unsigned int) -1 ; while (n) { count-- ; n &= (n - 1) ; } return count ; }
使用静态数组表，列出所有8bit(256个)无符号数含有Bit1的个数。将32Bit 的n分4部分，直接在表中找到对应的Bit1的个数，然后求和。
这是最快的方法了。缺点是需要比较大的内存。
reverse bits
翻转一个char的8个bits
char bitReverse(char a)
{
char b = 0;
for(int i = 0; i < 8; i++)
{
if(a & 1)
b = b | (1 << (7 - i));
a = a >> 1;
}
return b;
}
char bitReverse(char a)
{
char b = 0;
for(int i = 0; i < 8; i++)
{
if(a & 1)
b = b | (1 << (7 - i));
a = a >> 1;
}
return b;
}
<转>Find the Maximum of 2 numbers without using any if-else or any other comparison operator
Suppose 2 numbers are A and B .
Perform the operation A-B and extract the MSB .let it be k. Now if k =1 then A>B else B>A (2's complement)..
return (1-k)*A+k*B. This will alyways return the maximum of A&B
int a,b=0;
a = 7;
b = 9;
int diff = (unsigned int)(a-b) >> 31;
printf("\nDiff : %d\n",diff);
int sum = (1-diff)*a + (diff*b);
printf("\n Max of %d and %d is : %d\n",a,b,sum);
Perform the operation A-B and extract the MSB .let it be k. Now if k =1 then A>B else B>A (2's complement)..
return (1-k)*A+k*B. This will alyways return the maximum of A&B
int a,b=0;
a = 7;
b = 9;
int diff = (unsigned int)(a-b) >> 31;
printf("\nDiff : %d\n",diff);
int sum = (1-diff)*a + (diff*b);
printf("\n Max of %d and %d is : %d\n",a,b,sum);
2011年2月5日星期六
<转>atoi和itoa的实现
//atoi的实现
#include<iostream>
using namespace std;
int atio1(char *s)
{
int sign=1,num=0;
if(*s=='-')
sign=-1;
s++;
while((*s)!='\0')
{
num=num*10+(*s-'0');
s++;
}
return num*sign;
}
//itoa的实现
char *itoa(int num, char *str, int radix)
{
char* ptr = str;
int i;
int j;
while (num)
{
*ptr++ = string[num % radix];
num /= radix;
if (num < radix)
{
*ptr++ = string[num];
*ptr = '\0';
break;
}
}
j = ptr - str - 1;
for (i = 0; i < (ptr - str) / 2; i++)
{
int temp = str[i];
str[i] = str[j];
str[j--] = temp;
}
return str;
}
{
char* ptr = str;
int i;
int j;
while (num)
{
*ptr++ = string[num % radix];
num /= radix;
if (num < radix)
{
*ptr++ = string[num];
*ptr = '\0';
break;
}
}
j = ptr - str - 1;
for (i = 0; i < (ptr - str) / 2; i++)
{
int temp = str[i];
str[i] = str[j];
str[j--] = temp;
}
return str;
}
2011年2月4日星期五
<转>aligned malloc 实现
I checked it it works !!
#include <stdio.h>
#include <stdlib.h>
/*************************************************
Name :- aligned_malloc
Arguments:- number of bytes & Alignment Boundry
Return :- NULL on error
valid pointer on success
Working :- It will allocate memory with starting address
multiple of alignment passed and returns pointer
to it on success.
Ex.
aligned_malloc(50,128);
This will allocate 50 bytes of memory with
starting address multiple of 128.
*************************************************/
void *aligned_malloc(size_t bytes, size_t alignment)
{
void *p1 ,*p2; // basic pointer needed for computation.
if((p1 =(void *) malloc(bytes + alignment + sizeof(size_t)))==NULL)
return NULL;
size_t addr=(size_t)p1+alignment+sizeof(size_t);
p2=(void *)(addr - (addr%alignment));
*((size_t *)p2-1)=(size_t)p1;
return p2;
}
/************************************************
Name :- aligned_free
Arguments :- pointer to be freed
Returns :- Nothing
*************************************************/
void aligned_free(void *p )
{
free((void *)(*((size_t *) p-1)));
}
#include <stdio.h>
#include <stdlib.h>
/*************************************************
Name :- aligned_malloc
Arguments:- number of bytes & Alignment Boundry
Return :- NULL on error
valid pointer on success
Working :- It will allocate memory with starting address
multiple of alignment passed and returns pointer
to it on success.
Ex.
aligned_malloc(50,128);
This will allocate 50 bytes of memory with
starting address multiple of 128.
*************************************************/
void *aligned_malloc(size_t bytes, size_t alignment)
{
void *p1 ,*p2; // basic pointer needed for computation.
if((p1 =(void *) malloc(bytes + alignment + sizeof(size_t)))==NULL)
return NULL;
size_t addr=(size_t)p1+alignment+sizeof(size_t);
p2=(void *)(addr - (addr%alignment));
*((size_t *)p2-1)=(size_t)p1;
return p2;
}
/************************************************
Name :- aligned_free
Arguments :- pointer to be freed
Returns :- Nothing
*************************************************/
void aligned_free(void *p )
{
free((void *)(*((size_t *) p-1)));
}
memalign函数可以直接实现这个功能，限制是alignment必须是2的power
2011年1月25日星期二
<转>不用临时变量交换两个数的值
当要交换两个数的值时，通常的做法是定义一个临时变量，然后再进行交换。那么能不能不用临时变量而交换两个数的值呢？可以的！C语言提供的异或运算就可以实现这样的操作。
异或运算符^也称XOR运算符，它的规则是若参加运算的两个二进位同号，则结果为0（假）；异号为1（真）。即0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0。
例：
#include
int main(int argc, char *argv[])
{
int a = 2, b = 6;
a = a ^ b;
b = b ^ a;
a = a ^ b;
printf("a = %d b = %d\n", a, b);
return 0;
}
结果如下：
a = 6 b = 2
分析：
前两个赋值语句：“a = a ^ b；”和“b = b ^ a；”相当于b = b ^ (a ^ b)，而b ^ a ^ b等于a ^ b ^ b。b ^ b的结果为0，因为同一个数与相向相^，结果必为0。因此b的值等于a ^ 0，即a，其值为2。
再执行第三个赋值语句：“a = a ^ b”。由于a的值等于(a ^ b)，b的值等于(b ^ a ^ b)，因此，相当于a = a ^ b ^ b ^ a ^ b，即a的值等于a ^ a ^ b ^ b ^ b，等于b。
2007.06.02
今天又发现另外两种方法，特补上。
方法一
void swap(int *p, int *q)
{
*p = *p + *q;
*q = *p - *q;
*p = *p - *q;
}
方法二
void swap(int *p, int *q)
{
*p = *p + *q - (*q = *p);
}
原理为算术运算符的结合顺序为自左至右。
异或运算符^也称XOR运算符，它的规则是若参加运算的两个二进位同号，则结果为0（假）；异号为1（真）。即0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0。
例：
#include
int main(int argc, char *argv[])
{
int a = 2, b = 6;
a = a ^ b;
b = b ^ a;
a = a ^ b;
printf("a = %d b = %d\n", a, b);
return 0;
}
结果如下：
a = 6 b = 2
分析：
前两个赋值语句：“a = a ^ b；”和“b = b ^ a；”相当于b = b ^ (a ^ b)，而b ^ a ^ b等于a ^ b ^ b。b ^ b的结果为0，因为同一个数与相向相^，结果必为0。因此b的值等于a ^ 0，即a，其值为2。
再执行第三个赋值语句：“a = a ^ b”。由于a的值等于(a ^ b)，b的值等于(b ^ a ^ b)，因此，相当于a = a ^ b ^ b ^ a ^ b，即a的值等于a ^ a ^ b ^ b ^ b，等于b。
2007.06.02
今天又发现另外两种方法，特补上。
方法一
void swap(int *p, int *q)
{
*p = *p + *q;
*q = *p - *q;
*p = *p - *q;
}
方法二
void swap(int *p, int *q)
{
*p = *p + *q - (*q = *p);
}
原理为算术运算符的结合顺序为自左至右。
订阅：
博文 (Atom)
1) let the number be A = 10101111
2) A1 = A & 10101010 = 10101010
3) A2 = A & 01010101 = 00000101
4) A1 = A1 >> 1 = 01010101
5) A2 = A2 << 1 = 00001010
6) Answer = A1 | A2 = 01011111
so u require 5 instructions