/*
第22题：
有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，
再分别在A、B、C三人额头上贴任意两张牌，
A、B、C三人都可以看见其余两人额头上的牌，
看完后让他们猜自己额头上是什么颜色的牌，
A说不知道，B说不知道，C说不知道，然后A说知道了。
请教如何推理，A是怎么知道的。如果用程序，又怎么实现呢？
*/
推理如下：
因为第一次三者都说不知道，则两两相加不可能出现四红或四蓝，则A，B，C中必须至少有一个是红蓝。
A看B和C，如果B和C中是两红和两蓝，则A第二次可以确定自己是红蓝。同理B和C也是，则这种方式成立。
除此之外，剩下二种组合方式：三个人都是红蓝；两个人红蓝，一个人是两红或两蓝。
三个人都是红蓝,三个人都是红蓝，A就不说了，可以判断。
如果A，B，C中有一个是两红和两蓝，那么另两个就可以第二次判断出自已是红蓝。而此人只能判断出自己是两红或者是两蓝，那么A不能判断自己，所以A是红蓝，B和C是中有一个是红蓝，一个是两红或两蓝.
所以A是红蓝，B和C不确定。
/* 第23题： 用最简单， 最快速的方法计算出下面这个圆形是否和正方形相交。" 3D坐标系 原点(0.0,0.0,0.0) 圆形: 半径r = 3.0 圆心o = (*.*, 0.0, *.*) 正方形: 4个角坐标; 1:(*.*, 0.0, *.*) 2:(*.*, 0.0, *.*) 3:(*.*, 0.0, *.*) 4:(*.*, 0.0, *.*) */
计算正方形四个顶点和圆的关系，分3中情况：
1.圆内圆外都有顶点，相交
2.4个都在圆内，不相交
3.4个都在圆外，计算正方形每条边的线段与圆心到每条边的垂线交点（交点必须在边的线段上），如果有一个交点在圆内，相交。
否则，不相交。
/*
第24题：
链表操作，
（1）单链表就地逆置，
*/
//定义链表结构体
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
/*------------------------------------------
写代码之前，先好好分析下。
->m->n->
<-m n->
结点的m_pNext指针都指向前面一个结点。
我们遍历到结点m，需要在调整m的m_pNext之前要把n保存下来。
接下来试着找到反转后链表的头结点即原始链表的尾位结点，
就是m_pNext为空指针的结点。
------------------------------------------*/
ListNode* ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode != NULL) //pNode<=>m
{
ListNode* pNext = pNode->m_pNext; //n保存在pNext下
//如果pNext指为空，则当前结点pNode设为头。
if(pNext == NULL)
pReversedHead = pNode;
// reverse the linkage between nodes
pNode->m_pNext = pPrev;
// move forward on the the list
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
26.左旋转字符串
题目：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。
分析：如果不考虑时间和空间复杂度的限制，
最简单的方法莫过于把这道题看成是把字符串分成前后两部分，
通过旋转操作把这两个部分交换位置。
于是我们可以新开辟一块长度为n+1的辅助空间，
把原字符串后半部分拷贝到新空间的前半部分，在把原字符串的前半部分拷贝到新空间的后半部分。
不难看出，这种思路的时间复杂度是O(n)，需要的辅助空间也是O(n)。
把字符串看成有两段组成的，记位XY。左旋转相当于要把字符串XY变成YX。
我们先在字符串上定义一种翻转的操作，就是翻转字符串中字符的先后顺序。把X翻转后记为XT。显然有
(XT)T=X。
我们首先对X和Y两段分别进行翻转操作，这样就能得到XTYT。
接着再对XTYT进行翻转操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我们期待的结果。
分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段，
第一段为前面m个字符，其余的字符分到第二段。
再定义一个翻转字符串的函数，按照前面的步骤翻转三次就行了。
时间复杂度和空间复杂度都合乎要求。
#include "string.h"
// Move the first n chars in a string to its end
char* LeftRotateString(char* pStr, unsigned int n)
{
if(pStr != NULL)
{
int nLength = static_cast<int>(strlen(pStr));
if(nLength > 0 || n == 0 || n > nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// reverse the first part of the string
ReverseString(pFirstStart, pFirstEnd);
// reverse the second part of the strint
ReverseString(pSecondStart, pSecondEnd);
// reverse the whole string
ReverseString(pFirstStart, pSecondEnd);
}
}
return pStr;
}
// Reverse the string between pStart and pEnd
void ReverseString(char* pStart, char* pEnd)
{
if(pStart == NULL || pEnd == NULL)
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd --;
}
}
}
27.跳台阶问题
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。
首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。
如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。
现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。
当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，
此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；
另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。
因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。
我们把上面的分析用一个公式总结如下：
/ 1 n=1
f(n)= 2 n=2
/ f(n-1)+(f-2) n>2
分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。
int jump_sum(int n) //递归版本
{
assert(n>0);
if (n == 1 || n == 2) return n;
return jump_sum(n-1)+jump_sum(n-2);
}
int jump_sum(int n) //迭代版本
{
assert(n>0);
if (n == 1 || n == 2) return n;
int an, an_1=2, an_2=1;
for (; n>=3; n--)
{
an = an_2 + an_1;
an_2 = an_1;
an_1 = an;
}
return an;
}