LeetCode题解-C++文档类资源

该文档为《LeetCode题解》，程序员面试必备。主要是数据结构方面的知识，包括：数组、链表、栈、队列、树、图、查找、排序、动态规划以及贪心算法。包含题目130道左右，每道题目都给了不同的解法，方便大家面试前练练手感~~~蟹蟹
目录3.3 String to Integer(atoi585.1.5 Binary Tree Level or3.4 Add Binary59der traversal il23.5 Longest Palindromic Substring. 605.1.6 Binary Tree Zigzag3.6 Regular Expression Matching. 64Level order traversal3.7 Wildcard Matching5.1.7 Recover Binary Search3.8 Longest Common Prefix67Tree963.9 Valid Number685.1.8 Same tree983. 10 Integer to roman705.1.9 Symmetric Tree93.11 Roman to Integer715.1.10 Balanced Binary Tree.. 1003. 12 Count and say725.1.11 Flatten Binary Tree to3.13 Anagrams...........73Linked list1013. 14 Simplify Path745.1.12 Populating next Right3.15 Length of last Word75Pointers in each node第4章栈和队列7710341栈52二叉树的构建1054.1.1 Valid Parentheses..,. 775.2.1 Construct Binary Tree4.1.2 Longest Valid Parenfrom preorder andtheses78order traversal1054.1.3 Largest Rectangle in5.2.2 Construct Binary TreeHistogram80from Inorder and pos4.1.4 Evaluate reverse poltorder traversal,.,,.106ish notation5.3二叉查找树1074.2队列835.3.1 Unique Binary Search第5章树Trees1078451二又树的遍历845.3.2 Unique Binary Search5.1.1 Binary Tree PreorderTrees il108ravers845.3. 3 Validate Binary Search5.1.2 Binary Tree InorderTree109Traversal865.3.4 Convert Sorted Array5.1.3 Binary Tree Postorderto binary Search Tree. 110Traversal885.3.5 Convert Sorted list to5.1.4 Binary Tree Level OrBinary Search Tree111der traversal915.4又树的递归113目录5.4.1 Minimum Depth of Bi8.3.1 next_permutation.. 14nary Tre113832重新实现 next_permu5.4.2 Maximum Depth of Bitation141nary tree1148.33递归1425.4.3 Path Sum1158.4 PermutationsⅡ14354.4 Path sunⅡ1168.4.1 next_permutation...1435.4.5 Binary Tree Maximum842重新实现 next_permuPath Sun........117tation1435.4.6 Populating Next Right84.3递归143Pointers in each node 1188.5 Combinations ,,,,,,, 1455.4.7 Sum root to leaf num85.1递归145bers1208.52迭代1468.6 Letter Combinations of a第6章排序121Phone number1466.1 Merge Sorted array86.1递归1476.2 Merge Two Sorted Lists122862迭代1486. 3 Merge k Sorted Lists.1226.4 Insertion Sort list123第9章广度优先搜索1496.5 Sort list1249.1 Word Ladder1496.6 First Missing positive1269.2 Word Ladder il1516.7 Sort Colors....1279.3 Surrounded Regions15394小结154第7章查找130941适用场景1547. 1 Search for a range130942思考的步骤1547.2 Search Insert Position...,., 131943代码模板1557.3 Search a 2D Matrix132第10章深度优先搜索160第8章暴力枚举法13410. 1 Palindrome Partitioning1608.1 Subsets...,,,,,,.....13410.2 Unique Paths16381.1递归13410.21深搜16381.2迭代13610.22备忘录法1638.2 Subsets il13710.23动规16482.1递归13710.24数学公式16582.2迭代14010.3 Unique Paths II1668.3 Permutations14110.31备忘录法166目录0.3.2动规16713.4 Maximal Rectangle19610.4 N-Queens167 13.5 Best Time to Buy and Sell Stock10.5N- QueensⅡ170II19710.6 Restore ip addresses17113.6 Interleaving String19810.7 Combination Sum17213.7 Scramble String ....... 2010. 8 Combination sum il17413. 8 Minimum path Sum20510.9 Generate Parentheses17513.9 edit distance20810.10 Sudoku solver17613.10 Decode ways21010.11 Word Search17813. 11 Distinct Subsequences21110.12小结13.12 Word Break.21210.121适用场景...18013.13 Word Break il21310.122思考的步骤.18010.12.3代码模板181第14章图21510.124深搜与回溯法的区别.182141 Clone Graph...21510.12.5深搜与递归的区别182第15章细节实现题218第11章分治法18315. 1 Reverse Integer ........ 21811.1 Pow(x, n)18315.2 Palindrome number21911. 2 Sqrt(x)18415.3 Insert Interval,,,.,.,.,22015.4 Merge Intervals221第12章贪心法18515.5 Minimum Window Substring.. 22212.1 Jump Game18515.6 Multiply strings22412.2 Jump Game II18615.7 Substring with Concatenation12.3 Best Time to Buy and Sell Stock 188of all words22712.4 Best Time to Buy and Sell Stock II 18915.8 Pascals Triangle22812.5 Longest Substring Without Re15.9 Pascals Triangle Il229peating Characters19015.10 Spiral matrix23012.6 Container With Most Water19115.11 Spiral Matrix II231第13章动态规划19215.12 Zig Zag Conversion23313. 1 Triangle19215.13 Divide Two integers23413.2 Maximum Subarray19315. 14 Text Justification23513.3 Palindrome Partitioning II19515.15 Max Points on a line237目录第1章编程技巧在判断两个浮点数a和b是否相等时,不要用a=b,应该判断二者之差的绝对值fabs(a-b)是否小于某个阀值,例如1e-9。判断一个整数是否是为奇数,用x%2!=0,不要用x%2==1,因为ⅹ可能是负数。用char的值作为数组下标(例如,统计字符串中每个字符出现的次数),要考虑到char可能是负数。有的人考虑到了,先强制转型为 unsigned int再用作下标,这仍然是错的。正确的做法是,先强制转型为 unsigned char,再用作下标。这涉及C++整型提升的规则,就不详述了。以下是关于STL使用技巧的,很多条款来自《 Effective stla》这本书。vector和 string优先于动态分配的数组首先,在性能上,由于 vector能够保证连续内存,因此一旦分配了后,它的性能跟原始数组相当其次,如果用new,意味着你要确保后面进行了 delete,一旦忘记了,就会出现BUG且这样需要都写一行 delete,代码不够短;再次,声明多维数组的话,只能一个一个new,例如int** ary new int*row_numfor(int i=0; i< row num; ++1)ary [i] = new int [col_num用 vector的话一行代码搞定,vector<vector<int>>ary(row_ num, vector<int>(col_ num, 0))使用 reserve来避免不必要的重新分配第2章线性表这类题目考察线性表的操作,例如,数组,单链表,双向链表等。2.1数组2.1.1 Remove Duplicates from Sorted array描述Given a sorted array, remove the duplicates in place such that each element appear onlyonce and return the new lenDo not allocate extra space for another array, you must do this in place with constant memFor example, Given input array A=[1, 1, 2Your function should return length= 2, and a is now [1, 2]分析无代码1/ Leet Code, Remove Duplicates from Sorted Array/时间复杂度0(n),空间复杂度0(1)class Solution tpublic:int removeDuplicates(int A[], int n)tif (n==o return oint index = ofor (int i =1:i<n: i++iif (aindex]!=ali])A[++index]=Alireturn index 121数组3代码2//LeetCode, Remove Duplicates from Sorted Array/使用STL,时间复杂度0(n),空间复杂度0(1)class Solution tpublicint removeDuplicates (int A[, int n)treturn distance(A, unique(a, A +n))代码3/ Leet Code, Remove Duplicates from Sorted Array//使用STL,时间复杂度0(n),空间复杂度0(1)class Solution Ipublicint removeDuplicates(int A[l, int n)treturn removeDuplicates(A, A+n,A)-Atemplate<typename InIt, typename OutIt>OutIt removeDuplicates(InIt first, InIt last, OutIt output)twhile (first ! last)[output++first upper_bound (first, last, *firsttput相关题目Remove Duplicates from Sorted Array II,见§2.1.22.1.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, 34第2章线性表分析加一个变量记录一下元素出现的次数即可。这题因为是已经排序的数组,所以一个变量即可解决。如果是没有排序的数组,则需要引入一个 hashmap来记录出现次数。代码/ Leet Code, Remove Duplicates from Sorted Array II/时间复杂度0(n),空间复杂度0(1)//@authorhex108(https://github.com/hex108)lass Solution fpublic:int removeDuplicates(int A[, int n)tf (n <=2 retnt ind2for (int i =2:i< n: i++)ilf (a[i] ! A lindex -2]A Lindex++]=Ali]return index代码2下面是一个更简洁的版本。上面的代码略长,不过扩展性好一些,例如将 occur<2改为occur<3,就变成了允许重复最多3次/ Leet Code, Remove Duplicates from Sorted Array II7/@author虞航仲(http://weibo.com/u/1666779725)/时间复杂度0(n),空间复杂度0(1)class Solution ipublicint removeDuplicates(int A[], int n)tint index = ofor (int i =0;i<n: ++i)i(i>0&&i<n-1&&A[i]==A[i-1]&&A[i]==A[i+1])ontinueA [index++]=Alireturn index相关题目Remove Duplicates from Sorted Array,见§211