第6题
------------------------------------
给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下:
【0,1,2,3,4,5,6,7,8,9】
举一个例子,
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次,1在下排出现了2次,
2在下排出现了1次,3在下排出现了0次....
以此类推..
解题思路:关键是理解“要求下排每个数都是先前上排那十个数在下排出现的次数”。
做以下分析:设总共有n个数,上排a[0...n-1],下排b[0...n-1],。
1)下排n个数的累加和为n,即b[0]+b[1]+...+b[n-1] = n
2)ai*bi的累加和也为n,即a[0]*b[0]+a[1]*b[1]+...+a[n-1]*b[n-1] = n
3)对于b中任意一个元素b[j], 都存在i,a[i] = b[j].
4)对于b中任意一个元素b[j],都有b[j] >= 0
5)如果a中存在负数。其在b中出现的次数一定为0. 如果a中数值大于n,则其出现次数也为0.
6)a中至少有两个非0数值在b中出现的次数非0
a:由1)n > n*b[i],其中b[i]为最小值,则a b中一定均有数值0,否则无解。设a[0] = 0,b[0]为a[0]在b中出现次数。
b:由于b中一定存在0,则0的出现次数一定大于0,因此b[0]>0 且b[0] < n,b[1...n-1]中至少一个值为0. 非0元素出现的次数一共是n-b[0].
c:有2)和6)对任意a[i],a[i]*b[i] < n,即b[i] < n/a[i],对所有a[i]>=n/2的元素中,在b中出现的次数必须最多只有1个出现次数不为0,且为1.其余出现次数均为0,即[1, n/2)范围内最多只有n/2-1个元素,故0出现的次数必不小于n/2, [n/2,n)范围内的元素必有一个出现次数为1。因此a数列中也必须有1,否则无解。
d:有c得在数值范围为(0,n/2)中(假设有x这样的数)出现的次数和s为n - b[0]或n-b[0]-1。其中1出现的次数至少为1(由c得)。又如果1出现的次数为1,则1出现的次数已经为2,故1出现的次数必大于1.设为x,则x出现的次数至少为1,而x>1,如果x出现的次数大于1,那么必须要有其他数出现的次数为x,这样无法收敛。故x出现的次数只能为1,1出现的次数只能为2.
另外:如果上排数列中无0,则下排数列全是0,是其唯一解。
结论:
1)如果上排数列中有0,此时如果上排数列中无0,1,2,n-4这四个数,则下排数列无解;否则下排数列中0出现的次数为n-4;1出现的次数为2;2出现的次数为1;n-4出现的次数为1;其余为0。
2)如果上排数列中无0,则下排数列全0,是其唯一解。
/* 第7题 ------------------------------------ 微软亚院之编程判断俩个链表是否相交 给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交。 为了简化问题,我们假设俩个链表均不带环。 问题扩展: 1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列? */ //这一题,自己也和不少人讨论过了, //更详细的,请看这里: //My sina Blog: //http://blog.sina.com.cn/s/blog_5e3ab00c0100le4s.html /*1.首先假定链表不带环 那么,我们只要判断俩个链表的尾指针是否相等。 相等,则链表相交;否则,链表不相交。 2.如果链表带环, 那判断一链表上俩指针相遇的那个节点,在不在另一条链表上。 如果在,则相交,如果不在,则不相交。 所以,事实上,这个问题就转化成了: 1.先判断带不带环 2.如果都不带环,就判断尾节点是否相等 3.如果都带环,判断一链表上俩指针相遇的那个节点,在不在另一条链表上。 如果在,则相交,如果不在,则不相交。 */ //用两个指针,一个指针步长为1,一个指针步长为2,判断链表是否有环 bool check(const node* head) { if(head==NULL) return false; node *low=head, *fast=head->next; while(fast!=NULL && fast->next!=NULL) { low=low->next; fast=fast->next->next; if(low==fast) return true; } return false; } //如果链表可能有环,则如何判断两个链表是否相交 //思路:链表1 步长为1,链表2步长为2 ,如果有环且相交则肯定相遇,否则不相交 list1 head: p1 list2 head: p2 while( p1 != p2 && p1 != NULL && p2 != NULL ) [b]//但当链表有环但不相交时,此处是死循环。![/b] { p1 = p1->next; if ( p2->next ) p2 = p2->next->next; else p2 = p2->next; } if ( p1 == p2 && p1 && p2) //相交 else //不相交 [color=#FF0000][b]所以,判断带环的链表,相不相交,只能这样[/b]:[/color] 如果都带环,判断一链表上俩指针相遇的那个节点,在不在另一条链表上。 如果在,则相交,如果不在,则不相交。(未写代码实现,见谅。:).. ------------------
/*
第9题
-----------------------------------
判断整数序列是不是二元查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
……
[/Quote]
8
/ \
6 10
/ \ / \
5 7 9 11
后续遍历:
5、7、6、9、11、10、8
第9题:
其实,就是一个后序遍历二叉树的算法。
关键点:
1.
//确定根结点
int root = squence[length - 1];
2.
// the nodes in left sub-tree are less than the root
int i = 0;
for(; i < length - 1; ++ i)
{
if(squence[i] > root)
break;
}
// the nodes in the right sub-tree are greater than the root
int j = i;
for(; j < length - 1; ++ j)
{
if(squence[j] < root)
return false;
}
3.
递归遍历,左右子树。
//单词翻转 /*第10题 #include<iostream> #include<string> using namespace std; class ReverseWords{ public: ReverseWords(string* wo):words(wo){} void reverse_() { int length=words->size(); int begin=-1,end=-1; for(int i=0;i<length;++i){ if(begin==-1&&words->at(i)==' ') continue; if(begin==-1) { begin=i; continue; } if(words->at(i)==' ') end=i-1; else if(i==length-1) end=i; else continue; reverse__(begin,end); //1.字母翻转 begin=-1,end=-1; } reverse__(0,length-1); //2.单词翻转 } private: void reverse__(int begin,int end) // { while(begin<end) { char t=words->at(begin); words->at(begin)=words->at(end); words->at(end)=t; ++begin; --end; } } string* words; }; int main(){ string s="I am a student."; ReverseWords r(&s); r.reverse_(); cout<<s<<endl; return 0; } /*运行结果: student. a am I Press any key to continue */