数据结构常见编程题小结

1、单链表因为单链表要考虑的可能性比较少，所以单链表的题目比较简单，而且比较常考。特别要注意的是链表的数据的插入和删除，因为（没有头节点）的单链表在第一个元素之前插入和删除和最后一个元素的插入删除需要特别考虑。做题时，最好把单链表的示意图画出来，这样就很方便写代码了。常用技巧：快慢指针，拆分链表数据结构定义如下：C++Code12345structListNode{intval;//值ListNode*next;//下一个元素ListNode(intx):val(x),next(NULL){}//new初始化};下面是一些常考的题目：（1）LinkedListCycle-判断一个链表是否有环最好的方法是时间复杂度O(n)，空间复杂度O(1)的。设置两个指针，一个快一个慢，快的指针每次走两步，慢的指针每次走一步，如果快指针和慢指针相遇，则说明有环。（如何证明，上网找找）代码实现如下：C++Code123456789101112131415161718//LeetCode,LinkedListCycle//时间复杂度O(n)，空间复杂度O(1)classSolution{public: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）LinkedListCycleII-链表有环，找出环的起始点当fast与slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈(1n)。假设slow走了s步，则fast走了2s步（fast步数还等于s加上在环上多转的n圈），设环长为r，则：2s=s+nrs=nr设整个链表长L，环入口点与相遇点距离为a，起点到环入口点的距离为x，则x+a=nr=(n–1)r+r=(n1)r+Lxx=(n1)r+(L–x–a)L–x–a为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于n1圈内环+相遇点到环入口点，于是我们可以从head开始另设一个指针slow2，两个慢指针每次前进一步，它俩一定会在环入口点相遇。C++Code1234567891011121314151617181920212223242526//LeetCode,LinkedListCycleII//时间复杂度O(n)，空间复杂度O(1)classSolution{public: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）AddTwoNumberYouaregiventwolinkedlistsrepresentingtwonon-negativenumbers.Thedigitsarestoredinreverseorderandeachoftheirnodescontainasingledigit.Addthetwonumbersandreturnitasalinkedlist.Input:(2-4-3)+(5-6-4)Output:7-0-8代码实现如下：C++Code12345678910111213141516171819202122232425262728//LeetCode,AddTwoNumbers//跟AddBinary很类似//时间复杂度O(m+n)，空间复杂度O(1)classSolution{public: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）PartitionList描述Givenalinkedlistandavaluex,partitionitsuchthatallnodeslessthanxcomebeforenodesgreaterthanorequaltox.Youshouldpreservetheoriginalrelativeorderofthenodesineachofthetwopartitions.Forexample,Given1-4-3-2-5-2andx=3,return1-2-2-4-3-5.C++Code123456789101112131415161718192021222324252627282930//LeetCode,PartitionList//时间复杂度O(n)，空间复杂度O(1)classSolution{public: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-valx){left_cur-next=cur;left_cur=cur;}else{right_cur-next=cur;right_cur=cur;}}left_cur-next=right_dummy.next;right_cur-next=nullptr;returnleft_dummy.next;}};2、栈和队列基本概念：手动实现一个栈或者队列。剑指offer上面的最大栈的实现。3、字符串常用C语言库实现：C++Code12345char*strcpy(char*dst,constchar*src){if(dst==src)returndst;assert(dst!=NULL&&src!=NULL);char*addr=dst;while((*dst++=*src++)!='\0');67891011121314151617181920212223242526272829303132333435returnaddr;}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）TwoSumGivenanarrayofintegers,findtwonumberssuchthattheyadduptoaspecifictargetnumber.ThefunctiontwoSumshouldreturnindicesofthetwonumberssuchthattheyadduptothetarget,whereindex1mustbelessthanindex2.Pleasenotethatyourreturnedanswers(bothindex1andindex2)arenotzero-based.Youmayassumethateachinputwouldhaveexactlyonesolution.Input:numbers={2,7,11,15},target=9Output:true分析：先排序，然后左右夹逼，排序O(nlogn)，左右夹逼O(n)，最终O(nlogn)booltowSum(int*arr,intlen,inttarget){intleft=0;intright=len-1;qsort(arr,0,len-1);while(leftright){if(arr[left]+arr[right]==target){returntrue;}elseif(arr[left]+arr[right]target){left++;}else{right--;}}returnfalse;}（2）SingleNumber描述Givenanarrayofintegers,everyelementappearstwiceexceptforone.Findthatsingleone.Note:Youralgorithmshouldhavealinearruntimecomplexity.Couldyouimplementitwithoutusingextramemory?分析异或，不仅能处理两次的情况，只要出现偶数次，都可以清零。C++Code12345678910111213//LeetCode,SingleNumber//时间复杂度O(n)，空间复杂度O(1)classSolution{public:intsingleNumber(intA[],intn){intx=0;for(size_ti=0;in;++i)x^=A[i];returnx;}};（3）SearchinRotatedSortedArray题目意思：给定一个已排序数组，旋转了几次的，然后在这个旋转的数组里面查找一个目标值。分析二分查找，难度主要在于左右边界的确定。C++Code123456789101112131415161718//LeetCode,SearchinRotatedSortedArray//时间复杂度O(logn)，空间复杂度O(1)classSolution{public:intsearch(intA[],intn,inttarget){intfirst=0,last=n;while(first!=last){constintmid=(first+last)/2;if(A[mid]==target)returnmid;if(A