1.两棵二叉树T1和T2,T1的节点数是百万量级,T2的节点数一千以内,请给出判断T2是否T1子树的可行算法。
分析:首先想到的是递归,但是T1的数量级太大,递归会导致栈溢出,于是以非递归实现。
bool IsSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot1 == NULL || pRoot2 == NULL) {
return false;
}
stack<BinaryTreeNode*> stk;
stk.push(pRoot1);
while (!stk.empty()) {
BinaryTreeNode *tmp = stk.top();
stk.pop();
if (tmp->m_nValue == pRoot2->m_nValue) {
stack<BinaryTreeNode*> first;
BinaryTreeNode *f;
stack<BinaryTreeNode*> second;
BinaryTreeNode *s;
first.push(tmp);
second.push(pRoot2);
bool find = true;
while (!first.empty()) {
f = first.top();
first.pop();
s = second.top();
second.pop();
if (f->m_nValue != s->m_nValue) {
find = false;
break;
}
if (s->m_pLeft != NULL) {
if (f->m_pLeft == NULL) {
find = false;
break;
} else {
first.push(f->m_pLeft);
second.push(s->m_pLeft);
}
}
if (s->m_pRight != NULL) {
if (f->m_pRight == NULL) {
find = false;
break;
} else {
first.push(f->m_pRight);
second.push(s->m_pRight);
}
}
}
if (find == true && first.empty()) {
return true;
}
}
if (tmp->m_pLeft != NULL) {
stk.push(tmp->m_pLeft);
}
if (tmp->m_pRight != NULL) {
stk.push(tmp->m_pRight);
}
}
return false;
}
2.
从1到500的500个数,第一次删除奇数位,第二次删除剩下来的奇数位,以此类推,最后剩下的唯一一位数是:
A.500 B.256C.250D.128
分析:
比如:1,2,删除奇数位,那剩下的是2,
1,2,3,删除奇数位,剩下的是2,
1,2,3,4,剩下的是4,
1,2,3,4,5,6,7,剩下的是4,
1,2,3,4,5,6,7,8和1,2,3,4,5,6,7,8,9,10,11,12,13,14,15剩下的是8,
这里有什么规律:就是当1~n,2^i<n<2^(i+1)时候,这样删除剩下的是2^i。
2^8<500<2^9,所以剩下的就是2^8=256。
转载请注明原创链接:http://blog.csdn.net/wujunokay/article/details/12233223
分享到:
相关推荐
阿里巴巴2014笔试题(客户端)
阿里巴巴上机笔试题,想进阿里的同学可以看看
阿里巴巴年校园招聘笔试题(b2b-技术部-工程师)java,算法,C++,测试.doc 阿里巴巴校园招聘Oracle_DBA笔试题及参考答案.doc 阿里巴巴校园招聘前端在线笔试.doc 阿里巴巴校园招聘测试笔试题总结.doc 阿里巴巴校园招聘...
整理了一下阿里巴巴往届笔试面试题,希望对大家有帮助: 来源:阿里巴巴笔试面试圈>> 1、史上最全Java面试266题:算法+缓存+TCP+JVM+搜索+分布式+数据库 2、2018阿里软件工程师笔试题 3、2018秋招阿里巴巴java...
阿里巴巴2014笔试题(客户端) c++各个知识点的例子 Unity 3D手机游戏开发
阿里巴巴2014校园招聘笔试试题-软件研发工程师+答案.doc
阿里巴巴校招前端笔试题 校招前端笔试题.pages
阿里巴巴2014校招笔试题--测试开发(与研发题目相似)
阿里巴巴2014校园招聘笔试题-全国卷.pdf
阿里巴巴公司DBA笔试题 含答案,代表了国内DBA笔试题的经典,其实同志们,DBA笔试就那么些题,哈哈
文档是2014年阿里巴巴实习生笔试题。各个岗位的基础题是一样的,只是附加题不一样
找工作的同学有福啦,阿里巴巴2014最新笔试原题,免费提供给大家,一定要看,方能百战不殆!
求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘...
《技术之瞳——阿里巴巴技术笔试心得》由阿里巴巴集团校园招聘笔试项目组所著,收集了阿里历年校招中的精华笔试题,涉 及多个领域。《技术之瞳——阿里巴巴技术笔试心得》中内容大量结合了阿里巴巴的实际工作场景,...
1.一次内存访问、SSD硬盘访问和SATA硬盘随机访问的时间分别的是A、几微秒,几毫秒,几十毫秒B、几微秒,几十微秒,几十毫秒C、几十纳秒,几叶微秒,几叶毫秒D、几l-纳秒,几十微秒,十几毫秒 2....
阿里巴巴最新算法工程师笔试题.pdf
去哪儿网2014笔试算法题汇总:1.写一个函数,转换相对路径为绝对路径,比如:/home/abs/../temp/new/../,输出路径为:/home/temp。 参考代码: 1. //写一个函数,转换相对路径为绝对路径,比如:/home/abs/../temp/...
好难的题啊,忘大家好好准备,别再打酱油了
新鲜出炉的阿里巴巴笔试题,今年人工智能两个答题全部都是NLP
阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合阿里巴巴2011年笔试试题集合