LeetCode题解

所需积分/C币:11 2017-01-21 16:57:25 837KB PDF
收藏 收藏
举报

本书包含了LeetCode Online Judge(http://leetcode.com/onlinejudge)所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写。 全书的代码使用C++11编写,并在LeetCode Online Judge上测试通过,适合面试准备或者ACM等算法竞赛的新手。 本书是开源的,GitHub 地址:https://github.com/soulmachine/leetcode
目录 3. 4 Add binary 61 5.1.5 Binary Tree Level Or 3.5 Longest Palindromic Substring. 62 der Traversal il 3.6 Regular Expression Matching.. 66 5.1.6 Binary Tree Zigzag 3.7 Wildcard Matching .67 Level Order Traversal. 96 3.8 Longest Common Prefix 5. 1. 7 Recover Binary Search 3.9 Valid Number 70 Tree 98 3.10 Integer to roman 72 5.1. 8 Same Tree 3.11 Roman to Integer 73 5.1.9 Symmetric Tree 100 3.12 Count and Say 74 5.1.10 Balanced Binary Tree.. 102 3. 13 Anagrams 75 5. 1. 11 Flatten Binary Tree to 3. 14 Simplify Pat 76 Linked List 3.15 Length of Last Word 1.12 popul 77 op ating Next rig Pointers in each node il 105 第4章栈和队列 5.2二叉树的构建 106 41栈 79 5.2.1 Construct Binary Tree 4.1.1 Valid parentheses 79 from preorder and In- 4.1.2 Longest Valid Paren order traversal 106 theses 80 5.2.2 Construct Binary Tree 4.1.3 Largest Rectangle in from inorder and pos Histogram 82 torder traversal 107 4. 1. 4 Evaluate Reverse Pol 5.3二叉查找树 .108 ish notation 84 5.3.1 Unique Binary Search 4.2队列 85 108 5.3.2 Unique Binary Search 第5章树 86 110 5.1二叉树的遍历 5.3.3 Validate Binary search 5.1.1 Binary Tree Preorder T 111 Traversal,.,,.... 86 5.3. 4 Convert Sorted array to 5.1.2B T norder Binary Search ti 112 Traversal .88 5.3.5 Convert Sorted list to 5.1. 3 Binary Tree Postorder Binary Search Tree 113 Traversal 9054二叉树的递归 114 5.1.4 Binary Tree Level Or- 5.4.1 Minimum Depth of Bi der traversal ..... 92 nary lree 115 目录 5.4.2 Maximum Depth of Bi- .3.2重新实现 next permu nary tree 116 tation 142 5.4.3 Path Sum 117 8.33递归 143 5.4 4 Path Sum ll 118 8. 4 Permutations Il 144 5.4.5 Binary Tree Maximum 8.4.1 next permutation Path sun....,,,.119 42重新实现 next permu- 5.4.6 Populating Next Right tation 144 Pointers in each node 120 843递归 144 5.4.7 Sum root to leaf num 8.5 Combination 146 bers 121 85.1递归 146 8.52迭代 147 第6章排序 123 8.6 Letter Combinations of a phone 6.1 Merge Sorted Array 123 Number 147 6.2 Merge Two Sorted Lists 124 861递归 148 6. 3 Merge k Sorted Lists 124 6.2迭代 149 6. 4 Insertion Sort List 125 第9章广度优先搜索 150 6.5 Sort List 126 9.1 Word Ladder 150 6.6 First Missing positive 127 9.2 Word Ladder il 154 6.7 Sort Colors .128 9.3 Surrounded Regions....... 162 第7章查找 131 94小结 94.1适用场景 164 7. 1 Search for a Range .131 94.2思考的步骤 7.2 Search Insert Position 132 94.3代码模板 7. 3 Search a 2D Matrix 133 第10章深度优先搜索 173 第8章暴力枚举法 135 10.1 Palindrome Partitioning 173 8.1 Subsets 135 10.2 Unique Paths 176 811递归 135 0.2.1深搜 176 8.12迭代 137 0.2.2备忘录法 176 8.2 Subsets il 138 10.2.3动规........17 821递归 .138 10.24数学公式 .178 8.2.2迭代 141 10.3U Paths ll 179 8.3 Permutations 142 10.31备忘录法 179 8.3.1 next permutation(... 142 10.3.2动规 180 目录 10.4 N-Queens 181 13. 4 Maximal rectangle 213 10.5 N-Queens II 184 13.5 Best Time to Buy and Sell Stock 10.6 Restore IP Addresses 186 II,,,.,...,,,,,,,.214 10.7 Combination sum 188 13.6 Interleaving String .215 10.8 Combination sum Il .189 13.7 Scramble string 217 10.9 Generate Parentheses 190 13. 8 Minimum path Sum 222 10.10 Sudoku solver .192 13.9 Edit distance 224 10.11 Word Search 193 13. 10 Decode Ways .226 10.12小结 195 13. 11 Distinct Subsequences 227 10.12.1适用场景 195 13. 12 Word Break 228 10.122思考的步骤 195 13 13 Word Break ll 230 10.12.3代码模板 197 第14章图 232 10.12.4深搜与回溯法的区别.197 14.1 Clone graph 232 10.12.5深搜与递归的区别..197 第15章细节实现题 235 第11章分治法 199 15.1 Reverse Integer 35 11.1Pow(x,n). 199 15.2 Palindrome Number 236 11. 2 Sqrt(x) 200 15. 3 Insert Interval 37 第12章贪心法 201 15.4 Merge Intervals 238 12.1 Jump game 201 15.5 Minimum Window Substring.. 239 12.2 Jump game II 202 15.6 Multiply strings 241 12.3 Best Time to Buy and Sell Stock 204 15.7 Substring with Concatenation 12.4 Best Time to buy and sell stock ll205 of all words 12.5 Longest Substring Without re 15.8 Pascals Triangle .245 peating Characters 206 15.9 Pascals Triangle Il ..246 12.6 Container With most Water 207 15.10 Spiral Matrix 247 15. 11 Spiral matrix II 248 第13章动态规划 209 15.12 Zig Zag Conversion 250 13.1 Triangle 209 15.13 Divide Two Integers .251 13.2 Maximum Subarray 210 15. 14 Text Justification 253 13.3 Palindrome Partitioning II 12 15.15 Max Points on a Line 255 目录 第1章 编程技巧 在判断两个浮点数a和b是否相等时,不要用a==b,应该判断二者之差的绝对值 fabs(a-b)是否小汙于某个阈值,例如1e-9。 判断一个整数是否是为奇数,用x%2!=0,不要用x%2==1,因为x可能是负 用char的值作为数组下标(例如,统计字符串中每个字符岀现的次数),要考虑到 char可能是负数。有的人考虑到了,先强制转型为 unsigned int再用作下标,这仍然是 错的。正确的做法是,先强制转型为υ nsigned char,再用作下标。这涉及C++整型提升 的规则,就不详述了。 以下是关于STL使用技巧的,很多条款来自《 Effective STL》这本书。 vector和 string优先于动态分配的数组 首先,在性能上,由于 vector能够保证连续内存,因此一旦分配孓后,它的性能跟 原始数组相 其次,如果用new,意味着你要确保后面进行孓 delete,一旦忘记孓,就会岀现BUG, 且这样需要都写一行 delete,代码不够短 再次,声明多维数组的话,只能一个一个new,例如 int** ary new int*[row_ num] for(inti=0;主 row num: ++i) ary [i] = new int [col_num] 用 vector的话一行代码搞定 vector<vector<int>> ary(row_num, vector<int>(col_num, 0)) 使用 reserve来避免不必要的重新分配 第2章 线性表 这类题目考察线性表的操作,例如,数组,单链表,双向链表等。 2数组 2.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] 分析 无 代码1 // Leet Code, Remove Duplicates from Sorted Array //时间复杂度0(n),空间复杂度0(1) public int removeDuplicates(vector<int>& nums)t f (nums empty o) return 0 t index o for (int i =1; i nums size o); i++)t if (nums [index] ! nums li]) nums [++index= nums li return index 1 2.1数组 代码2 // LeetCode, Remove Duplicates from Sorted Array /使用STL,时间复杂度0(n),空间复杂度0(1) class Solution i public int removeDuplicates(vector<int>& nums)t return distance(nums begin, unique(nums begin) nums, en nd(); 代码3 /使用STL,时间复杂度0(n),空间复杂度0(1) ay class Solution i public: int removeDuplicates(vector<int>& nums)t return distance (nums begin, removeDuplicates(nums begin(, nums end(, nums begin() template<typename InIt, typename OutIt> OutIt removeDuplicates(InIt first, InIt last, OutIt output)t hile (first last)[ * outpu七+=* first; first upper_bound(first, last, *first) return output 相关题目 Remove duplicates from Sorted Array II,见§2.1.2 2.1.2 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 分析 加一个变量记录一下元素出现的次数即可。这题因为是已经排序的数组,所以一个变量即可解 决。如果是没有排序的数组,则需要引入一个 hashmap来记录出现次数。 4 第2章线性表 代码1 // LeetCode, Remove Duplicates from Sorted Array II //时间复杂度0(n),空间复杂度0(1) //qauthorhex108(https://github.com/hex108) class Solution i public nt removeDuplicates(vector<int>& nums)t f (nums size<= 2 return nums size int index 2 for (int i =2: i< nums size(: i++)t f (nums [i] ! nums lindex -2]) nums [index++]= nums [i] retu Index, }: 代码2 下面是一个更简洁的版本。上面的代码略长,不过扩展性好一些,例如将。ccur<2改为 3,就变成了允许重复最多3次。 //Leet Code, Remove Duplicates from Sorted Array II @author虞航仲(http://weibo.com/u/1666779725) //时间复杂度0(n),空间复杂度0(1) class Solution i public int removeDuplicates(vector<int>& nums)t const int n nums size o int index =o for (int i =0;i<n: ++i) t f (i>0&& i n-1 & nums [ i] = nums [i -1]&& nums [i] = nums [i 1]) continue; nums [index++] = nums [i]; return index; 相关题目 Remove Duplicates from Sorted Array,见§2.1.1

...展开详情
一个资源只可评论一次,评论内容不能少于5个字
Vincent乐 不错的资源
2018-03-31
回复
一起玩哦 这本书很不错。
2017-04-25
回复
img
wangtianqt

关注 私信 TA的资源

上传资源赚积分,得勋章
最新推荐
LeetCode题解 版权受限,无法下载
1/127
LeetCode题解第1页
LeetCode题解第2页
LeetCode题解第3页
LeetCode题解第4页
LeetCode题解第5页
LeetCode题解第6页
LeetCode题解第7页
LeetCode题解第8页
LeetCode题解第9页
LeetCode题解第10页
LeetCode题解第11页
LeetCode题解第12页
LeetCode题解第13页
LeetCode题解第14页
LeetCode题解第15页
LeetCode题解第16页
LeetCode题解第17页
LeetCode题解第18页
LeetCode题解第19页
LeetCode题解第20页

试读已结束,剩余107页未读...

版权受限,无法下载