- 博客(169)
- 收藏
- 关注
RSS订阅原创 leetcode_188. 买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入: [2,4,1], k = 2输出: 2解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。示例 2:输入: [3,2,6,5,0,3], k = 2输出: 7解释: 在第
2020-08-31 12:11:17
194
原创 leetcode_187. 重复的DNA序列
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。示例：输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”输出：[“AAAAACCCCC”, “CCCCCAAAAA”]解析：本题题目写的不是很清楚明白本题的要求：在目标字符串中找出所有长度为10的重
2020-08-28 10:59:55
197
原创 leetcode_179.最大数
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。示例 1:输入: [10,2]输出: 210示例 2:输入: [3,30,34,5,9]输出: 9534330说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。解析：本题的核心在于排序，将数字按照字符串的字典序进行排序。排序的方式有很多，这里就不再手写，直接调用c++的sort方法。排序规则的简单办法便是将数字转换成字符串然后按照字符串的方式排序。class Solution { /*static bo
2020-08-28 10:10:15
208
原创 leetcode_173. 二叉搜索树迭代器
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 next() 将返回二叉搜索树中的下一个最小的数。示例：BSTIterator iterator = new BSTIterator(root);iterator.next(); // 返回 3iterator.next(); // 返回 7iterator.hasNext(); // 返回 trueiterator.next(); // 返回 9iterator.hasNext(); // 返回 t
2020-08-27 17:36:49
190
原创 leetcode_174. 地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数
2020-08-27 17:24:06
103
原创 leetcode_172. 阶乘后的零
给定一个整数 n，返回 n! 结果尾数中零的数量。示例 1:输入: 3输出: 0解释: 3! = 6, 尾数中没有零。示例 2:输入: 5输出: 1解释: 5! = 120, 尾数中有 1 个零.说明: 你算法的时间复杂度应为 O(log n) 。解析：本题肯定不能把阶乘算出来然后数，凭借阶乘的爆炸式增长，很快便会发生溢出。我们以5为例进行分析5！ = 5 * 4 * 3 * 2 * 1 = 120阶乘尾数的零，来自其中的每一个10而每一个10,仅可能来自2 * 5而阶乘中偶数
2020-08-27 16:16:05
318
原创 leetcode_171. Excel表列序号
给定一个Excel表格中的列名称，返回其相应的列序号。例如，A -> 1B -> 2C -> 3…Z -> 26AA -> 27AB -> 28…示例 1:输入: “A”输出: 1示例 2:输入: “AB”输出: 28示例 3:输入: “ZY”输出: 701解析：本题是之前某道题的翻转版，难度没有那一道高。本题其实就是一个简单的26进制转换。class Solution {public: int titleToNumbe
2020-08-27 15:51:30
79
原创 leetcode_169. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1:输入: [3,2,3]输出: 3示例 2:输入: [2,2,1,1,1,2,2]输出: 2解析：本题方法较多，这里学习并使用了一种简单且快速的算法——摩尔投票算法。其理解方法不再于此赘述可以参见以下网址：https://www.zhihu.com/question/49973163class Solution {
2020-08-27 15:43:05
74
原创 leetcode_168. Excel表列名称
给定一个正整数，返回它在 Excel 表中相对应的列名称。例如，1 -> A2 -> B3 -> C…26 -> Z27 -> AA28 -> AB…示例 1:输入: 1输出: “A”示例 2:输入: 28输出: “AB”示例 3:输入: 701输出: “ZY”解析：本题看上去比较简单，但是在一些边角处可能出现问题。本题类似于一个26进制的转换，但是转换的数字是1-26而计算机上的数字是从零开始的。因此我们在每个字母的计算前，
2020-08-27 15:16:45
71
原创 leetcode_167.两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。说明:返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。示例:输入: numbers = [2, 7, 11, 15], target = 9输出: [1,2]解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, inde
2020-08-27 15:14:05
86
原创 leetcode_165.比较版本号
比较两个版本号 version1 和 version2。如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。你可以假设版本字符串非空，并且只包含数字和 . 字符。. 字符不代表小数点，而是用于分隔数字序列。例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3
2020-08-27 15:05:16
164
原创 leetcode_164.最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。示例 1:输入: [3,6,9,1]输出: 3解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。示例 2:输入: [10]输出: 0解释: 数组元素个数小于 2，因此返回 0。说明:你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。解析：本题
2020-08-27 14:56:28
177
原创 Leetcode_162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。示例 1:输入: nums = [1,2,3,1]输出: 2解释: 3 是峰值元素，你的函数应该返回其索引 2。示例 2:输入: nums = [1,2,1,3,5,6,4]输出: 1 或 5解释: 你的函数可以返回索引 1，
2020-08-27 14:38:05
98
原创 leetcode_160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表：在节点 c1 开始相交。示例 1：输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：相交节点的值为 8 （注意，如...
2020-01-22 10:07:32
128
原创 leetcode_155. 最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。push(x) -- 将元素 x 推入栈中。pop() -- 删除栈顶的元素。top() -- 获取栈顶元素。getMin() -- 检索栈中的最小元素。示例:MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);...
2020-01-22 09:42:07
111
原创 leetcode_154. 寻找旋转排序数组中的最小值 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。注意数组中可能存在重复的元素。示例 1：输入: [1,3,5]输出: 1示例 2：输入: [2,2,2,0,1]输出: 0说明：这道题是 寻找旋转排序数组中的最小值 的延伸题目。允许重复会影响算法的时间复杂...
2020-01-22 09:37:23
90
原创 leetcode_153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你可以假设数组中不存在重复元素。示例 1:输入: [3,4,5,1,2]输出: 1示例 2:输入: [4,5,6,7,0,1,2]输出: 0解析：本题与之前一道在旋转数组中寻找某数字比较类似。甚至本题还要简...
2020-01-21 17:04:01
78
原创 leetcode_152. 乘积最大子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。解析：本题与加法版的不同，对于相同的数，加法中大的数加上这个数一定比小的数加上这个数要大，因此...
2020-01-21 16:31:10
92
原创 leetcode_151. 翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。示例 1：输入: “the sky is blue”输出: “blue is sky the”示例 2：输入: " hello world! "输出: “world! hello”解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：输入: “a good example”输出: “examp...
2020-01-21 15:28:57
125
原创 leetcode_150. 逆波兰表达式求值
根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。示例 1：输入: [“2”, “1”, “+”, “3”, “*”]输出: 9解释: ((2 + 1) * 3) = 9示例 2：输入:...
2020-01-21 14:32:47
94
原创 leetcode_149. 直线上最多的点数
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。示例 1:输入: [[1,1],[2,2],[3,3]]输出: 3解释:^| | o| o| o+------------->0 1 2 3 4示例 2:输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]输出: 4解释:^...
2020-01-21 13:57:42
147
原创 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解析：对时间空间复杂度有要求，那么就必须思考用什么方法进行排序对于时间复杂度O...
2020-01-21 10:48:44
166
原创 leetcode_147. 对链表进行插入排序
对链表进行插入排序。插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。插入排序算法：插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到...
2020-01-21 09:43:50
87
原创 leetcode_146. LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数...
2020-01-20 17:24:33
201
原创 leetcode_145. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。解析：递归法过于简单，这里用迭代解决后序遍历不同于前序中序的迭代法，不同于后两者，后序遍历需要先遍历左右两子树，最后才输出自身。如果使用平常的方法，节点自身在过程中便会丢失。因此定义一个变量，用来界定是否应该输出这个节点。如果某个节点的右子树没有遍历，那么这个节点就不应该输出，也不应该从栈中移除。class Solution {public: ...
2020-01-20 16:32:36
108
原创 leetcode_144. 二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。示例:输入: [1,null,2,3]1 \ 2 /3输出: [1,2,3]进阶: 递归算法很简单，你可以通过迭代算法完成吗？解析：二叉树的遍历是基本算法，建议全文背诵/** * Definition for a binary tree node. * st...
2020-01-20 16:09:49
84
原创 leetcode_143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例 1:给定链表 1->2->3->4, 重新排列为 1->4->2->3.示例 2:给定链表 1->2->3->4->5, 重新排列为 1-...
2020-01-20 15:32:12
126
原创 leetcode_142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。示例 1：输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1解释：...
2020-01-20 14:34:45
87
原创 leetcode_141. 环形链表
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。示例 1：输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。示例 2：输入：head = [1,2], pos = 0输出：true解...
2020-01-20 11:26:26
85
原创 leetcode_140. 单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明：分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入:s = “catsanddog”wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]输出:...
2020-01-20 11:11:44
90
原创 leetcode_139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true解释: 返回 true 因为 “leetcode” 可以被拆分...
2020-01-20 10:13:02
97
原创 leetcode_138. 复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 nu...
2020-01-20 09:10:00
295
原创 leetcode_137. 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？示例 1:输入: [2,2,3,2]输出: 3示例 2:输入: [0,1,0,1,0,1,99]输出: 99解析：我是真的做不到使用额外空间实现本题的正确做法是模拟三进制运算。定义两个变量A,B，B为低位...
2020-01-20 09:02:02
85
原创 leetcode_136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？示例 1:输入: [2,2,1]输出: 1示例 2:输入: [4,1,2,1,2]输出: 4解析：使用异或位运算，相同的数字异或会变成0，全部异或之后剩下的数字便是答案class Solution {pu...
2020-01-19 16:32:19
55
原创 leetcode_135. 分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？示例 1:输入: [1,0,2]输出: 5解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2:输入...
2020-01-19 16:25:56
142
1
原创 leetcode_134. 加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。说明:如果题目有解，该答案即为唯一答案。输入数组均为非空数组，且长度相同。输入数组中的元素均为非...
2020-01-19 15:52:11
108
原创 leetcode_133. 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。class Node {public int val;public List neighbors;}测试用例格式：简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1，第二个节点值为 2，以此类推。该图在测试用例中使用邻...
2020-01-19 14:35:51
238
原创 leetcode_132. 分割回文串 II
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。示例:输入: “aab”输出: 1解释: 进行一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。解析：本题与上一题不同，要求返回最少分割次数。看似更加简单，实则相反。如果用上一题的基础来看，对上一题的结果即所有的分割可能进行统计即可获得最少分割次数。但是毫无疑问的超时...
2020-01-19 13:57:10
131
原创 leetcode_131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例:输入: “aab”输出:[[“aa”,“b”],[“a”,“a”,“b”]]解析：遇到这种需要返回所有可能方案的题目，应该思考是否可以用回溯法解决。本题采用回溯法加剪枝来解决。见图对于字符串aab,我们尝试在它的每一位进行截断，并对截下来的前半段进行判定，如果前半段是回文串...
2020-01-19 10:11:11
195
原创 leetcode_130. 被围绕的区域
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。示例:X X X XX O O XX X O XX O X X运行你的函数后，矩阵变为：X X X XX X X XX X X XX O X X解释:被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。...
2020-01-17 17:40:02
95
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人