数据结构常见编程题小结.docx

1、 单链表因为单链表要考虑的可能性比较少，所以单链表的题目比较简单，而且比较常考。特别要注意的是链表的数据的插入和删除，因为（没有头节点）的单链表在第一个元素之前插入和删除和最后一个元素的插入删除需要特别考虑。做题时，最好把单链表的示意图画出来，这样就很方便写代码了。常用技巧：快慢指针，拆分链表数据结构定义如下：C+ Code12345structListNodeintval;/值ListNode*next;/下一个元素ListNode(intx):val(x),next(NULL)/new初始化;下面是一些常考的题目：（1） Linked List Cycle-判断一个链表是否有环最好的方法是时间复杂度 O(n)，空间复杂度 O(1) 的。设置两个指针，一个快一个慢，快的指针每次走两步，慢的指针每次走一步，如果快指针和慢指针相遇，则说明有环。（如何证明，上网找找）代码实现如下：C+ Code123456789101112131415161718/LeetCode,LinkedListCycle/时间复杂度O(n)，空间复杂度O(1)classSolutionpublic:boolhasCycle(ListNode*head)/设置两个指针，一个快一个慢ListNode*slow=head,*fast=head;while(fast&fast-next)slow=slow-next;fast=fast-next-next;if(slow=fast)returntrue;returnfalse;（2） Linked List Cycle II-链表有环，找出环的起始点当 fast 与 slow 相遇时，slow 肯定没有遍历完链表，而 fast 已经在环内循环了 n 圈 (1 n)。假设 slow 走了 s 步，则 fast 走了 2s 步（fast 步数还等于 s 加上在环上多转的 n 圈），设环长为 r，则：2s = s + nrs = nr设整个链表长 L，环入口点与相遇点距离为 a，起点到环入口点的距离为 x，则x + a = nr = (n1)r + r = (n 1)r + L xx = (n 1)r + (Lxa)Lxa 为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于 n 1 圈内环 + 相遇点到环入口点，于是我们可以从 head 开始另设一个指针 slow2，两个慢指针每次前进一步，它俩一定会在环入口点相遇。C+ Code1234567891011121314151617181920212223242526/LeetCode,LinkedListCycleII/时间复杂度O(n)，空间复杂度O(1)classSolutionpublic:ListNode*detectCycle(ListNode*head)ListNode*slow=head,*fast=head;while(fast&fast-next)slow=slow-next;fast=fast-next-next;if(slow=fast)ListNode*slow2=head;while(slow2!=slow)slow2=slow2-next;slow=slow-next;returnslow2;returnnullptr;（3） Add Two NumberYou are given two linked lists representing two non-negative numbers. The digits are stored in reverseorder and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.Input: (2 - 4 - 3) + (5 - 6 - 4)Output: 7 - 0 - 8代码实现如下：C+ Code12345678910111213141516171819202122232425262728/LeetCode,AddTwoNumbers/跟AddBinary很类似/时间复杂度O(m+n)，空间复杂度O(1)classSolutionpublic:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2)ListNodedummy(-1);/头节点intcarry=0;ListNode*prev=&dummy;for(ListNode*pa=l1,*pb=l2;pa!=nullptr|pb!=nullptr;pa=pa=nullptr?nullptr:pa-next,pb=pb=nullptr?nullptr:pb-next,prev=prev-next)constintai=pa=nullptr?0:pa-val;constintbi=pb=nullptr?0:pb-val;constintvalue=(ai+bi+carry)%10;carry=(ai+bi+carry)/10;prev-next=newListNode(value);/尾插法if(carry0)prev-next=newListNode(carry);returndummy.next;（4）Partition List描述Given a linked list and a value x, partition it such that all nodes less than x come before nodes greaterthan or equal to x.You should preserve the original relative order of the nodes in each of the two partitions.For example, Given 1-4-3-2-5-2 and x = 3, return 1-2-2-4-3-5.C+ Code123456789101112131415161718192021222324252627282930/LeetCode,PartitionList/时间复杂度O(n)，空间复杂度O(1)classSolutionpublic:ListNode*partition(ListNode*head,intx)ListNodeleft_dummy(-1);/头结点ListNoderight_dummy(-1);/头结点autoleft_cur=&left_dummy;autoright_cur=&right_dummy;for(ListNode*cur=head;cur;cur=cur-next)if(cur-valnext=cur;left_cur=cur;elseright_cur-next=cur;right_cur=cur;left_cur-next=right_dummy.next;right_cur-next=nullptr;returnleft_dummy.next;2、 栈和队列基本概念：手动实现一个栈或者队列。剑指offer上面的最大栈的实现。3、 字符串常用C语言库实现：C+ Code1234567891011121314151617181920212223242526272829303132333435char*strcpy(char*dst,constchar*src)if(dst=src)returndst;assert(dst!=NULL&src!=NULL);char*addr=dst;while(*dst+=*src+)!=0);returnaddr;intstrcmp(constchar*s,constchar*t)assert(s!=NULL&t!=NULL)while(*s&*t&*s=*t)+s;+t;return(*s-*t);voidmemcpy(void*dst,constvoid*src,intcount)assert(dst!=NULL&src!=NULL);void*addr=dst;while(cout-)*(char*)dst=*(char*)src;dst=(char*)dst+;src=(char*)src+;returnaddr;intmemcmp(constvoid*s,constvoid*t,intcount)assert(s!=NULL&t!=NULL);while(*(char*)s&*(char*)t&*(char*)s=*(char*)t&count-)s=(char*)s+;t=(char*)t+;return(*(char*)s-*(char*)t);4、 数组（1） Two SumGiven an array of integers, find two numbers such that they add up to a specific target number.The function twoSum should return indices of the two numbers such that they add up to the target, whereindex1 must be less than index2. Please note that your returned answers (both index1 and index2) are notzero-based.You may assume that each input would have exactly one solution.Input: numbers=2, 7, 11, 15, target=9Output:true分析：先排序，然后左右夹逼，排序 O(n log n)，左右夹逼 O(n)，最终 O(n log n)booltowSum(int*arr,intlen,inttarget)intleft=0;intright=len-1;qsort(arr,0,len-1);while(leftright)if(arrleft+arrright=target)returntrue;elseif(arrleft+arrrighttarget)left+;elseright-;returnfalse; （2） Single Number描述Given an array of integers, every element appears twice except for one. Find that single one.Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?分析异或，不仅能处理两次的情况，只要出现偶数次，都可以清零。C+ Code12345678910111213/LeetCode,SingleNumber/时间复杂度O(n)，空间复杂度O(1)classSolutionpublic:intsingleNumber(intA,intn)intx=0;for(size_ti=0;in;+i)x=Ai;returnx;（3） Search in Rotated Sorted Array题目意思：给定一个已排序数组，旋转了几次的，然后在这个旋转的数组里面查找一个目标值。分析二分查找，难度主要在于左右边界的确定。C+ Code12345678910111213141516171819202/LeetCode,SearchinRotatedSortedArray/时间复杂度O(logn)，空间复杂度O(1)classSolutionpublic:intsearch(intA,intn,inttarget)intfirst=0,last=n;while(first!=last)constintmid=(first+last)/2;if(Amid=target)returnmid;if(Afirst=Amid)if(Afirst=target&targetAmid)last=mid;elsefirst=mid+1;elseif(Amidtarget&target=Alast-1)first=mid+1;elselast=mid;return-1;5、 二叉树二叉树的基本概念：（1）度：某节点所拥有的子树的个数称为该节点的度；树中各个节点读的最大值称为该树的度。（2）节点的层数、树的深度：规定根节点的层数为1，对于其余任何节点，若某节点在第k层，则其孩子节点在第k+1层。树中所有节点的最大层数称为树的深度，也称为树的高度。（3）满二叉树：在一颗二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。（4） 完全二叉树对一颗具有n个节点的二叉树按层序编号，如果编号为i（1=i=n）的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则这颗二叉树称为完全二叉树。（5） 二叉查找树二叉查找树，或者是一颗空的二叉树，或者是具有如下性质的二叉树：（1） 若它的左子树不空，则左子树上所有节点的值均小于根结点的值。（2） 若它的右子树不空，则右子树上所有节点的值均大于根节点的值（3） 它的左右子树也都是二叉查找树。二叉树解题思路：主要是通过递归解决问题。见到二叉树的题目，优先从递归方向考虑。递归都需要返回的，考虑好返回的边界条件是什么，一般是当节点是空的时候就返回。（1） 二叉树的遍历（递归的比较简单，上网看看）非递归前序：使用栈实现C+ Code1234567891011121314151617181920212223/LeetCode,BinaryTreePreorderTraversal/使用栈，时间复杂度O(n)，空间复杂度O(n)classSolutionpublic:vectorpreorderTraversal(TreeNode*root)vectorresult;constTreeNode*p;stacks;p=root;if(p!=nullptr)s.push(p);while(!s.empty()p=s.top();s.pop();result.push_back(p-val);if(p-right!=nullptr)s.push(p-right);if(p-left!=nullptr)s.push(p-left);returnresult;非递归中序遍历：使用栈实现C+ Code12345678910111213141516171819202122232425262728/LeetCode,BinaryTreeInorderTraversal/使用栈，时间复杂度O(n)，空间复杂度O(n)classSolutionpublic:vectorinorderTraversal(TreeNode*root)vectorresult;constTreeNode*p=root;stacks;while(!s.empty()|p!=nullptr)if(p!=nullptr)s.push(p);p=p-left;elsep=s.top();s.pop();result.push_back(p-val);p=p-right;returnresult;非递归后序遍历：C+ Code1234567891011121314151617181920212223242526272829303132333435363738394041424344/LeetCode,BinaryTreePostorderTraversal/使用栈，时间复杂度O(n)，空间复杂度O(n)classSolutionpublic:vectorpostorderTraversal(TreeNode*root)vectorresult;/*p，正在访问的结点，q，刚刚访问过的结点*/constTreeNode*p,*q;stacks;p=root;dowhile(p!=nullptr)/*往左下走*/s.push(p);p=p-left;q=nullptr;while(!s.empty()p=s.top();s.pop();/*右孩子不存在或已被访问，访问之*/if(p-right=q)result.push_back(p-val);q=p;/*保存刚访问过的结点*/else/*当前结点不能访问，需第二次进栈*/s.push(p);/*先处理右子树*/p=p-right;break;while(!s.empty();returnresult;层次遍历：描述Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level bylevel).For example: Given binary tree 3,9,20,#,#,15,7,3/ 9 20/ 15 7return its level order traversal as:3,9,20,15,7层次遍历，是广度搜索，使用队列实现：C+ Code123456789101112131415/LeetCode,BinaryTreeLevelOrderTraversal/递归版，时间复杂度O(n)，空间复杂度O(n)classSolutionpublic:vectorvectorlevelOrder(TreeNode*root)vectorvectorresult;traverse(root,1,result);returnresult;voidtraverse(TreeNode*root,size_tlevel,vectorvector&result)if(!root)return;if(levelresult.size()result.push_back(vector();resultlevel-1.push_back(root-val);traverse(root-left,level+1,result);traverse(root-right,level+1,result);（2） Same Tree 判断两棵树是否一样，二叉树常用的思想是递归，用好递归C+ Code123456789101112131415/递归版/LeetCode,SameTree/递归版，时间复杂度O(n)，空间复杂度O(logn)classSolutionpublic:boolisSameTree(TreeNode*p,TreeNode*q)if(!p&!q)returntrue;/终止条件if(!p|!q)returnfalse;/剪枝returnp-val=q-val/三方合并&isSameTree(p-left,q-left)&isSameTree(p-right,q-right);（3） Symmetric Tree 判断两棵树是否是镜像的，同样采用递归实现C+ Code123456789101112131/LeetCode,SymmetricTree/递归版，时间复杂度O(n)，空间复杂度O(logn)classSolutionpublic:boolisSymmetric(TreeNode*root)returnroot?isSymmetric(root-left,root-right):true;boolisSymmetric(TreeNode*left,TreeNode*right)if(!left&!right)returntrue;/终止条件if(!left|!right)returnfalse;/终止条件returnleft-val=right-val/三方合并&isSymmetric(left-left,right-right)&isSymmetric(left-right,right-left);（4） Balanced Binary Tree 判断一棵树是否是平衡的。C+ Code12345678910111213141516/LeetCode,BalancedBinaryTree/时间复杂度O(n)，空间复杂度O(logn)classSolutionpublic:boolisBalanced(TreeNode*root)returnbalancedHeight(root)=0;/*Returnstheheightofrootifrootisabalancedtree,*otherwise,returns-1.*/intbalancedHeight(TreeNode*root)if(root=nullptr)return0;/终止条件intleft=balancedHeight(root-left);intright=balancedHeight(root-right);if(left0|right1)return-1;/剪枝returnmax(left,right)+1;/三方合并;（4）二叉查找树 判断是否是二叉查找树 Validate Binary Search TreeC+ Code12345678910111213/LeetCode,ValidateBinarySearchTree/时间复杂度O(n)，空间复杂度O(logn)classSolutionpublic:boolisValidBST(TreeNode*root)returnisValidBST(root,INT_MIN,INT_MAX);boolisValidBST(TreeNode*root,intlower,intupper)if(root=nullptr)returntrue;returnroot-vallower&root-valleft,lower,root-val)&isValidBST(root-right,root-val,upper);（5） 一颗树的最大深度C+ Code12345678910/LeetCode,MaximumDepthofBinaryTree/时间复杂度O(n)，空间复杂度O(logn)classSolutionpublic:intmaxDepth(TreeNode*root)if(root=nullptr)return0;returnmax(maxDepth(root-left),maxDepth(root-right)+1;（6） 一棵树的最小深度C+ Code1234567891011121314/LeetCode,MinimumDepthofBinaryTree/递归版，时间复杂度O(n)，空间复杂度O(logn)classSolutionpublic:intminDepth(constTreeNode*root)returnminDepth(root,false);private:staticintminDepth(constTreeNode*root,boolhasbrother)if(!root)returnhasbrother?INT_MAX:0;return1+min(minDepth(root-left,root-right!=NULL),minDepth(root-right,root-left!=NULL);（7） Path Sum描述Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all thevalues along the path equals the given sum.For example: Given the below binary tree and sum = 22,return true, as there exist a root-to-leaf path 5-4-11-2 which sum is 22.C+ Code123456789101112/LeetCode,PathSum/时间复杂度O(n)，空间复杂度O(logn)classSolutionpublic:boolhasPathSum(TreeNode*root,intsum)if(root=nullptr)returnfalse;if(root-left=nullptr&root-right=nullptr)/leafreturnsum=root-val;returnhasPathSum(root-left,sum-root-val)|hasPathSum(root-right,sum-root-val);（8） 两个结点的最低公共祖先二叉查找树版本：C+ Code1234567891011121314151617181920212223242526272829303132333435363738394041/copyrighteriol2011/modifiedbyJuly2014publicintquery(Nodet,Nodeu,Nodev)intleft=u.value;intright=v.value;Nodeparent=null;/二叉查找树内，如果左结点大于右结点，不对，交换if(leftright)inttemp=left;left=right;right=temp;while(true)/如果t小于u、v，往t的右子树中查找if(t