- 博客(114)
- 资源 (4)
- 收藏
- 关注
RSS订阅
原创 LeetCode题解汇总
LeetCode题解汇总LeetCode题解总结目录，C++语言 题号 题目 难度 解析连接 5 最长回文子串 medium C++ 17 电话号码的字母组合 medium C++ 31 下一个排列 medium C++ 32 最长有效括号 hard C++ 41 缺失的第一个...
2018-09-10 20:38:08
1035
原创 Python 闭包
变量作用域变量作用域是在程序运行时变量可以被访问的范围，定义在函数内部的为局部变量，只能在函数内部可以访问def fun(): num = 10 #局部变量 print('num = %d' % num)fun()[输出结果] num = 10定义在模块外的为全局变量，它在全局范围内均为可见，同时在函数内部也可以访问全局变量num = 10 #全局变量def fu...
2019-10-09 20:24:20
239
原创 [C++] LeetCode 23. 合并K个排序链表
题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:[1->4->5,1->3->4,2->6]输出: 1->1->2->3->4->4->5->6方法一这题可以考虑用二路归并排序，也就是分治法，两两一组合并，最终得到有序的链表。代码/** * Definiti...
2018-09-23 14:09:28
1045
原创 [C++]LeetCode 164. 最大间距
题目给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。示例 1:输入: [3,6,9,1]输出: 3解释: 排序后的数组是[1,3,6,9], 其中相邻元素 (3,6)和 (6,9)之间都存在最大差值 3。示例 2:输入: [10]输出: 0解释: 数组元素个数小于 2，因此返回0。说明:你可以假设数组中所有元素都是非负...
2018-09-23 00:53:25
980
原创 [C++] LeetCode 200. 岛屿的个数
题目给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。示例 1: 输入: 11110 11010 11000 00000 输出: 1示例 2: 输入: 11000 11000 00100 ...
2018-09-06 23:50:40
2460
原创 [C++] LeetCode 287. 寻找重复数
题目给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2: 输入: [3,1,3,4,2] 输出: 3说明： 不能更改原数组（假设数组是只读的）。 只能使用额外的 ...
2018-09-04 15:12:27
733
原创 [C++] LeetCode 295. 数据流的中位数
题目中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5设计一个支持以下两种操作的数据结构： void addNum(int num)- 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。 示...
2018-08-30 15:49:42
982
原创 [C++] LeetCode 436. 寻找右区间
题目给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。注意: 你可以假设区间的终点总是大于它...
2018-08-17 00:49:25
616
原创 [C++] LeetCode 718. 最长重复子数组
题目给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 示例 1: 输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3解释: 长度最长的公共子数组是 [3, 2, 1]。 说明: 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 1...
2018-08-16 23:31:53
711
原创 [C++] LeetCode 174. 地下城游戏
题目一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数...
2018-08-16 00:08:51
684
原创 [C++] LeetCode 354. 俄罗斯套娃信封问题
题目给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。说明: 不允许旋转信封。示例: 输入: envelopes = [[5,4],[6,4],[6,7],[...
2018-08-15 23:06:10
1533
原创 [C++] LeetCode 300. 最长上升子序列
题目给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明: 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n ...
2018-08-15 22:58:37
2146
4
原创 [C++] LeetCode 二叉树的前序、中序、后序遍历
题目二叉树的前序、中序、后序遍历，采用递归和非递归写法。 具体题目见： 二叉树前序遍历https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/ 二叉树中序遍历(https://leetcode-cn.com/problems/binary-tree-inorder-traversal/desc...
2018-07-18 00:22:15
1189
原创 [C++] LeetCode 378. 有序矩阵中第K小的元素
题目给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。说明: 你可以假设k 的值永远...
2018-07-15 18:16:45
2999
原创 [C++] LeetCode 336. 回文对
题目给定一组独特的单词， 找出在给定列表中不同 的索引对(i, j),使得关联的两个单词，例如：words[i] + words[j]形成回文。示例 1: 给定words = ["bat", "tab", "cat"] 返回 [[0, 1], [1, 0]] 回文是["battab", "tabbat"]示例 2: 给定 words = ["abcd", "d
2018-07-15 13:23:00
1001
原创 [C++] LeetCode 214. 最短回文串
题目给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。示例 1: 输入: "aacecaaa" 输出:"aaacecaaa" 示例 2: 输入:"abcd" 输出:"dcbabcd"思路解析这题考虑把字符串s分成s1和s2两部分，即s=s1+s2，其中s1为回文串，s2不是回文串，那么构成的最短回文串就是r...
2018-07-15 13:00:39
2871
原创 [C++] LeetCode 5. 最长回文子串
题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。 示例 1： 输入: &quot;babad&quot; 输出: &quot;bab&quot; 注意: &quot;aba&quot;也是一个有效答案。 示例 2： 输入:&quot;cbbd&quot; 输出: &quot;bb&quot
2018-07-15 12:24:06
2945
原创 [C++] LeetCode 135. 分发糖果
题目老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 相邻的孩子中，评分高的孩子必须获得更多的糖果。 那么这样下来，老师至少需要准备多少颗糖果呢？ 示例 1: 输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发...
2018-07-12 23:51:22
1357
原创 [C++] LeetCode 42. 接雨水
题目给定n 个非负整数表示每个宽度为 1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。 示例: 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6思路解析这道...
2018-07-12 23:00:24
3738
原创 【C++】 LeetCode 240. 搜索二维矩阵 II
题目编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例: 现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22...
2018-07-08 16:12:37
1891
2
原创 [C++] LeetCode 74. 搜索二维矩阵
题目编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。示例 1: 输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] targ...
2018-07-08 16:08:59
652
原创 [C++] LeetCode 57. 插入区间
题目给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。 示例 1: 输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]]示例 2: 输入: intervals = [[1,2],...
2018-07-08 15:45:52
492
原创 [C++] LeetCode 60. 第k个排列
题目给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下："123" "132" "213" "231" "312" "321" 给定 n 和 k，返回第 k 个排列。说明： 给定 n 的范围是 [1, 9]。 给定 k的范围是[1, n!]。 示例 1: 输入
2018-07-08 00:48:26
777
原创 [C++] LeetCode 两数相加 II
题目给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。进阶: 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。示例: 输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 ->...
2018-07-08 00:02:34
559
原创 [C++] LeetCode 148. 排序链表
题目在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5思路解析这题可以采用两种方法，
2018-07-07 22:44:53
918
原创 [C++] LeetCode 407. 接雨水 II
题目给定一个m x n的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。 说明: m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。 示例： 如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。 下雨后，雨水将会被存储在这些...
2018-05-18 21:48:11
1158
1
原创 [C++] LeetCode 117. 填充同一层的兄弟节点 II
题目给定一个二叉树 填充它的每个 next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。 说明: 1. 你只能使用额外常数空间。 2. 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。 示例: 给定二叉树， 调用你的函数后，该二叉树变...
2018-05-04 16:19:49
778
原创 [C++] LeetCode 116. 填充同一层的兄弟节点
题目给定一个二叉树 填充它的每个 next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next指针都被设置为 NULL。 说明:你只能使用额外常数空间。使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两...
2018-05-04 15:59:55
491
原创 [C++] LeetCode 315. 计算右侧小于当前元素的个数
题目给定一个整型数组 nums，按要求返回一个新的 counts 数组。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于nums[i] 的元素的数量。 例子: 返回数组 [2, 1, 1, 0].题解用树状数组（lowbit），然后倒序遍历原始数组即可代码class Solution {public: int ...
2018-05-03 12:24:32
2342
1
原创 [C++] LeetCode 493. 翻转对
题目给定一个数组 nums ，如果 i < j且 nums[i] > 2*nums[j]我们就将 (i, j)称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 示例 1: 示例 2: 注意: 1. 给定数组的长度不会超过50000。 2. 输入数组中的所有数字都在32位整数的表示范围内。题解这道题目用树状数组加上hash来做。关于树...
2018-05-03 12:21:34
1781
原创 [C++] LeetCode 215. 数组中的第K个最大元素
题目在未排序的数组中找到第 k 个最大的元素。请注意，它是数组有序排列后的第 k 个最大元素，而不是第 k个不同元素。 例如， 给出 [3,2,1,5,6,4]和k = 2，返回 5。 注意事项: 你可以假设 k 总是有效的，1 ≤ k ≤数组的长度。方法一直接排序，然后取出第K大即可 代码：class Solution {public: int fin...
2018-04-27 20:01:04
3891
2
原创 [C++] LeetCode 560. 和为K的子数组
题目给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 说明 : 数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。解法一用一个数组累计求和，然后进行遍历就可以了，直接上代码class Solution {public: in...
2018-04-27 00:29:37
3143
原创 [C++] LeetCode 41. 缺失的第一个正数
题目给定一个未排序的整数数组，找出其中没有出现的最小的正整数。 示例 1: 示例 2： 示例 3： 说明: 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。题解这道题直接做其实不难，难就难在时间复杂度为O(n)，同时还要求常数级别的空间。 考虑交换数组中数字位置，由于本题只要求正整数，所以考虑用索引为i的位置存储数字i+1，那么只要遍历一遍，进...
2018-04-26 22:46:54
1077
原创 [C++] std::ios::sync_with_stdio(false); cin.tie(NULL);
std::ios::sync_with_stdio(false)这句语句是用来取消cin的同步，什么叫同步呢？就是iostream的缓冲跟stdio的同步。如果你已经在头文件上用了using namespace std;那么就可以去掉前面的std::了。取消后就cin就不能和scanf，sscanf, getchar, fgets之类同时用了，否则就可能会导致输出和预期的不一样。 取消同步的...
2018-04-25 20:04:30
2644
原创 [C++] LeetCode 236. 二叉树的最近公共祖先
题目给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义： “对于有根树T的两个结点u、v，最近公共祖先表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。”（一个节点也可以是它自己的祖先） 例如，节点5和节点1的最近公共祖先是节点3；节点5和节点4的最近公共祖先是节点5，因为根据定义，一个节点可以是它自己的祖先。题解这道题应该是面试常...
2018-04-23 13:13:59
3580
原创 [C++] LeetCode 85. 最大矩形
题目给定一个填充了 0 和 1 的二进制矩阵，找到最大的只包含 1 的矩形并返回其面积。 例如，给出以下矩阵： 返回6题解这道题可以参考LeetCode 84. 柱状图中最大的矩形，这道题，那么这里每一行维持一个数组，记录当前矩阵的高度，然后就可以采用84. 柱状图中最大的矩形的方法计算出当前层最大面积，逐层下去，就可以得出最大值 84. 柱状图中最大的矩形求解过程可以参考8...
2018-04-17 14:21:45
1280
原创 [C++] LeetCode 84. 柱状图中最大的矩形
题目给出 n 个非负整数来表示柱状图的各个柱子的高度，每个柱子紧挨彼此，且宽度为 1 。 您的函数要能够求出该柱状图中，能勾勒出来的最大矩形的面积。 示例： 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的各个高度为 [2,1,5,6,2,3]。 图中阴影部分为最大矩形面积，其面积为 10 个单位。 所以，您的函数给定高度是 [2,1,5,6,2,3] 的话，则返回 10...
2018-04-17 14:15:07
8645
原创 [C++] LeetCode 132. 分割回文串 II
题目给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 符合要求的的最少分割次数。 例如，给出 s = &amp;amp;quot;aab&amp;amp;quot;, 返回 1 因为进行一次分割可以将字符串 s 分割成 [&amp;amp;quot;aa&amp;amp;quot;,&amp;amp;quot;b&amp;amp;quot;] 这样两个回文子串。题解这
2018-04-17 13:48:08
1286
原创 [C++] LeetCode 140. 单词拆分 II
题目给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字串中增加空格来构建一个句子，使得句子里所有的单词都在词典中。你可以假设字典中无重复的单词。 返回所有这些可能的句子。 例如，给出 s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"]. 答案为 ["cats and
2018-04-17 12:47:29
1058
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人