算法面试笔试总结Word文档格式.docx
《算法面试笔试总结Word文档格式.docx》由会员分享，可在线阅读，更多相关《算法面试笔试总结Word文档格式.docx（56页珍藏版）》请在冰点文库上搜索。
//至此算法完结。
在这个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!
tNode1=tNode1.next;
lHead1++;
while（tNode2!
tNode2=tNode2.next;
lHead2++;
//到最后都没有相交，必然没有相交。
if（tNode1!
=tNode2）
//相交了，这时还可以继续从参数提取俩链表首地址。
else
tNode1=head1;
tNode2=head2;
//没有这两个赋值，他们的next都为null了。
//先假设两个链表长度不一样，求出他们的长度差。
intf=System.Math.Abs（lHead1-lHead2）;
//先判断后循环，小优化。
if（lHead1>
lHead2）
//使长的链表将长的一部分走完，之后就能一起走到交点。
当循环结束，两个链表指针到末尾的长度一样了。
for（intk=0;
k<
f;
k++）
//两个指针一样了，返回谁都一样。
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<
N;
i++）
nTmpNode=nTmpNode.next;
//走到结尾即可。
while（nTmpNode!
nCountDownNode=nCountDownNode.next;
returnnCountDownNode;
1-1-1-4删除单个节点
删除单链表中的某节点，或者不知道头节点，这时需要保证此节点不是最后一个节点，或者即使让你知道头节点，但是不允许循环遍历。
思路即为，因为知道这个节点，不遍历，能找到的只有他下一个节点以及他本身，这样的话将他下一个节点的数据和next属性付给当前节点，并将下一节点删除即可，偷梁换柱，达到效果。
代码可以如下：
publicvoidDeleOndeNode（NoderandomNode）
//没有判断
NodemyNext=randomNode.next;
if（myNext!
randomNode.data=myNext.data;
randomNode.next=myNext.next;
myNext=null;
/*只有当给定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!
slowH=slowH.next;
fastH=fastH.next.next;
//退出循环的条件未知，判断一下是否有环
if（slowH==fastH）
returnfalse;
1-1-1-6两个递增链表合并为递减链表
给定两个递增的链表，头节点分别为head1,head2,如何操作使之合并为一个递减的链表。
思路为经典的二路归并排序算法，建立一个新链表，开始遍历两个链表，将数值小的插入到新链表的末尾，并且将该节点原来指针向前移动一次，继续比较，大多数情况在遍历玩一个链表后，另外一个会有剩余节点，需要处理。
publicvoidMergeSortList（Nodehead1,Nodehead2）
//为了不破坏原有链表，依然设立托管指针。
NodeDele1=head1;
NodeDele2=head2;
NodetmpNode=null;
NodetmpNode2=null;
Nodehead=null;
//判断链表的节点，谁的data值为小的，则将其对接在新链表的末尾，并将新链表前移一位。
//若两个链表值相等，则同时对接在末尾，并使dele1在前。
while（Dele1!
Dele2!
if（Dele1.data<
Dele2.data）
tmpNode=Dele1.next;
Dele1.next=head;
head=Dele1;
Dele1=tmpNode;
elseif（Dele1.data>
tmpNode=Dele2.next;
Dele12.next=head;
head=Dele2;
Dele2=tmpNode;
tmpNode2=Dele2.next;
Dele1.next=Dele2;
Dele2=tmpNode2;
//在此循环之前，其中一个链表已经循环完毕了，下面就是看哪个链表还有剩余.
//同逆转的思想，对接到新链表。
while（Dele1.next!
while（Dele2.next!
Dele2.next=head;
//此时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
publicBinTreeNodeLeftChildTree;
publicBinTreeNodeRightChildTree;
在对二叉树的操作中，频繁的会用到递归，分治的思想。
同时由于二叉树的深度优先，广度优先遍历，以及先序，中序，后序的非递归方式涉及到堆栈以及队列，故列到后面，属于复合数据结构的部分。
1-1-2-1先序，中序，后序遍历
二叉树有3种遍历方式，先序，中序，后序。
三种遍历方式写法类似，都用到了递归：
遍历结果都知道，程序如下：
publicvoidPreOrder（BinTreeNodehead）
if（head!
Console.WriteLine（head.data.ToString（））;
PreOrder（head.LeftChildTree）;
PreOrder（head.RightChildTree）;
publicvoidMidOrder（BinTreeNodehead）
MidOrder（head.LeftChildTree）;
MidOrder（head.RightChildTree）;
publicvoidPostOrder（BinTreeNodehead）
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.data&
node2.data<
root.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<
node2.data<
returnSearchCommonFather（node1,node2,head.LeftChildTree）;
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;
publicBinTreeNodeConvertBstToLinkedList（BinTreeNodehead）
//求出左右子树的链表。
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.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;
FindMaxLen（head.LeftChildTree）;
if（head.RightChildTree==null）
head.nMaxRight=0;
FindMaxLen（head.RightChildTree）;
//这里计算左子树的最大距离，非叶子节点都要经过这里两个逻辑中至少一个。
if（head.LeftChildTree!
intnTempMax=0;
//判断左右子树哪个更深
head.LeftChildTree.nMaxLeft>
head.LeftChildTree.nMaxRight?
nTempMax=head.LeftChildTree.nMaxLeft:
nTempMax=head.LeftChildTree.nMaxRight;
//将左右子树更深的+和根节点的这条连线，作为这个子树的深度。
head.LeftChildTree.nMaxLeft=nTempMax+1;
//右子树
if（head.RightChildTree!
head.RightChildTree.nMaxLeft>
head.RightChild
升级会员 