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

最新版本的leetcode题解，包含目前leetcode网站上几乎所有题目的代码解析，对刷算法题库有很大帮助。
目录3.4 Add binary605.1.5 Binary Tree Level Or-3.5 Longest Palindromic Substring. 61der traversal il933.6 Regular Expression Matching655.1.6 Binary Tree Zigzag3.7 Wildcard MatchingLevel Order traversal. 953.8 Longest Common Prefix685.1.7 Recover Binary Search3. 9 Valid Number69Tree973.10 Integer to roman715.1. 8 Same tree3. 11 Roman to Integer2乃5.1.9 Symmetric Tree1003.12 Count and Say5.1.10 Balanced Binary Tree.. 1013. 13 Anagrams..745.1.11 Flatten Binary Tree to3. 14 Simplify PathLinked List1023. 15 Length of Last Word765.1. 12 Populating Next RightPointers in each node ii 104第4章栈和队列7852二叉树的构建1064.1栈785.2.1 Construct Binary Tree4Valid Parentheses78from Preorder and In4.1.2 Longest valid Parenorder traversa106theses75.2.2 Construct Binary Tree4.1.3 Largest Rectangle infrom Inorder and posHistogram8torder Traversal1074.14 Evaluate reverse pol-53二叉查找树108ish notation835.3. 1 Unique Binary Search4,2队列84Trees1085.3.2 Unique Binary Search第5章树855.1二叉树的遍历855.3.3 Validate Binary Search5.1.1 Binary Tree PreorderTreeTraversal855.3.4 Convert Sorted array to5.1.2 Binary Tree InorderBinary Search TreeTraversal875.3.5 Convert Sorted List to5.1. 3 Binary Tree PostorderBinary search tree11Traversal8954二叉树的递归.1145. 1. 4 Binary Tree Level Or5.4.1 Minimum Depth of Bider traversal)2nary lree.114目录5.4.2 Maximum Depth of Bi8.32重新实现 next permunary Tree115tation1415.4.3 Path Sum116833递归.1425.4 4 Path Sum il1178.4 Permutations li1435.4.5 Binary Tree Maximum8.4.1 next permutation(... 143Path Suum118842重新实现 next permu5.4.6 Populating Next Righttation143Pointers in Each Node. 11984.3递归1435.4.7 Sum Root to Leaf Num8.5 Combinations145bers21851递归145852迭代146第6章排序1228.6 Letter Combinations of a phone6.1 Merge Sorted Array122umber1466.2 Merge Two Sorted Lists..... 12386.1递归1476.3 Merge k Sorted Lists123862迭代1486.4 Insertion Sort List124第9章广度优先搜索1496.5 Sort list1259.1 Word Ladder.1496.6 First Missing Positive1269.2 Word Ladder il1516.7 Sort Colors1279. 3 Surrounded regions153第7章查找94小结15513094.1适用场景1557.1 Search for a range130942思考的步骤1557.2 Search Insert Position.13194.3代码模板1567. 3 Search a 2D Matrix132第10章深度优先搜索161第8章暴力枚举法13410.1 Palindrome Partitioning..1618.1 Subsets13410.2 Unique Paths1648.1.1递归13410.2.1深搜1648.1.2迭代13610.22备忘录法.1648.2 Subsets il13710.23动规165821递归1371024数学公式166822迭代.14010.3 Unique Paths Il1678. 3 Permutations1410.3.1备忘录法1678.3.1 next permutation14110.3.2动规.168目录10.4 N-Queens16813.4 Maximal rectangle19810.5 N-Queens II17113.5 Best Time to Buy and Sell Stock10.6 Restore ip addresses172.19910.7 Combination Sum17313.6 Interleaving String10.8 Combination Sum Il17413.7 Scramble String20210.9 Generate Parentheses.17613. 8 Minimum Path Sum20710.10 Sudoku solver17713.9 Edit Distance20910.11 Word Search.17913. 10 Decode Ways.21110.12小结18013. 11 Distinct Subsequences21210.12.1适用场景18013. 12 Word Break21310.122思考的步骤18013 13 Word Break il21510.12.3代码模板182第14章图21710.12.4深拽与回溯法的区别.18314. 1 Clone Graph21710.12.5深搜与递归的区别..183第15章细节实现题220第11章分治法18415.1 Reverse Integer2201.1 Pow(x, n).18415.2 Palindrome Number.22111. 2 Sqrt(x)18515.3 Insert Interval222第12章贪心法18615.4 Merge Intervals22312.1 Jump game18615.5 Minimum Window Substring.. 22412.2 Jump game Il18715.6 Multiply Strings22612.3 Best Time to buy and sell stock 18915.7 Substring with Concatenation12. 4 Best Time to buy and sell stock l190of all words12. 5 Longest Substring Without re15.8 Pascal,s Triangle230peating Characters1915.9 Pascals Triangle Il23112.6 Container With Most Water.. 192 15.10 Spiral Matrix23215.11 Spiral matrix II233第13章动态规划19415.12 ZigZag Conversion23513. 1 Triangle19415.13 Divide Two Integers23613.2 Maximum Subarray19515. 14 Text Justification23713.3 Palindrome Partitioning II19715.15 Max Points on a line239目录第1章编程技巧在判断两个浮点数a和b是否相等时,不要用a=-b,应该判断二者之差的绝对值fabs(a-b)是否小于某个阀值,例如1e-9。判断一个整数是否是为奇数,用x%2!=0,不要用x%2==1,因为x可能是负数。用char的值作为数组下标(例如,统计字符串中每个字符出现的次数),要考虑到char可能是负数。有的人考虑到了,先强制转型为 unsigned int再用作下标,这仍然是错的。正确的做法是,先强制转型为 unsigned char,再用作下标。这涉及C++整型提升的规则,就不详述了。以下是关于STL使用技巧的,很多条款来自《 EffectiⅤ ve StL》这本书。vector和 string优先于动态分配的数组首先,在性能上,由于 vector能够保证连续内存,因此一旦分配了后,它的性能跟原始数组相当其次,如果用new,意味着你要确保后面进行了 delete,旦忘记了,就会出现BUG,且这样需要都写一行 delete,代码不够短再次,声明多维数组的话,只能一个一个new,例如:int** ary = new int*[row_num];for(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章线性表这类题目考察线性表的操作,例如,数组,单链表,双向链表等。21数组2.1.1 Remove Duplicates from Sorted array描述Given a sorted array, remove the duplicates in place such that each element appear only onceand return the new lengthDo not allocate extra space for another array, you must do this in place with constant memoryFor example, Given input array A =[1, 1, 2Your function should return length=2, and a is now [1, 2]分析无代码1/ LeetCode, Remove Duplicates from Sorted Array/时间复杂度0(n),空间复杂度0(1)class Solution tublicint removeDuplicates(int A[], int n)tlf (n==o return oint index =0:for (int i =1:i <n: i++iif (Alindex ! alidA[++index]= Alireturn index 12.1数组代码2// Leet Code, Remove Duplicates from Sorted Array//使用STL,时间复杂度0(n),空间复杂度0(1)class Solution ipublicint removeDuplicates(int A[, int n)treturn distance(A, unique(A, A n))代码3/ LeetCode, Remove Duplicates from Sorted Array/使用STL,时间复杂度0(n),空间复杂度0(1)lass Solution fublicint removeDuplicates (int A[], int n)treturn removeDuplicates(A, A +n, A)-A;template<typename InIt, typename outit>OutIt removeDuplicates(InIt first, InIt last, OutIt output)thile (first last)i*output++ = *firstfirst upper_bound(first, last, *firstreturn output相关题目Remove duplicates from Sorted Array Il,见§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, 3分析加一个变量记录一下元素出现的次数即可。这题因为是已经排序的数组,所以一个变量即可解决。如果是没有排序的数组,则需要引入一个 hashmap来记录出现次数4第2章线性表代码1// Leet Code, Remove Duplicates from Sorted Array II/时间复杂度0(n),空间复杂度0(1)//qauthorhex108(https://github.com/hex108)class Solution tublicint removeDuplicates (int A[], int n)tlf (n <=2 return nint index =2for (int i=2: i n: 1++)if (all] ! Alindex -2])A Lindex++]= Ali]return index;代码2下面是一个更简洁的版本。上面的代码略长,不过扩展性好一些,例如将 occur<2改为ocur<3,就变成了允许重复最多3次。//LeetCode, Remove Duplicates from Sorted Array II//@author虞航仲(http://weibo.com/u/1666779725)//时间复杂度0(n),空间复杂度0(1)class Solution ipublicint removeDuplicates(int A[, int n)tmt index = ofor (intif(i>0&&i<1&&A[i]==A[i-1]&&A[i]==A[i+1])continueA lindex++]=Alireturn index;相关题目Remove Duplicates from Sorted Array,见§2.1.12.1.3 Search in Rotated Sorted Array描述Suppose a sorted array is rotated at some pivot unknown to you beforehand