LeetCode解题总结

所需积分/C币:38 2018-10-09 16:02:19 9.62MB PDF
22
收藏 收藏
举报

LeetCode解题总结 1. 数组 1.1 从有序数组中删除重复元素 1.2 在排序数组被旋转后进行查找 1.3 寻找两个排序数组的中位数 1.4 最长连续序列 1.5 累加和 1.6 移除数组中指定值 1.7 下一个排列 1.8 第n个全排列 1.9 验证数独的正确性 1.10 容纳雨水的量 1.11 旋转图像 1.12 数字加1 1.13 爬楼梯 1.14 格雷码 1.15 设置矩阵的行列为0 1.16 加油站问题 1.17 分糖果 1.18 只出现一次的数 2. 单链表 2.1 单链表相加 2.2 指定位置反转单链表 2.3 依据给定值将链表重新排序 2.4 删除链表中重复元素 2.5 指定位置旋转链表 2.6 删除倒数第N个节点 2.7 成对交换链表元素 2.8 复制复杂链表 2.9 链表环相关问题 2.9.1 链表是否有环 2.9.2 链表环的入口 2.10 改变链表中的元素位置2.11 LRU Cache(设计题) 3. 字符串 3.1 判断字符串是否为回文 3.2 实现strStr() 3.3 字符串转为int(atoi) 3.4 二进制树相加 3.5 最长回文字符串 3.6 正则表达式匹配[hard] 3.7 正则匹配 3.8 最长公共前缀 3.9 验证字符串是否为数字 3.10 数字转为罗马数字 3.11 罗马数字到数字 3.12 Count and Say 3.13 变位词 3.14 简化系统路径 3.15 最后一个单词的长度 3.16 反转字符串中的单词 3.16.1 字符串前后和中间可能存在多个空格 3.16.2 不存在前后和中间的多余空格 3.17 一个编辑距离 4. 栈 4.1 验证括号的正确性 4.2 最长的正确括号表达式 4.3 柱状图中的最大矩形面积 4.4 计算逆波兰式的值 5. 树 5.1 二叉树的遍历 5.1.1 二叉树的前、中、后序遍历 5.1.2 二叉树的层序遍历 5.1.3 恢复二叉树[hard] 5.1.4 判断两棵树是否相等 5.1.5 判断二叉树是否为AVL树 5.1.6 将二叉树转为链表 5.1.7 二叉树添加指向右边节点的指针 5.1.8 树中节点的最小公共祖先 5.2 二叉树的构建5.3 二叉查找树 5.3.1 生成不重复的二叉查找树数目 5.3.2 验证是否为二叉查找树 5.3.3 将有序数组转为二叉树 5.3.4 将有序链表转为二叉树 5.4 二叉树的递归 5.4.1 二叉树的最大深度 5.4.2 二叉树的最小深度 5.4.3 路径和 5.4.4 满二叉树添加指向右边节点的指针 5.4.5 根节点到叶结点的所有路径代表的数字之和 6. 排序 6.1 合并两个有序数组到其中一个数组 6.2 合并两个有序链表 6.3 合并K个有序链表 6.4 使用插入排序来排序链表 6.5 归并排序排序链表 6.6 第一个缺少的正数 6.7 排序颜色 7. 查找 7.1 在排序数组中查找数出现的范围 7.2 在排序数组中查找给定值的插入位置 7.3 在二维排序数组中查找给定值 7.4 在旋转有序数组中查找最小值 7.4.1 数组无重复 7.4.2 数组有重复 7.5 在旋转排序数组中查找指定数字 8. 暴力枚举法 8.1 求集合的子集 8.2 集合的全排列 8.3 在指定树中选择进行全排列 8.4 电话上对应数字的字母组成的所有单词 9. 广度优先搜索 9.1 单词变换路径(Word Ladder) 9.1.1 是否存在变换路径 9.1.2 所有最短变换路径9.2 包围区域 10. 深度优先搜索 10.1 N皇后问题 10.2 恢复IP地址 10.3 集合元素之和 10.3.1 元素可以重复 10.3.2 元素不可重复 10.3.3 给定元素数目和元素范围 10.4 正确的括号对 10.5 解数独 10.6 单词搜索 10.7 小结 10.7.1 适用场景 10.7.2 思考步骤 10.7.3 代码模板 10.7.4 深搜与回溯、递归的区别 11. 分治法 11.1 实现pow(x, n) 11.2 Sqrt(x) 12. 贪心算法 12.1 跳台阶游戏 12.2 买卖股票的最佳时机 12.2.1 最多允许交易一次 12.2.2 可以交易任意多次 12.2.3 最多可以交易两次 12.2.4 可以交易任意多次 12.2.5 交易后需要停止一段时间 12.3 最长不含重复元素的子串 12.4 存放的最大水量 13. 动态规划 13.1 三角形从顶到底的最小路径和 13.2 最大连续子数组 13.3 字符串的所有子回文字符串 13.4 最长公共子序列问题 13.5 字符串的编辑距离 13.6 不同路径之和 13.6.1 无障碍13.6.2 有障碍 13.7 最大矩形面积 13.8 字符串
53二叉查找树 5.31生成不重复的二叉查找树数目 532验证是否为二叉查找树 533将有序数组转为二叉树 534将有序链表转为二叉树 54二叉树的递归 54.1二叉树的最大深度 54.2二叉树的最小深度 543路径和 544满二叉树添加指向右边节点的指针 54.5根节点到叶结点的所有路径代表的数字之和 排序 6.1合并两个有序数组到其中一个数组 62合并两个有序链表 63合并K个有序链表 64使用插入排序来排序链表 65归并排序排序链表 66第一个缺少的正数 67排序颜色 7.查找 7.1在排序数组中查找数出现的范围 7.2在排序数组中查找给定值的插入位置 7.3在二维排序数组中查找给定值 7.4在旋转有序数组中查找最小值 74.1数组无重复 7.4.2数组有重复 7.5在旋转排序数组中査找指定数字 8.暴力枚举法 8.1求集合的子集 82集合的全排列 8.3在指定树中选择进行全排列 84电话上对应数字的字母组成的所有单词 9.广度优先搜索 9.1单词变换路径( Word ladder) 9.1.1是否存在变换路径 9.12所有最短变换路径 92包围区域 10.深度优先搜索 10.1N皇后问题 10.2恢复IP地址 10.3集合元素之和 10.3.1元素可以重复 10.32元素不可重复 10.33给定元素数目和元素范围 10.4正确的括号对 10.5解数独 10.6单词搜索 10.7小结 10.7.1适用场景 107.2思考步骤 10.7.3代码模板 10.7.4深搜与回溯、递归的区别 11.分治法 11实现pow(x,n) 11.2 Sqrt(x) 12.贪心算法 12.1跳台阶游戏 122买卖股票的最佳时机 122.1最多允许交易一次 122.2可以交易任意多次 1223最多可以交易两次 1224可以交易任意多次 1225交易后需要停止一段时间 123最长不含重复元素的子串 124存放的最大水量 13.动态规划 131三角形从顶到底的最小路径和 132最大连续子数组 13.3字符串的所有子回文字符串 134最长公共子序列问 刁题 13.5字符串的编辑距离 13.6不同路径之和 13.6.1无障碍 13.6.2有障碍 137最大矩形面积 13.8字符串交叉组合 139旋转字符串 13.10最小路径和 13.11所有的编码方式 13.12独一无二的子序列数 13.13拆分单词 13.13.1单词是否由词典中的单词组成 13.132返回所有可以切分的解 14.图 14.1图的克隆 15.细节实现题 15.1反转整数 152对称数判断 153区间的相关操作 153.1在区间中插入新的区间 1532合并区间 154包含子串元素的最小窗口 15.5大数乘法 15.6给定串中是否存在包含所有单词的子串 157 Pascal三角形 157.1生成 Pasca三角形 157.2 Pascal三角形的第N行 15.8螺旋形矩阵 158.1螺旋打印矩阵 15.82生成螺旋矩阵 159Z字形输出字符串 15.10不使用乘、除、取模实现两个整数相除 15.11文本对齐 15.12共线的最大点数 16其他问题 16.1随机数生成器 1.数组 11从有序数组中删除重复元素 情况1:要求删除后每个数字只出现一次 要点:双指针,一前一后 代码1双指针解决 / LeetCode, Remove Duplicates from Sorted Array 7时间复杂度0(n),空间复杂度0(1) class Solution t public: int remove Duplicates(vector<int>& nums)t if (nums empty () return 0 int index o for (int i =1; i nums size(); i++)I if (nums [index] ! nums [i]) mums [++index]= nums [i] return index 1 ·情况二:每个数字最多可以出现两次 要点:还是双指针,不过注意变化 LeetCode, Remove Duplicates from Sorted Array II 时间复杂度0n),空间复杂度0(1) //qauthorhex108(https://github.com/hex108) class Solution t public: int remove Duplicates(vector<int>& nums)t if (nums size()<= 2) return nums size( int index 2 for (int i=2; i< nums, size(: i++)f if (nums [i] ! nums [index-2]) nums [index+]= nums [il return index; 1.2在排序数组被旋转后进行查找 情况1:不存在重复的数字 例如:01234567->4567012 要点:二分查找,不过特别注意边界条件的判断 LeetCode, Search in Rotated Sorted Array /时间复杂度0(1ogn),空间复杂度0(1) class solution pub⊥ic: int search(const vector<int>& nums, int target)i int first =o, last nums size( while (first ! last)i const int mid first +(last -first)/2 if (nums [mid] = target return mid: if (nums [first] < nums [mid])I f (nums [first] < target & target nums [mid]) last mid: else first mid t 1. else i if (nums [mid] target & target < nums [last -1]) first mid 1 else last mid; return -1 }; 情况2:允许重复 例如:1,3,1,1,1 允许重复元素,则上一题中如果A[m]>=A[1],那么[1,m]为递增序列的假设就不能成立了,比 如[1,3,1,1,1]。 如果A[m]>=A[1]不能确定递增,那就把它拆分成两个条件: 若A[mMA[1],则区间[1,m一定递增 若A[m]=A[]碓定不了,那就1++,往下看一步即可。 //LeetCode, Search in Rotated Sorted Array II //时间复杂度0(n),空间复杂度0(1) class Solution I public: bool search(const vector<int>& nums, int target)t int first =0, last =nums size( while (first ! last)i const int mid first (last -first)/2 if (nums [mid] = target) return true; if (nums [first] nums [mid])i if (nums [first] <= target & target nums [mid]) last mid else first mid +1 F else if (nums [first] nums [mid])i if (nums [mid] target & target < nums [last-1l) first mid +1 else last mid f else //skip duplicate one first++; return false } 1.3寻找两个排序数组的中位数 要点:比较A的第k/2个元素和B的第k2个元素 假设A和B的元素个数都大于k/2,我们将A的第k/2个元素(即A[k/2-1)和B的第k/2 个元素(即Bk/2-1])进行比较,有以下三种情况(为了简化这里先假设k为偶数,所得到的结论 对于k是奇数也是成立的) A[k/2-1]==B[k/2-1] A[k/2-1]>B[k/2-1 A[k/2-1]<B[k/2-1 如果A[k/2-1]<B[k/2-1].票味着A[O]到A[x/2-1的肯定在AUB的topk元系的范围 内,換句话说,A[k/2-1]不可能大于A∪B的第k大元素。留给读者证明。 因此,我们可以放心的删除A数组的这k/2个元素。同理,当A[k/2-1]>B[k/2-1]时,可 以删除B数组的k/2个元素。 当A[k/2-1]==B[κ/2-1]时,说明找到了第k大的元素.直接返回A[k/2-1]或B[k/2-1] 即可。 /LeetCode, Median of Two Sorted Arrays //时间复水度0(1og(m+n),空间复办度0(1og(m+n) class Solution ublic double findMedianSortedArrays(const vector<int>&A, const vector<int>& B)i const int m =A size const int n =B size int total =m +n. f (total 0x1) return find_kth(A begin(,m, B begin(,n, total /2+ 1) else return (find_kth(Abegin(),m, Bbegin(,n, total /2 find_kth(Abegin(), m, B begin, n, total /2+1))/2.0; private static int find_kth(std:: vector<int>:: const_iterator A, int m, std:: vector<int>:: const iterator B, int n, int k)i //always assume that m is equal or smaller if (m>n) return find_kth(B,n, A, m, k) if (m ==0)retum *(B+ k-1) if (k = 1)return min(*A, *B); //divide k into tuo parts int ia min(k /2, m), ib=k-ia; 主f(*(+ia-1)<*(B+ib-1) return find kth(A ia, m -ia, B, n, k-ia) else if (*(A+ ia-1)>*(B+lb-1) return find kth(A. m, B+ ib. n-ib. k -ib) else return A[ia-1] 14最长连续序列 例子:100,4,200,1,3,2]最长连续序列为[1,2,3,4] 要点:使用 unordered set进行解决 class Solution t public: int longestConsecutive(vectorsint> &num)[ unordered_set<int> record(num begin(), num end(); int res =1 for (int n: num)i if(record. find (n==record. endo continue record. erase(n); int prev= n-l, next n+l2 while(record. find(prev)! =record. endo) record.erase (prev--) while (record. find (next)l -record, endo record, erase (next++): res= max(res, next-prev-1): return res, 1.5累加和 ·情况1:在给定数组中找出2个数字,累加和为 target,返回下标 要点:利用hash表存储每个数的下标 //LeetCode, TwO Sum /方法2:hash。用一个哈希表,存储每个数对应的下标 /时间复杂度0n),空间复杂度0(n) class Solution t public: vector<int> twoSum (vector<int> &nums, int target)t unordered_mapsint, int> mapping; vector<int> result: for (int i =0: i nums, size(: i++)t mapping [nums [i] =i1 for (int i =0: i nums size:i++)[ const int gap target- nums [i] if (mapping find (gap)!= mapping end( && mapping [gap]>i)t result.push_back(i +1) result. push_back(mapping [gap] +1); break; return result: }; 如果是已经排序的数组,可以采用双指针的方法

...展开详情
试读 127P LeetCode解题总结
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
LeetCode解题总结 38积分/C币 立即下载
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页

试读结束, 可继续阅读

38积分/C币 立即下载 >