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

《Leetcode数组类题目总结(Java版本)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Leetcode151题目详解1第一章线性表此类题目考察线性表的操作，例如数组，单链表，双向链表1.1RemoveDuplicatesfromSortedArray描述Givenasortedarray,removetheduplicatesinplacesuchthateachelementappearonlyonceandreturnthenewlength.Donotallocateextraspaceforanotherarray,youmustdothisinplacewithconstantmemory.Forexample,Giveninputarr

2、ayA=[1,1,2],Yourfunctionshouldreturnlength=2,andAisnow[1,2].分析无代码：publicclassSolution{publicintremoveDuplicates(int[]A){if(A==null

3、

4、A.length==0)return0;intindex=0;for(inti=1;i

5、.2RemoveDuplicatesfromSortedArrayII描述Followupfor”RemoveDuplicates”:Whatifduplicatesareallowedatmosttwice?Forexample,GivensortedarrayA=[1,1,1,2,2,3],Yourfunctionshouldreturnlength=5,andAisnow[1,1,2,2,3]分析可以加一个变量来记录重复元素的个数能很好的解决问题。由于此题已经是排序的了，如果是没有排序的，可以使用hashmap来求元素的个数。代码publicclassSol

6、ution{publicintremoveDuplicates(int[]A){if(A==null

7、

8、A.length==0)return0;intindex=0,cnt=0;for(inti=1;i

9、tedArray描述Supposeasortedarrayisrotatedatsomepivotunknowntoyoubeforehand.(i.e.,0124567mightbecome4567012).Youaregivenatargetvaluetosearch.Iffoundinthearrayreturnitsindex,otherwisereturn-1.Youmayassumenoduplicateexistsinthearray.分析二分查找，此题要特别注意边界值。此题的边界比较多。（1）mid的位置判定，mid可能在左边区域，也可能在右边区域

10、，需求通过（A[mid]与A[first]大小关系进行判定）（2）在判定边界时，要注意考虑大于，小于，等于三种情况，在写代码时，本题我开始忘记了一个等号，如代码中标红的地方。（3）二分的思想是一步一步将区域缩小，并且要充分考虑缩小的正确性，不能放松对边界的警惕（即要注意等于的情况）。如图所示：FirstmidlastFirstmidlast要注意mid落在哪个区域，通过A[mid]与A[first]大小比较可以确定，同时要注意边界条件的判断，当A[mid]==A[first]应该是将其归类A[mid]>A[first]的情况。代码publicintsearch(i

11、nt[]A,inttarget){if(A==null

12、

13、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]&&target<=A[last]){first

14、=mid+