《Leetcode数组类题目总结（Java版本）精品资料.docx》由会员分享，可在线阅读，更多相关《Leetcode数组类题目总结（Java版本）精品资料.docx（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Leetcode151题目详解1 第一章线性表此类题目考察线性表的操作，例如数组，单链表，双向链表1.1 Remove Duplicates from Sorted Array描述Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not allocate extra space for another array, you must do this in place with constant memo
2、ry.For example, Given input array A = 1,1,2,Your function should return length = 2, and A is now 1,2.分析无代码：public class Solution public int removeDuplicates(int A) if(A=null|A.length=0) return 0; int index=0; for(int i=1;iA.length;i+) if(Aindex!=Ai) A+index=Ai; return index+1; 相关题：Remove Duplicates
3、from Sorted Array II 见1.21.2 Remove Duplicates from Sorted Array II 描述Follow up for ”Remove Duplicates”: What if duplicates are allowed at most twice?For example, Given sorted array A = 1,1,1,2,2,3,Your function should return length = 5, and A is now 1,1,2,2,3分析可以加一个变量来记录重复元素的个数能很好的解决问题。由于此题已经是排序的了，
4、如果是没有排序的，可以使用hashmap来求元素的个数。代码public class Solution public int removeDuplicates(int A) if(A=null|A.length=0) return 0; int index=0,cnt=0; for(int i=1;iA.length;i+) if(Aindex!=Ai) A+index=Ai; cnt=0; else if(Aindex=Ai&cnt1) A+index=Ai; cnt+; return index+1; 相关题扩展该题到可重复n次的场景，只需要将cnt的上限设为Afirst的情况。代码pub
5、lic int search(int A, int target) if(A=null|A.length=0) return -1; int first=0,last=A.length-1; while(first=Afirst) if(target=Afirst&targetAmid&target=Alast) first=mid+1; else last=mid-1; return -1; 相关题目Search in Rotated Sorted Array II，见 1.41.4 Search in Rotated Sorted Array II描述Follow up for ”Sear
6、ch in Rotated Sorted Array”: What if duplicates are allowed?Would this affect the run-time complexity? How and why?Write a function to determine if a given target is in the array.分析问题就出在边界上，即Amid=Afirst的情况，如果这样，那么无法确定mid的位置属于上题的图一还是图二。因此这时判断Afirst=target,如果不成立则first+缩小一个范围。代码public class Solution pu
7、blic boolean search(int A, int target) if(A=null|A.length=0) return false; int first=0,last=A.length-1; while(firstAfirst) if(target=Afirst&targetAmid) last=mid-1; else first=mid+1; else if(AmidAmid&targetBk/2 递归找k-k/2个数，且b的start位置为k/2+1Ak/2lenb)return findMedianCore(B,A,bstart,bend,astart,aend,k);i
8、f(lenaBbstart?Bbstart:Aastart;int pa=k/2lena?lena:k/2;int pb=k-pa;if(Aastart+pa-1=Bbstart+pb-1)return Aastart+pa-1;else if(Aastart+pa-1Bbstart+pb-1)return findMedianCore(A,B,astart,aend,bstart+pb,bend,k-pb);elsereturn findMedianCore(A,B,astart+pa,aend,bstart,bend,k-pa);相关题目无1.6 Longest Consecutive S
9、equence描述Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given 100, 4, 200, 1, 3, 2, The longest consecutive elements sequence is 1,2, 3, 4. Return its length: 4. Your algorithm should run in O(n) complexity.分析此题由于复杂度是O(n)因此不能排序。因此想到用ha
10、sh。考虑数组当hash但是由于题目中说是整型，因此不能用。所以使用HashSet解决。将所有的数放入集合中（已经去重）。取数，前后探索，记录连续的个数更新max。当set为空时返回的max即为最大值。本题在实验室发现一个问题，即你在遍历集合的时候修改集合会报错，java.util.ConcurrentModificationException，因此我采用了HashMap来做，value记录是否访问过。代码import java.util.Map.Entry;public class Solution public int longestConsecutive(int num) if(num=
11、null) return 0; HashMap set=new HashMap(); for(int i=0;inum.length;i+) set.put(numi,false); int max=0; /traversal IteratorEntry it=set.entrySet().iterator(); while(it.hasNext() Entry tem=it.next(); if(tem.getValue()=true) continue; int key=tem.getKey(); int cnt=1; tem.setValue(true); while(set.get(-
12、key)!=null) cnt+; set.put(key,true); key=tem.getKey(); while(set.get(+key)!=null) cnt+; set.put(key,true); max=maxcnt?max:cnt; return max; 但是这个方法过于繁琐，我后来看了我最开始写的代码，发现我的处理方式是修改完以后每次遍历之前另外使用it.iterator();重新获取遍历对象。代码2public class Solution public int longestConsecutive(int num) if(num=null) return 0; Ha
13、shSet set=new HashSet(); for(int i=0;inum.length;i+) set.add(numi); Iterator it=set.iterator(); int count=0; int max=0; while(it.hasNext() int a=it.next(); count+; set.remove(a); int tem=a; while(set.contains(+tem) count+; set.remove(tem); tem=a; while(set.contains(-tem) count+; set.remove(tem); if(
14、countmax) max=count; count=0; it=set.iterator(); return max; 这个代码写的时候我又犯了错误，即两个循环一个向前查找一个向后查找，向前查找完以后要将tem值重新回到中间位置再向后查找。1.7 Two Sum描述Given 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
15、they add up to the target, whereindex1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.You may assume that each input would have exactly one solution.Input: numbers=2, 7, 11, 15, target=9Output: index1=1, index2=2分析方法1：暴力，每两个元素都考虑到，这样就有O(n
16、2)复杂度方法2：哈希，很简单。方法3：先排序再夹逼，但是顺序乱了index也乱了，因此不好。最终采用方法2的思路。代码public class Solution public int twoSum(int numbers, int target) / HashMap map=new HashMap(); for(int i=0;inumbers.length;i+) map.put(numbersi,i); int index1=0,index2=0; for(int i=0;inumbers.length;i+) index1=i; int find=target-numbersindex
17、1; if(map.get(find)!=null&map.get(find)!=index1) index2=map.get(find); break; int res=new int2; res0=index1index2?index1+1:index2+1; return res; 相关题目3Sum，1.83Sum，1.94Sum，1.101.8 3Sum描述Given an array S of n integers, are there elements a,b,c in S such that a + b + c = 0? Find all unique triplets in t
18、he array which gives the sum of zero.Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a b c) The solution set must not contain duplicate triplets.For example, given array S = -1 0 1 2 -1 -4.A solution set is:(-1, 0, 1)(-1, -1, 2)分析利用two sum的夹逼方法，先对数组进行排序。然后两层循环，第一层遍历每个元素，然后找
19、到后面数组中两个元素和等于该元素。但是要考虑去重复的问题。在第二层循环里，碰到相同元素就继续向前。第一层循环碰到相同元素也继续向前，这样可以去重复。代码public class Solution public ListList threeSum(int num) ListList res=new ArrayListList(); if(num=null|num.length=0) return res; Arrays.sort(num);/from small to big num for(int i=0;inum.length;i+) ArrayList sub=new ArrayList(
20、); if(i0&numi=numi-1) continue; int n1=numi; int sum=-n1; int p=i+1,q=num.length-1; while(pq) if(numq+nump=sum) sub.add(n1); sub.add(nump); sub.add(numq); res.add(ArrayList)sub.clone(); sub=new ArrayList(); while(p+1p&numq-1=numq) q-;q-; else if(numq+numpsum)q-; else p+; return res; 相关题目3Sum，1.83Sum
21、，1.94Sum，1.101.9 3Sum Closest描述Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.For example, given array S = -1 2 1 -4, and target = 1.
22、The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).分析在3Sum的基础上改的代码，夹逼的思想不变。最后return的值是三个数的和而不是差距ab的值，这里要特别注意。如果差距为零就直接返回，否则就一直夹逼到不能夹逼为止。比较值取target-n1代码public class Solution public int threeSumClosest(int num, int target) Arrays.sort(num);/from small to big num int res=Integer.MAX_VALUE; in
23、t res_res=Integer.MAX_VALUE; for(int i=0;i0&numi=numi-1) continue; int n1=numi; int sum=target-n1;/near sum int p=i+1,q=num.length-1; int sub=Integer.MAX_VALUE; int res_sub=Integer.MAX_VALUE; while(psum) int ab=Math.abs(numq+nump+n1-target); if(subab)sub=ab; res_sub=numq+nump+n1; q-; elseint ab=Math
24、.abs(numq+nump+n1-target);if(subab) sub=ab; res_sub=numq+nump+n1; p+; if(ressub) res=sub;res_res=res_sub; return res_res; 相关题目3Sum，1.83Sum，1.94Sum，1.101.10 4Sum描述Given an array S of n integers, are there elements a,b,c, and d in S such that a+b+c+d = target?Find all unique quadruplets in the array w
25、hich gives the sum of target.Note: Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a b c d) The solution set must not contain duplicate quadruplets.For example, given array S = 1 0 -1 0 -2 2, and target = 0.A solution set is:(-1,0, 0, 1)(-2, -1, 1, 2)(-2,0, 0, 2)分析本题直接使用3Sum
26、的思路，该3Sum的代码使得能处理任意target值（3Sum原本只能处理0值）。然后在外面加一层循环即可。代码public class Solution public ListList threeSum(int num,int target,int start) ListList res=new ArrayListList(); if(num=null|num.length=0) return res; for(int i=start;inum.length;i+) ArrayList sub=new ArrayList(); if(istart&numi=numi-1) continue;
27、 int n1=numi; int sum=target-n1; int p=i+1,q=num.length-1; while(pq) if(numq+nump=sum) sub.add(n1); sub.add(nump); sub.add(numq); res.add(ArrayList)sub.clone(); sub=new ArrayList(); while(p+1p&numq-1=numq) q-;q-;else if(numq+numpsum)q-; else p+; return res; public ListList fourSum(int num, int targe
28、t) ListList res=new ArrayListList(); if(num=null|num.length=0) return res; Arrays.sort(num);/from small to big num for(int i=0;i0&numi=numi-1) continue; int tem=numi; ListList half=threeSum(num,target-tem,i+1); for(int j=0;jhalf.size();j+) half.get(j).add(0,tem); res.addAll(half); return res; 相关题目3S
29、um，1.83Sum，1.94Sum，1.101.11 Remove Element描述Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesnt matter what you leave beyond the new length.分析无代码public class Solution public int removeElement(int A, int elem) if(A=null|A.length=0) return 0; int p=0; for(int q=0;qA.length;q+) i