<pre name="code" class="cpp">/*
第 8 题（算法）
1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，
这两个房间是 分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一
块。
如果你只能将金条切割两次，你怎样分给这些工人?
3.
★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。
★用一种算法整理一个数组。你为什么选择这种方法?
★用一种算法使通用字符串相匹配。
★颠倒一个字符串。优化速度。优化空间。
★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
★找到一个子字符串。优化速度。优化空间。
★比较两个字符串，用 O(n)时间和恒量空间。
★假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有
的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现两次外，其他所有数字只出
现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运
算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?
★不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。
*/
/*
1.先进有开关的房子,先开A开关,过一段时间关上,再开B开关,
然后进入有灯的房子,亮着的灯由B开关控制,用手摸熄灭的两盏灯,
热的受A开关控制,剩下的受C开关控制.
2.
1+2+4;
分别是整根金条的1/7、2/7 4/7
第一天：给1/7的， 第二天：给2/7的，收回1/7的 第三天，给1/7的
第四天：给4/7的，收回1/7和2/7的 第五天：给1/7的 第六天：给2/7的，收回1/7的
3.
★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
node * reverse(node *head)
{
if(head=NULL) return head;
if(head->next==NULL) return head;
node *ph=reverse(head->next);
head->next->next=head;
head->next=NULL;
return ph;
}
node * reverseNonrecurse(node *head)
{
if(head==NULL) return head;
node *p=head,*previous=NULL,*next=NULL;
while(p->next!=NULL)
{
next=p->next;//保存下一个
p->next=previous;//p下一个为他前面的
previous=p;
p=next;
}
p->next=previous;
return p;
}
★用一种算法使通用字符串相匹配。
int match(char *str,char *ptn)
{
if(*ptn=='\0') return 1;//要匹配的完毕了
if(*ptn=='*'){
do{
if(match(str++,ptn+1)) return 1;
}while(*str!='\0');
return 0;
}
if(*str=='\0') return 0;
if(*str==*ptn||*ptn=='?'){
return match(str+1,ptn+1);
}
return 0;
}
★颠倒一个字符串。优化速度。优化空间。
void reverse(char *str)
{
reverFixlen(str,strlen(str));
}
void reverFixlen(char *str,int len)
{
char *p=str+len-1;//最后位
char ch;
while(str<p)
{
ch=*str;
*str=*p;
*p=ch;
str++;p--;
}
}
★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
//翻转两次，第一次将整个字符串翻转，第二次将每个单词翻转
//I am a student”反转成为“tneduts a ma I==>"student a am I"
void reverWordSen(char *sen)
{
int len=strlen(sen);
reverFixlen(sen,len);//整个翻转
char *p=sen,*str;
while (*p!='\0')
{
while(*p==' '&&*p!='\0') p++;
str=p;//起始位置
while(*p!=' '&&*p!='\0') p++;
reverFixlen(str,p-str);
}
}
★比较两个字符串，用 O(n)时间和恒量空间。
int strcmp(char *s1,char *s2)
{
while(*s1!='\0'&&*s2!='\0'&&*s1==*s2)
{
s1++;s2++;
}
if(*s1=='\0'&&*s2=='\0') return 0;
if(*s1=='\0') return -1;
if(*s2=='\0') return 1;
return *s1-*s2;
}
★假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有
的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现两次外，其他所有数字只出
现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运
算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?
加起来然后减去1-1000的和；
★不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。
n<<3;
(n<<3)-n;
*/