Leetcode数组类题目总结(Java版本)

Leetcode151题目详解1第一章线性表此类题目考察线性表的操作，例如数组，单链表，双向链表1.1RemoveDuplicatesfromSortedArray描述Givenasortedarray,removetheduplicatesinplacesuchthateachelementappearonlyonceandreturnthenewlength.Donotallocateextraspaceforanotherarray,youmustdothisinplacewithconstantmemory.Forexample,GiveninputarrayA=[1,1,2],Yourfunctionshouldreturnlength=2,andAisnow[1,2].分析无代码：publicclassSolution{publicintremoveDuplicates(int[]A){if(A==null||A.length==0)return0;intindex=0;for(inti=1;iA.length;i++){if(A[index]!=A[i]){A[++index]=A[i];}}returnindex+1;}}相关题：RemoveDuplicatesfromSortedArrayII见1.21.2RemoveDuplicatesfromSortedArrayII描述Followupfor”RemoveDuplicates”:Whatifduplicatesareallowedatmosttwice?Forexample,GivensortedarrayA=[1,1,1,2,2,3],Yourfunctionshouldreturnlength=5,andAisnow[1,1,2,2,3]分析可以加一个变量来记录重复元素的个数能很好的解决问题。由于此题已经是排序的了，如果是没有排序的，可以使用hashmap来求元素的个数。代码publicclassSolution{publicintremoveDuplicates(int[]A){if(A==null||A.length==0)return0;intindex=0,cnt=0;for(inti=1;iA.length;i++){if(A[index]!=A[i]){A[++index]=A[i];cnt=0;}elseif(A[index]==A[i]&&cnt1){A[++index]=A[i];cnt++;}}returnindex+1;}}相关题扩展该题到可重复n次的场景，只需要将cnt的上限设为n-1即可。1.3SearchinRotatedSortedArray描述Supposeasortedarrayisrotatedatsomepivotunknowntoyoubeforehand.(i.e.,0124567mightbecome4567012).Youaregivenatargetvaluetosearch.Iffoundinthearrayreturnitsindex,otherwisereturn-1.Youmayassumenoduplicateexistsinthearray.分析二分查找，此题要特别注意边界值。此题的边界比较多。（1）mid的位置判定，mid可能在左边区域，也可能在右边区域，需求通过（A[mid]与A[first]大小关系进行判定）（2）在判定边界时，要注意考虑大于，小于，等于三种情况，在写代码时，本题我开始忘记了一个等号，如代码中标红的地方。（3）二分的思想是一步一步将区域缩小，并且要充分考虑缩小的正确性，不能放松对边界的警惕（即要注意等于的情况）。如图所示：FirstmidlastFirstmidlast要注意mid落在哪个区域，通过A[mid]与A[first]大小比较可以确定，同时要注意边界条件的判断，当A[mid]==A[first]应该是将其归类A[mid]A[first]的情况。代码publicintsearch(int[]A,inttarget){if(A==null||A.length==0)return-1;intfirst=0,last=A.length-1;while(first=last){intmid=(first+last)/2;if(A[mid]==target){returnmid;}elseif(A[mid]=A[first]){if(target=A[first]&&targetA[mid]){last=mid-1;}else{first=mid+1;}}else{if(targetA[mid]&&target=A[last]){first=mid+1;}else{last=mid-1;}}}return-1;}相关题目SearchinRotatedSortedArrayII，见§1.41.4SearchinRotatedSortedArrayII描述Followupfor”SearchinRotatedSortedArray”:Whatifduplicatesareallowed?Wouldthisaffecttherun-timecomplexity?Howandwhy?Writeafunctiontodetermineifagiventargetisinthearray.分析问题就出在边界上，即A[mid]==A[first]的情况，如果这样，那么无法确定mid的位置属于上题的图一还是图二。因此这时判断A[first]==target,如果不成立则first++缩小一个范围。代码publicclassSolution{publicbooleansearch(int[]A,inttarget){if(A==null||A.length==0)returnfalse;intfirst=0,last=A.length-1;while(first=last){intmid=(first+last)/2;if(A[mid]==target){returntrue;}elseif(A[mid]A[first]){if(target=A[first]&&targetA[mid]){last=mid-1;}else{first=mid+1;}}elseif(A[mid]A[first]){if(targetA[mid]&&target=A[last]){first=mid+1;}else{last=mid-1;}}else{if(A[first]==target)returntrue;elsefirst++;}}returnfalse;}}相关题目1.3SearchinRotatedSortedArray1.5MedianofTwoSortedArrays描述TherearetwosortedarraysAandBofsizemandnrespectively.Findthemedianofthetwosortedarrays.TheoverallruntimecomplexityshouldbeO(log(m+n)).分析看到本题对算法的复杂度要求非常的高，是对数级别的，因此一定要运用二分查找的思想才行。本题更通用的问法是求第k个数。现在需要我们求的是中位数即第（m+n）/2个数。但也不完全准确，如果数组的个数是奇数，那么应该是（m+n）/2,如果是偶数，那么是((m+n)/2+(m+n)/2+1)/2.现在问题转换成了求第K+1个数。（此处的K从1开始计算），从1开始是为了方便。思路是两个数组都查找弟k/2个数，如果A[k/2]==B[k/2]returnA[k/2]A[[k/2]B[k/2]递归找k-k/2个数，且b的start位置为k/2+1A[k/2]B[k/2]同样递归找k-k/2,且a的start位置为k/2+1同时要注意如果两个数组长度悬殊太大，那么段数组可能不存在第k/2个元素，因此这是的K为short.length。此题的边界条件判断比较繁琐，当k==1时还需要单独判断，这个在考虑的时候没考虑到是在用例测试的时候发现的问题。代码publicclassSolution{publicdoublefindMedianSortedArrays(intA[],intB[]){intlena=A.length;intlenb=B.length;intlen=lena+lenb;if(len%2==0){return(findMedianCore(A,B,0,lena-1,0,lenb-1,len/2)+findMedianCore(A,B,0,lena-1,0,lenb-1,len/2+1))/2;}else{returnfindMedianCore(A,B,0,lena-1,0,lenb-1,len/2+1);}}publicdoublefindMedianCore(int[]A,int[]B,intastart,intaend,intbstart,intbend,intk){intlena=aend-astart+1;intlenb=bend-bstart+1;//thelengthofaisalwayssmallerthanthelengthofbif(lenalenb){returnfindMedianCore(B,A,bstart,bend,astart,aend,k);}if(lena=0){returnB[bstart+k-1];}if(k==1){returnA[astart]B[bstart]?B[bstart]:A[astart];}intpa=k/2lena?lena:k/2;intpb=k-pa;if(A[astart+pa-1]==B[bstart+pb-1]){returnA[astart+pa-1];}elseif(A[astart+pa-1]B[bstart+pb-1]){returnfindMedianCore(A,B,astart,aend,bstart+pb,bend,k-pb);}else{returnfindMedianCore(A,B,astart+pa,aend,bstart,bend,k-pa);}}}相关题目无1.6LongestConsecutiveSequence描述Givenanunsortedarrayofintegers,findthelengthofthelongestconsecutiveelementssequence.Forexample,Given[100,4,200,1,3,2],Thelongestconsecutiveelementssequenceis[1,2,3,4].Returnitslength:4.YouralgorithmshouldruninO(n)complexity.分析此题由于复杂度是O(n)因此不能排序。因此想到用hash。考虑数组当hash但是由于题目中说是整型，因此不能用。所以使用HashSet解决。将所有的数放入集合中（已经去重）。取数，前后探索，记录连续的个数更新max。当set为空时返回的max即为最大值。本题在实验室发现一个问题，即你在遍历集合的时候修改集合会报错，java.util.ConcurrentModificationException，因此我采用了HashMap来做，value记录是否访问过。代码importjava.util.Map.Entry;publicclassSolution{publicintlongestConsecutive(int[]num){if(num==null)return0;HashMapInteger,Booleanset=newHashMapInteger,Boolean();for(inti=0;inum.length;i++){set.put