Leetcode数组类题目总结（Java版本）精品资料.docx

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 memory.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;i<A.length;i+) if(Aindex!=Ai) A+index=Ai; return index+1; 相关题：Remove Duplicates 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分析可以加一个变量来记录重复元素的个数能很好的解决问题。由于此题已经是排序的了，如果是没有排序的，可以使用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;i<A.length;i+) if(Aindex!=Ai) A+index=Ai; cnt=0; else if(Aindex=Ai&&cnt<1) A+index=Ai; cnt+; return index+1; 相关题扩展该题到可重复n次的场景，只需要将cnt的上限设为<n-1即可。1.3 Search in Rotated Sorted Array描述Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.分析二分查找，此题要特别注意边界值。此题的边界比较多。（1） mid的位置判定，mid可能在左边区域，也可能在右边区域，需求通过（Amid与Afirst大小关系进行判定）（2） 在判定边界时，要注意考虑大于，小于，等于三种情况，在写代码时，本题我开始忘记了一个等号，如代码中标红的地方。（3） 二分的思想是一步一步将区域缩小，并且要充分考虑缩小的正确性，不能放松对边界的警惕（即要注意等于的情况）。如图所示：FirstmidlastFirstmidlast要注意mid落在哪个区域，通过Amid与Afirst大小比较可以确定，同时要注意边界条件的判断，当Amid=Afirst应该是将其归类Amid>Afirst的情况。代码public int search(int A, int target) if(A=null|A.length=0) return -1; int first=0,last=A.length-1; while(first<=last) int mid=(first+last)/2; if(Amid=target) return mid; else if(Amid>=Afirst) if(target>=Afirst&&target<Amid) last=mid-1; else first=mid+1; else if(target>Amid&&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 ”Search 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 public boolean search(int A, int target) if(A=null|A.length=0) return false; int first=0,last=A.length-1; while(first<=last) int mid=(first+last)/2; if(Amid=target) return true; else if(Amid>Afirst) if(target>=Afirst&&target<Amid) last=mid-1; else first=mid+1; else if(Amid<Afirst) if(target>Amid&&target<=Alast) first=mid+1; else last=mid-1; else if(Afirst=target) return true; else first+; return false; 相关题目1.3 Search in Rotated Sorted Array1.5 Median of Two Sorted Arrays描述There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(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个数，如果Ak/2=Bk/2 return Ak/2Ak/2>Bk/2 递归找k-k/2个数，且b的start位置为k/2+1Ak/2<Bk/2 同样递归找k-k/2,且a的start位置为k/2+1同时要注意如果两个数组长度悬殊太大，那么段数组可能不存在第k/2个元素，因此这是的K为short.length。此题的边界条件判断比较繁琐，当k=1时还需要单独判断，这个在考虑的时候没考虑到是在用例测试的时候发现的问题。代码public class Solution public double findMedianSortedArrays(int A, int B) int lena=A.length; int lenb=B.length; int len=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 return findMedianCore(A,B,0,lena-1,0,lenb-1,len/2+1); public double findMedianCore(int A,int B,int astart,int aend,int bstart,int bend,int k)int lena=aend-astart+1;int lenb=bend-bstart+1;/ the length of a is always smaller than the length of bif(lena>lenb)return findMedianCore(B,A,bstart,bend,astart,aend,k);if(lena<=0)return Bbstart+k-1;if(k=1)return Aastart>Bbstart?Bbstart:Aastart;int pa=k/2>lena?lena:k/2;int pb=k-pa;if(Aastart+pa-1=Bbstart+pb-1)return Aastart+pa-1;else if(Aastart+pa-1>Bbstart+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 Sequence描述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)因此不能排序。因此想到用hash。考虑数组当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=null) return 0; HashMap<Integer,Boolean> set=new HashMap<Integer,Boolean>(); for(int i=0;i<num.length;i+) set.put(numi,false); int max=0; /traversal Iterator<Entry<Integer,Boolean>> it=set.entrySet().iterator(); while(it.hasNext() Entry<Integer,Boolean> tem=it.next(); if(tem.getValue()=true) continue; int key=tem.getKey(); int cnt=1; tem.setValue(true); while(set.get(-key)!=null) cnt+; set.put(key,true); key=tem.getKey(); while(set.get(+key)!=null) cnt+; set.put(key,true); max=max>cnt?max:cnt; return max; 但是这个方法过于繁琐，我后来看了我最开始写的代码，发现我的处理方式是修改完以后每次遍历之前另外使用it.iterator();重新获取遍历对象。代码2public class Solution public int longestConsecutive(int num) if(num=null) return 0; HashSet<Integer> set=new HashSet<Integer>(); for(int i=0;i<num.length;i+) set.add(numi); Iterator<Integer> 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(count>max) 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 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(n2)复杂度方法2：哈希，很简单。方法3：先排序再夹逼，但是顺序乱了index也乱了，因此不好。最终采用方法2的思路。代码public class Solution public int twoSum(int numbers, int target) /<number,index> HashMap<Integer,Integer> map=new HashMap<Integer,Integer>(); for(int i=0;i<numbers.length;i+) map.put(numbersi,i); int index1=0,index2=0; for(int i=0;i<numbers.length;i+) index1=i; int find=target-numbersindex1; if(map.get(find)!=null&&map.get(find)!=index1) index2=map.get(find); break; int res=new int2; res0=index1<index2?index1+1:index2+1; res1=index1>index2?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 the 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的夹逼方法，先对数组进行排序。然后两层循环，第一层遍历每个元素，然后找到后面数组中两个元素和等于该元素。但是要考虑去重复的问题。在第二层循环里，碰到相同元素就继续向前。第一层循环碰到相同元素也继续向前，这样可以去重复。代码public class Solution public List<List<Integer>> threeSum(int num) List<List<Integer>> res=new ArrayList<List<Integer>>(); if(num=null|num.length=0) return res; Arrays.sort(num);/from small to big num for(int i=0;i<num.length;i+) ArrayList<Integer> sub=new ArrayList<Integer>(); if(i>0&&numi=numi-1) continue; int n1=numi; int sum=-n1; int p=i+1,q=num.length-1; while(p<q) if(numq+nump=sum) sub.add(n1); sub.add(nump); sub.add(numq); res.add(ArrayList<Integer>)sub.clone(); sub=new ArrayList<Integer>(); while(p+1<q&&nump+1=nump) p+; p+; while(q-1>p&&numq-1=numq) q-;q-; else if(numq+nump>sum)q-; else p+; return res; 相关题目3Sum，1.83Sum，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.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; int res_res=Integer.MAX_VALUE; for(int i=0;i<num.length;i+) if(i>0&&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(p<q) if(numq+nump=sum) return target; else if(numq+nump>sum) int ab=Math.abs(numq+nump+n1-target); if(sub>ab)sub=ab; res_sub=numq+nump+n1; q-; elseint ab=Math.abs(numq+nump+n1-target);if(sub>ab) sub=ab; res_sub=numq+nump+n1; p+; if(res>sub) 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 which 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的思路，该3Sum的代码使得能处理任意target值（3Sum原本只能处理0值）。然后在外面加一层循环即可。代码public class Solution public List<List<Integer>> threeSum(int num,int target,int start) List<List<Integer>> res=new ArrayList<List<Integer>>(); if(num=null|num.length=0) return res; for(int i=start;i<num.length;i+) ArrayList<Integer> sub=new ArrayList<Integer>(); if(i>start&&numi=numi-1) continue; int n1=numi; int sum=target-n1; int p=i+1,q=num.length-1; while(p<q) if(numq+nump=sum) sub.add(n1); sub.add(nump); sub.add(numq); res.add(ArrayList<Integer>)sub.clone(); sub=new ArrayList<Integer>(); while(p+1<q&&nump+1=nump) p+; p+; while(q-1>p&&numq-1=numq) q-;q-;else if(numq+nump>sum)q-; else p+; return res; public List<List<Integer>> fourSum(int num, int target) List<List<Integer>> res=new ArrayList<List<Integer>>(); if(num=null|num.length=0) return res; Arrays.sort(num);/from small to big num for(int i=0;i<num.length;i+) if(i>0&&numi=numi-1) continue; int tem=numi; List<List<Integer>> half=threeSum(num,target-tem,i+1); for(int j=0;j<half.size();j+) half.get(j).add(0,tem); res.addAll(half); return res; 相关题目3Sum，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;q<A.length;q+) i