程序算法总结没有密码版本.docx
- 文档编号:4633100
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:56
- 大小:41.93KB
程序算法总结没有密码版本.docx
《程序算法总结没有密码版本.docx》由会员分享,可在线阅读,更多相关《程序算法总结没有密码版本.docx(56页珍藏版)》请在冰点文库上搜索。
程序算法总结没有密码版本
注:
所有程序以及算法均为本人从网络,书籍中收集,程序均为手写调试完成,供RD001内部使用,参考,谢绝其他一切形式的扩散,共享。
应聘的环节主要包括面试和笔试,其中不免会涉及到很多算法和数据结构的问题,在这里将其先分为两大类,笔试的时候算法题为非即时算法考察,面试的时候算法题为即时算法考察。
笔试时写的算法允许有较长的思考时间,可以专注功能的实现,而暂时不管空间以及时间复杂度,面试的时候不一样,当你写出一个半吊子算法,往往面试官会让你写出一个更好的,一般也会有一些提示。
面试的时候算法的提问一般不会给你很长时间,短则2分钟最长也5分钟你连思路也没有的话基本就pass了。
这里不管是不是即时考察题型,暂且归纳为一起。
AlgorithmsandDataStructures
1明确数据结构,单一进行操作
1-1单一数据结构
1-1-1链表
在单数据结构(即在题目中明确提到了某种数据结构,没有掺杂,也没有背景,只是进行某些特定操作)的题型中,链表是一大类,而单链表因为其特定的存储结构和读取方法又成为考查的重点。
列举题目如下
(注:
以下题目的给定Node节点全部为如下定义方式)
publicclassNode
{
publicNodenext;
publicobjectdata;
}
1-1-1-1单链表的反转
给定单链表的头节点Nodehead.给出将此链表反转的方法。
publicvoidReverseLinkedList(Nodehead)
{
//首先,反转后必然head为尾部节点,将head的一份拷贝赋值给一个新的node节点,用于托管旧的链表。
NodenDele=head;
//等你将旧链表需要摘取的项加到新链表头部时,需要用另一个node暂时托管旧链表。
NodenNext=null;
//此时就将head置为了新链表的末尾了。
head=null;
while(nDele!
=null)
{
//这几部依次为:
先存下当前节点的下一节点用于备份,之后将dele节点指向新链表的头部并且将新链表的头位置前移,同时控制每次循环都能指向后一个节点向前进行。
nNext=nDele.next;
nDele.next=head;
head=nDele;
nDele=nNext;
}
//至此算法完结。
在这个while循环结束时候,就将原来的链表重新接在了新链表上,完成了逆转操作。
}
1-1-1-2链表相交
给定两个单链表,表头分别为head1和head2.判断两个链表是否相交,如果不相交返回null,如果相交,则给出相交的第一个交点。
对题目进行简单分析后不难得出,因为链表的特殊存储结构,使得其在存储结构上如果交叉则一定为“Y”型或者为“V”型,不可能为“X”型。
所以相交只需求出第一个交点。
算法具体实现可以如下
publicNodeFindSameNode(Nodehead1,Nodehead2)
{
if(head1==null||head2==null)
{
returnnull;
}
//两个Node用于托管两个Linkedlist,这样在操作时候不会破坏原有Node地址。
NodetNode1=head1;
NodetNode2=head2;
//用于记录两个链表的长度。
intlHead1=0,lHead2=0;
//用于求出连个链表的长度,
while(tNode1!
=null)
{
tNode1=tNode1.next;
lHead1++;
}
while(tNode2!
=null)
{
tNode2=tNode2.next;
lHead2++;
}
//到最后都没有相交,必然没有相交。
if(tNode1!
=tNode2)
{
returnnull;
}
//相交了,这时还可以继续从参数提取俩链表首地址。
else
{
tNode1=head1;
tNode2=head2;//没有这两个赋值,他们的next都为null了。
//先假设两个链表长度不一样,求出他们的长度差。
intf=System.Math.Abs(lHead1-lHead2);
//先判断后循环,小优化。
if(lHead1>lHead2)
{
//使长的链表将长的一部分走完,之后就能一起走到交点。
当循环结束,两个链表指针到末尾的长度一样了。
for(intk=0;k { tNode1=tNode1.next; } while(tNode1! =tNode2) { tNode1=tNode1.next; tNode2=tNode2.next; } //两个指针一样了,返回谁都一样。 returntNode1; } else { //长度相等会进此分支,只不过第一个循环不执行。 其余,类似逻辑,只不过判断在外,这样代码多了,但是快一些。 for(intk=0;k { tNode2=tNode2.next; } while(tNode1! =tNode2) { tNode1=tNode1.next; tNode2=tNode2.next; } returntNode1; } } } 1-1-1-3链表倒数第N个节点 给定一个单链表,头节点为nodehead.找出其倒数第N个节点。 算法思路即为给定两个Node,起初在Head节点向后走的时候,使另外一个节点node1托管这个链表的头,在Head向后走了N个节点后,node1向后遍历,在Head为Null时,node1即指向了倒数第N个节点。 算法可以如下: publicNodeFindCountdownNode(Nodehead,intN) { if(head==null){returnnull;} //两个托管指针。 NodenTmpNode=head; NodenCountDownNode=head; //循环结束后,两个指针相差距离为N for(inti=0;i { nTmpNode=nTmpNode.next; } //走到结尾即可。 while(nTmpNode! =null) { nTmpNode=nTmpNode.next; nCountDownNode=nCountDownNode.next; } returnnCountDownNode; } 1-1-1-4删除单个节点 删除单链表中的某节点,或者不知道头节点,这时需要保证此节点不是最后一个节点,或者即使让你知道头节点,但是不允许循环遍历。 思路即为,因为知道这个节点,不遍历,能找到的只有他下一个节点以及他本身,这样的话将他下一个节点的数据和next属性付给当前节点,并将下一节点删除即可,偷梁换柱,达到效果。 代码可以如下: publicvoidDeleOndeNode(NoderandomNode) { //没有判断 NodemyNext=randomNode.next; if(myNext! =null) { randomNode.data=myNext.data; randomNode.next=myNext.next; myNext=null; } else { /*只有当给定head时候才可以处理末尾节点,代码为 Nodecurr_node=head; while(curr_node.next! =ramdomNode){curr_node=curr_node.next;} curr_node=NULL; */ } } 1-1-1-5链表是否有环 如何判断一个链表是否有环存在。 思路为定义两个指针,即好像在操场上跑步,只要两个人速度不一样,速度快的肯定会有套速度慢的一圈的时刻。 难点的还可以加上找到环的入口点,这里暂且不说。 代码可以如下 publicboolIsExistLoop(NodeHead) { if(Head==null||Head.next==null){returnfalse;} if(Head.next==Head) { returntrue; } NodeslowH=Head; NodefastH=Head.next; //两个指针开始追逐 while(slowH! =fastH&&fastH! =null&&fastH.next! =null) { slowH=slowH.next; fastH=fastH.next.next; } //退出循环的条件未知,判断一下是否有环 if(slowH==fastH) { returntrue; } returnfalse; } 1-1-1-6两个递增链表合并为递减链表 给定两个递增的链表,头节点分别为head1,head2,如何操作使之合并为一个递减的链表。 思路为经典的二路归并排序算法,建立一个新链表,开始遍历两个链表,将数值小的插入到新链表的末尾,并且将该节点原来指针向前移动一次,继续比较,大多数情况在遍历玩一个链表后,另外一个会有剩余节点,需要处理。 代码可以如下 publicvoidMergeSortList(Nodehead1,Nodehead2) { //为了不破坏原有链表,依然设立托管指针。 NodeDele1=head1; NodeDele2=head2; NodetmpNode=null; NodetmpNode2=null; Nodehead=null; //判断链表的节点,谁的data值为小的,则将其对接在新链表的末尾,并将新链表前移一位。 //若两个链表值相等,则同时对接在末尾,并使dele1在前。 while(Dele1! =null&&Dele2! =null) { if(Dele1.data { tmpNode=Dele1.next; Dele1.next=head; head=Dele1; Dele1=tmpNode; } elseif(Dele1.data>Dele2.data) { tmpNode=Dele2.next; Dele12.next=head; head=Dele2; Dele2=tmpNode; } else { tmpNode=Dele1.next; tmpNode2=Dele2.next; Dele12.next=head; Dele1.next=Dele2; head=Dele1; Dele1=tmpNode; Dele2=tmpNode2; } } //在此循环之前,其中一个链表已经循环完毕了,下面就是看哪个链表还有剩余. //同逆转的思想,对接到新链表。 while(Dele1.next! =null) { tmpNode=Dele1.next; Dele1.next=head; head=Dele1; Dele1=tmpNode; } while(Dele2.next! =null) { tmpNode=Dele2.next; Dele2.next=head; head=Dele2; Dele2=tmpNode; } //此时head即为新链表的头节点,完成了降序排列,严格来说。 //此算法不是2路归并排序,二路归并排序具体效果是使两个升序链表生成新的升序链表。 //而在操作完了之后还需要一次逆转,我认为这样的效率不如直接逆转。 //如果采用传统的二路归并,核心代码应该如下,切记在完成之后需一次Reverse操作。 /* *判断谁小,假设dele1, *head.next=dele1 *head=dele1 *dele1=dele1.next *等到循环完毕只需要用if不需要用while判断,对接到剩余的链表即可, *if(dele1! =null)head.next=dele1; *if(dele2! =null)head.next=dele2; */ } 1-1-2二叉树 在如下算法中所默认的二叉树节点结构均如下所示: publicclassBinTreeNode { publicobjectdata; publicBinTreeNodeLeftChildTree; publicBinTreeNodeRightChildTree; } 在对二叉树的操作中,频繁的会用到递归,分治的思想。 同时由于二叉树的深度优先,广度优先遍历,以及先序,中序,后序的非递归方式涉及到堆栈以及队列,故列到后面,属于复合数据结构的部分。 1-1-2-1先序,中序,后序遍历 二叉树有3种遍历方式,先序,中序,后序。 三种遍历方式写法类似,都用到了递归: 遍历结果都知道,程序如下: publicvoidPreOrder(BinTreeNodehead) { if(head! =null) { Console.WriteLine(head.data.ToString()); PreOrder(head.LeftChildTree); PreOrder(head.RightChildTree); } } publicvoidMidOrder(BinTreeNodehead) { if(head! =null) { MidOrder(head.LeftChildTree); Console.WriteLine(head.data.ToString()); MidOrder(head.RightChildTree); } } publicvoidPostOrder(BinTreeNodehead) { if(head! =null) { MidOrder(head.LeftChildTree); MidOrder(head.RightChildTree); Console.WriteLine(head.data.ToString()); } } 1-1-2-2求二叉树的深度 同样用递归,算法如下 publicintGetDepth(BinTreeNodehead) { if(head==null)return0; intleftDepth,rightDepth,totalDepth; leftDepth=GetDepth(head.LeftChildTree); rightDepth=GetDepth(head.RightChildTree); totalDepth=leftDepth>rightDepth? leftDepth+1: rightDepth+1; returntotalDepth; } 1-1-2-3求二叉(排序)树的最近公共祖先 算法思想,对于二叉排序树(binarysearchtree)有一个特点,就是对于一个root左节点都是小于他的value的node节点,而root的右节点都大于root的value值,这样的话可以归纳出如下思考方法: 当待寻找的两个节点node1和node2,满足node1.data 若都大于则去右树寻找,再不然就一定是root节点, 可以得到程序如下 publicBinTreeNodeSearchCommonFather(BinTreeNodenode1,BinTreeNodenode2,BinTreeNodehead) { if(head==null)returnnull; if(node1.data>head.data&&node2.data>head.data) { returnSearchCommonFather(node1,node2,head.RightChildTree); } elseif(node1.data { returnSearchCommonFather(node1,node2,head.LeftChildTree); } else returnhead; } 难点在于对于普通二叉树的查找最近公共祖先。 非常麻烦,一般也不会问到。 感兴趣的可以去搜索“二叉树RMQ”问题。 而对于二叉排序树找公共祖先是属于LCA问题。 1-1-2-4二叉排序树转换为循环双向链表 思路仍然为递归,先将左子树变为LinkedList(LL),再将右子树变为LL,之后将左子树,Root,右子树变为一个整体的LL. 代码可以如下 #regionBST-To-DoubleSortedLinkedList //此函数用于将两个LinkedList首尾对接。 publicBinTreeNodeAppendLL(BinTreeNodenode1,BinTreeNodenode2) { if(node1==null) returnnode2; if(node2==null) returnnode1; //找到尾巴节点 BinTreeNodetail1=node1.LeftChildTree; BinTreeNodetail2=node2.RightChildTree; //完成首尾对接,两个首尾都需要对接 tail1.RightChildTree=node2; node2.LeftChildTree=tail1; tail2.RightChildTree=node1; node1.LeftChildTree=tail2; returnnode1; } publicBinTreeNodeConvertBstToLinkedList(BinTreeNodehead) { if(head==null)returnnull; //求出左右子树的链表。 BinTreeNodeleftLL=ConvertBstToLinkedList(head.LeftChildTree); BinTreeNoderightLL=ConvertBstToLinkedList(head.RightChildTree); //首先让head独立,不然乱了,具体原因可以查看Append函数。 head.RightChildTree=head; head.LeftChildTree=head; //嫁接 leftLL=AppendLL(leftLL,head); leftLL=AppendLL(leftLL,rightLL); returnleftLL; } #endregion 1-1-2-5计算一个二叉树的叶子数目 同样的思想,总之二叉树递归就对了,注意设置递归的出口。 代码如下 publicvoidCountTreeLeaf(BinTreeNodehead,refintcount) { //用Out传址方式返回数目。 count=0; if(head! =null) { if(head.LeftChildTree==null&&head.RightChildTree==null) count++; //分别计算左右子树,计算完毕后Count即为叶子数目。 CountTreeLeaf(head.LeftChildTree,refcount); CountTreeLeaf(head.RightChildTree,refcount); } } //没有带返回值,也没有调试,这样不方便是需要在调用时确定Count为0,或者可以用返回int值的。 左右相加即可 1-1-2-6求二叉树叶子节点的最大距离 此为编程之美上的一道算法题,文章在最后着重说了如何控制递归的调用和退出。 所谓距离,就是指两个节点之间的距离。 可以想象,距离最远两个节点必然为两个叶子节点,假设根节点为K,两个最大距离的节点为U和V,那么有两种情况: (1)U和V分别在K节点的两个子树上,那么他们之间的路线必然经过K. (2)U和V在K节点的一个子树上,那么他们之间的路线必然不经过K. 问题即可以转化为在子树上求最大距离的点,之后Max一下就可以了。 注: 在做这个问题的时候,需要在以前的BinTreeNode重新派生一个类,其中多出来两个属性用以记录该节点左子树和右子树中的最长距离,或者直接加也可,否则无法编译通过。 代码如下,参照编程之美。 intmaxlen=0; publicvoidFindMaxLen(BinTreeNodehead) { //空树 if(head==null)return; //一下两步用于判断左右子树是否为空,在给属性赋值完毕之后,用递归确保程序执行,而真正算距离的还没开始,也是到达叶子节点以后的反弹阶段。 if(head.LeftChildTree==null) { head.nMaxLeft=0; } else { FindMaxLen(head.LeftChildTree); } if(head.RightChildTree==null) { head.nMaxRight=0; } else { FindMaxLen(head.RightChildTree); } //这里计算左子树的最大距离,非叶子节点都要经过这里两个逻辑中至少一个。 if(head.LeftChildTree! =null) { intnTempMax=0; //判断左右子树哪个更深 head.LeftChildTree.nMaxLeft>head.Le
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序 算法 总结 没有 密码 版本