LeetCode全套详细题解

所需积分/C币:28 2018-12-27 22:37:42 1.51MB PDF

LeetCode详细题解,按照C++语言编写。该文档按照LeetCode的题型分类来组织章节,譬如Array,Hash Table等,而对每个章节里面的题目,通常采用由易到难的方式进行说明。
G=台能乖职 www.icebear.me V. Triangle vi. Unique Binary Search Trees ⅶi. Perfect Squares 6. Backtracking i. Combination i. Subsets iii. Permutation 7. Greed Jump Game li, Gas station iii Candy iV. Word Break 8. Linked list Linked List Cycle Remove Duplicates from Sorted List lll. Merge Sorted Lists i, Reverse linked list v. Swap Nodes in Pairs Sort list ⅶi. Rotate list vii. Reorder list ix. Partition list x Add Two numbers xi. Copy List with Random Pointer Math i. Reverse Integer 10. String Add Binary i. Basic calculator‖ 事务所,获取更多资料礼包 G=台能乖职 www.icebear.me 前言 首先声明,我和张晓翀都不是算法牛人,确切的说应该是算法的门外汉,小白一个。所以我们为了撬开算 法的大门,各自刷完了一逼 lLeetcode的题目,这其中碰到了很多困难,当然也少不了用了Goog以及参考 了别人的代码。 做完一遍下来,陡然发现,很多题目还是忘记了,再次碰到又不知道如何下手,其实这就是典型的没有理 解,掌握透。所以我们決定,应该好好的烀自己做题的思路记录下来,一个知识点,自己能弄憧,写出来 让大家都明白,同时能做到举一反三,舳类旁通,那么在一定程度上面扌算是真的掌握了。 于是就有了现在准各开始的这本书:《 Leetcode题解》,用来记录我们刷 LEeteσe题目时候的心酸历史。 我们保证,书中的代码一定通过了当时 Leetcode的测试,虽然后续可能因为 Leetcode测试条件的改变导致 某些解题无法通过,但我们会实时的跟进。 编程语霅使用C++,代码风格上面并没有强制的采用什厶编码规范,毕竟是算法解题,只需要代码清晰易 懂就可以了。 我们准备按照 Leetcode的题型分类来组织章节,譬如Ary, Hash table等,而对每个章节里面的题目,通 常采用由易到难的方式进行说明。釆用这种方式,能让我们在短时间內快速学习掌握某一类知识,同时也 便于讲解说明 当然,除了 Leetcode现有的题目,我们也希望在每个章节加入相关的扩展知识,这需要我们参考大量现有 的算法书籍,鉴于个人精力时间有限,可能并不会完全实施。 最后,我们非常欢迎大家的反馈(前提是有人看我们的东西)。如果你有任何的意见建议,欢迎在Ghub 的 issue!里面提出,或者直接与我们联系。 Thanks Contributor ·陈心宇collectchen@gmai.com ·张晓翀 xIzhang07@ gmail.con Maintainer SiddonTangsiddontang@gmail.com 事务所,获取更多资料礼包 Introduction G=台能乖职 www.icebear.me Array 事务所,获取更多资料礼 G=台能乖职 www.icebear.me 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 doesn't matter what you leave beyond the new length 作为开胃菜,我当然选取了最容易的一道题目,在一个数组里面移除指定vaue,并且返回新的数组长度。 这题唯一需要注意的地方在于 in place,不能新建另一个数组。 方法很简单,使用两个游标,j,逼历数組,如果碰到了vaue,使用记录位置,同吋递增i,直到下一个非 value出现,将此时i对应的值复制到的位置上,增加,重复上逑过程直到逼历结束。这时候就是新的数组 长度 代码如下 class solution public int removeElement (int A[, int n, int elem)t int⊥=o; Int J= for(工=0;i<n;i++) if(all] elem)I continue i AlJ= ALi return 举一个最简单的例子,譬如数组为1,2,2,3,2,4,我们需要删除2,首先初始化i利为0,指向第一个 位置,因为第一个元秦为1,所以A]=A,i和都加1,而第二个元秦为2,我们递增i,直到碰到3,此时 A]=A3],也就是3,递增,这时候下一个元素又是2,递增,直到碰到4,此时A[2]=A5],也就是 4,再次递增和,这时候数组已经通历完毕,结束。这时候j的值为3,刚好就是新的数组的长度 Remove element G=台能乖职 www.icebearme 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 这道题目与前一题 Remove element比较类似。但是在一个排序好的数组里面删除重复的元素。 首先我们需要知道,对于一个排好序的数组来说,A[N+1]>=A[N],我们仍然使用两个游标和来处 理,假设现在ⅰ=j+1,如果A==A],那么我们递增,直到A!=A],这时候我们再设置A+1]= A[],同时递增和,重复上述过程直到灜历结束。 代码如下: class solution public int removeDuplicates(int ALl, int n)t 0){ return o ant for(int +){ if(A[]]!=A[1]) A[++j]=A[1]; return 多资米 譬如一个数组为1,1,2,3,首先=1,j=0,这时侯A=A,于是增;碰到,不等于1,此时没懂 A[+1]=A叮,也就是A1]=A[2],递增和为3和1,这时候A[3]!=A[1],设置A+1]=A],也就是A[2]= A[3],再次逸增,遍历结束。这时侯新的数组长度就为2+1,也就是3。 Remove Duplicates from Sorted Array Il 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 紧接着上一题,同样是移除重复的元秦,但是可以允许最多两次重复元素存在。 Remove Duplicates from Sorted Array G=台能乖职 www.icebear.me 仍然是第一题的思路,但是我们需要用一个计数器来记录重复的次数,如果重复次数大于等于2,我们会按 照第一题的方式处理,如果不是重复元秦了,我们将计数器清帑。 代码如下: class Solution i public int removeDuplicates(int A[l, int n)i if(n==0){ return e Int J=0 int num 07 for(int i=1; i < n: i++)i if(al]]== Ali])i num++ 1f(num<2){ A[++j]=A[i] else I A[++j]=A[i] num return J+1, 事务所,获取更多资料礼 Remove Duplicates from Sorted Array 8 G=台能乖职 www.icebear.me Plus one Given a non-negative number represented as an array of digits, plus one to the number The digits are stored such that the most significant digit is at the head of the list 这道题目很简单,就是考的加法进位问题。直接上代码 class Solution t public vectorcint> plusone(vectorcint> &digits)i vector<int> res(digits, size,0) int sum =0 for(int i= digits. size (-1i i >=0;)i sum one digits] one = sum /10 res[i= sum; resinsert(res begin(, one)i return res 眼事务所,获取更多资料礼 Plus one G=台能乖职 www.icebearme Pascal's Triangle Given numROWS, generate the first numRows of Pascal's triangle For example, given num Rows = 5, Return [1,1 [1,2,1], [1,3,3,1 [1,4,6,41] 要得到一个帕斯卡三角,我们只需要找到规律即可。 第k层有k个元秦 ·每层第一个以及最后一个元素值为1 ·对于第k(k>2)层第n(n>1&&n<k)个元素Ak][m],Ak[n=Ak-1]n1]+Ak1]n 知道了上面的规律,就很好做了,我们使用一个二维数组来存储整个三角,代码如下 class Solution i public vector<vector<int>> generate(int numRows )i vectorsvector<int> vals vals. resize(numRows for( sli. resize(1 1) valsli][vals[i]. size ()-1]=1 for(int j=1ij< vals[i] size(-1ij++) vals][j] s[1-1][-1]+vals[1-1][j 更多资料剂 return vals Pascal's Triangle ll Given an index k, return the kth row of the Pascal's triangle For example, given k=3, Return [1, 3,3, 1 不同于上一题,这里我们仅仅需要得到的第k层的集合,但只能使用O(k)的空间。所以不能用前面二维数组 的方式,只能使用一位数组滚动计算。 Pascal's triangle 10

...展开详情
img
mishangyou
  • 分享达人

    成功上传6个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐