leetcode-solution

1. Introduction2. Arrayi. Remove Elementii. Remove Duplicates from Sorted Arrayiii. Plus Oneiv. Pascal's Trianglev. Merge Sorted Arrayvi. Sumvii. Find Minimum in Rotated Sorted Arrayviii. Largest Rectangle in Histogramix. Maximal Rectanglex. Palindrome Numberxi. Search a 2D Matrixxii. Search for a Rangexiii. Search Insert Positionxiv. Find Peak Element3. Bit Manipulationi. Missing Numberii. Power of Twoiii. Number of 1 Bits4. Treei. Depth of Binary Treeii. Construct Binary Treeiii. Binary Tree Level Order Traversaliv. Symmetric Treev. Same Treevi. Balanced Binary Treevii. Path Sumviii. Binary Tree Depth Order Traversalix. Populating Next Right Pointers in Each Nodex. Convert Sorted List/Array to Binary Search Treexi. Path Sum IIxii. Flatten Binary Tree to Linked Listxiii. Validate Binary Search Treexiv. Recover Binary Search Treexv. Binary Tree Pathxvi. Sum Root to Leaf Numbers5. Dynamic Programmingi. Best Time To Buy And Sell Stockii. Unique Pathsiii. Maximum Subarrayiv. Climbing StairsTable of ContentsLeetCode题解2v. Trianglevi. Unique Binary Search Treesvii. Perfect Squares6. Backtrackingi. Combinationii. Subsetsiii. Permutation7. Greedyi. Jump Gameii. Gas Stationiii. Candyiv. Word Break8. Linked Listi. Linked List Cycleii. Remove Duplicates from Sorted Listiii. Merge Sorted Listsiv. Reverse Linked Listv. Swap Nodes in Pairsvi. Sort Listvii. Rotate Listviii. Reorder Listix. Partition Listx. Add Two Numbersxi. Copy List with Random Pointer9. Mathi. Reverse Integer10. Stringi. Add Binaryii. Basic Calculator IILeetCode题解3首先声明，我和张晓翀都不是算法牛人，确切的说应该是算法的门外汉，小白一个。所以我们为了撬开算法的大门，各自刷完了一遍LeetCode的题目，这其中碰到了很多困难，当然也少不了用了Google以及参考了别人的代码。做完一遍下来，陡然发现，很多题目还是忘记了，再次碰到又不知道如何下手，其实这就是典型的没有理解，掌握透。所以我们决定，应该好好的将自己做题的思路记录下来，一个知识点，自己能弄懂，写出来让大家都明白，同时能做到举一反三，触类旁通，那么在一定程度上面才算是真的掌握了。于是就有了现在准备开始的这本书：《LeetCode题解》，用来记录我们刷LeetCode题目时候的心酸历史。我们保证，书中的代码一定通过了当时LeetCode的测试，虽然后续可能因为LeetCode测试条件的改变导致某些解题无法通过，但我们会实时的跟进。编程语言使用C++，代码风格上面并没有强制的采用什么编码规范，毕竟是算法解题，只需要代码清晰易懂就可以了。我们准备按照LeetCode的题型分类来组织章节，譬如Array，Hash Table等，而对每个章节里面的题目，通常采用由易到难的方式进行说明。采用这种方式，能让我们在短时间内快速学习掌握某一类知识，同时也便于讲解说明。当然，除了LeetCode现有的题目，我们也希望在每个章节加入相关的扩展知识，这需要我们参考大量现有的算法书籍，鉴于个人精力时间有限，可能并不会完全实施。最后，我们非常欢迎大家的反馈（前提是有人看我们的东西）。如果你有任何的意见建议，欢迎在Github的issue里面提出，或者直接与我们联系。陈心宇 [e-mail]张晓翀 [e-mail] [e-mail]前言Thanks ContributorMaintainerLeetCode题解4IntroductionArrayLeetCode题解5ArrayGiven 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.作为开胃菜，我当然选取了最容易的一道题目，在一个数组里面移除指定value，并且返回新的数组长度。这题唯一需要注意的地方在于 in place ，不能新建另一个数组。方法很简单，使用两个游标i，j，遍历数组，如果碰到了value，使用j记录位置，同时递增i，直到下一个非value出现，将此时i对应的值复制到j的位置上，增加j，重复上述过程直到遍历结束。这时候j就是新的数组长度。代码如下：class Solution {public: int removeElement(int A[], int n, int elem) { int i = 0; int j = 0; for(i = 0; i n; i++) { if(A[i] == elem) { continue; } A[j] = A[i]; j++; } return j; }};举一个最简单的例子，譬如数组为1，2，2，3，2，4，我们需要删除2，首先初始化i和j为0，指向第一个位置，因为第一个元素为1，所以A[0] = A[0]，i和j都加1，而第二个元素为2，我们递增i，直到碰到3，此时A[1] = A[3]，也就是3，递增i和j，这时候下一个元素又是2，递增i，直到碰到4，此时A[2] = A[5]，也就是4，再次递增i和j，这时候数组已经遍历完毕，结束。这时候j的值为3，刚好就是新的数组的长度。Remove ElementLeetCode题解6Remove ElementGiven a sorted array, remove the duplicates in place such that each element appear only onceand 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] ，我们仍然使用两个游标i和j来处理，假设现在i = j + 1，如果A[i] == A[j]，那么我们递增i，直到A[i] != A[j]，这时候我们再设置A[j + 1] =A[i]，同时递增i和j，重复上述过程直到遍历结束。代码如下：class Solution {public: int removeDuplicates(int A[], int n) { if(n == 0) { return 0; } int j = 0; for(int i = 1; i n; i++) { if(A[j] != A[i]) { A[++j] = A[i]; } } return j + 1; }};譬如一个数组为1，1，2，3，首先i = 1，j = 0，这时候A[i] = A[j]，于是递增i，碰到2，不等于1，此时设置A[j + 1] = A[i]，也就是A[1] = A[2]，递增i和j为3和1，这时候A[3] != A[1]，设置A[j + 1] = A[i]，也就是A[2] =A[3]，再次递增，遍历结束。这时候新的数组长度就为2 + 1，也就是3。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 ArrayRemove Duplicates from Sorted Array IILeetCode题解7Remove Duplicates from Sorted Array仍然是第一题的思路，但是我们需要用一个计数器来记录重复的次数，如果重复次数大于等于2，我们会按照第一题的方式处理，如果不是重复元素了，我们将计数器清零。代码如下：class Solution {public: int removeDuplicates(int A[], int n) { if(n == 0) { return 0; } int j = 0; int num = 0; for(int i = 1; i n; i++) { if(A[j] == A[i]) { num++; if(num 2) {