164. 最大间距

题目描述 给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。 如果数组元素个数小于 2,则返回 0。 示例 1: 输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 示例 2: 输入: [10] 输出: 0 解释: 数组元素个数小于 2,因此返回 0。 说明: 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。 https://leetcode-cn.com/problems/maximum-gap/ 解法1 解法1使用Radix sort(基数排序)。因为题目要求线性的时间复杂度,而所有的基于比较的排序算法平均时间复杂度最优也只有O(nlogn)。而使用基数排序,当数组长度为n,数组中位数最多的数字有w位,那么基数排序的时间复杂度能达到O(wn)。此外,题目提到了数字是非负整数,这样实现Radix sort会更加容易。 题目中说明了数字是能用32位整数表示的,那么2^32 = 2,147,483,647,只有10位。也就是说w=10,是一个常数。那么在题目的限制下,时间复杂度可以认为是O(n),符合题意。而Radix sort是非原地排序,需要长度位n的辅助数组,空间复杂度为O(n),也符合题意。 我们以”nums = [13,23,36,39,11]”为例,来解释Radix的执行过程。首先,我们需要长度为10的数组count,来记录每个数字的个位数出现几次。 nums = [13,23,36,39,11]” 当前位:个位count:idx content0 01 12 03 24 05…

Read more

127. 单词接龙

题目描述 给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则: 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明: 如果不存在这样的转换序列,返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。 示例 1: 输入: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出: 5 解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。 示例 2: 输入: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”] 输出: 0 解释: endWord “cog” 不在字典中,所以无法进行转换。 https://leetcode-cn.com/problems/word-ladder/ 解法1…

Read more

128. 最长连续序列

题目描述 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 https://leetcode-cn.com/problems/longest-consecutive-sequence/ 解法1 题目要求时间复杂度O(n),那就说明只能扫描一次,排序什么的是不行的。我们可以举个简单的例子,来启发我们寻找合适的算法解决问题。 例1: nums = {1,2,0,5,4,3,-1} 遇到1,那么1独立成一个序列,长度是1; 遇到2,1和2能连在一起成为长度为2的序列{1,2}; 遇到0,那么0可以和刚刚{1,2}的序列成为长度为3的连续序列{0,1,2}; 遇到5,那么5需要独立成一个序列,长度是1; 遇到4,那么5和4能够接上,形成长度为2的序列{4,5}; 遇到3,那么3会将刚刚发现的两个序列{0,1,2}与{4,5}接上,形成{0,1,2,3,4,5},长度为6。 遇到-1,那么-1将会与刚刚形成的序列{0,1,2,3,4,5}连接,形成长度为7的序列{-1,0,1,2,3,4,5} 根据例1,我们可以使用map来记录数字与数字所对应序列的长度。每当添加一个新的数字num,检查num-1与num+1是否存在;如果存在,那么就将左右两部分与新添加的数字num连接起来,形成新的序列。然后更新新序列两端,为新序列的长度。 为什么只需要更新新序列左右两端的值,而不是新序列每一个数字的值?这是因为,序列相联时,只会取端点的值。根据上面的分析,我们能够编写出下面代码。时间复杂度O(n), 空间复杂度O(n)。

Read more

334. 递增的三元子序列

题目描述 给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。 数学表达式如下: 如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1,使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1) 。 示例 1: 输入: [1,2,3,4,5] 输出: true 示例 2: 输入: [5,4,3,2,1] 输出: false 解法1 首先题目要求时间复杂度O(n),空间复杂度O(1)。这就要求我们只扫描一遍,并且只可以使用有限个变量,那么使用暴力法是不可能的。双指针法?好像用不上哎。排序再处理?不行,要求O(n)。使用TreeMap?不行,要求O(n)。经过了5分钟的思考,嗯,我们可以试试找长度为2的递增子序列。那么可以用变量min记录之前遇到的最小的数字,如果当前数字比min大,那么我们就找到了长度为2的子序列;如果当前数字比min小,那么就更新min。 扩展下,题目要求长度为3的子序列。那么我们可以维护两个变量min1, min2,使得min1始终小于min2,当我们遇到一个数num,且num > min2时,就满足了min1<min2<num。此时,我们就找到了第一组递增三元子序列,返回true即可。 P.S. 好高兴啊,这道题是我刷了好久的题,第一次就想到了最优解法。

Read more

11. 盛最多水的容器

题目描述 给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明:你不能倾斜容器,且 n 的值至少为 2。 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。 示例: 输入: [1,8,6,2,5,4,8,3,7] 输出: 49 https://leetcode-cn.com/problems/container-with-most-water/ 解法1 解法1使用暴力法,使用变量i,j(i<j)指向每一个挡板,计算res = max(res, (j-i)*min(height[i], height[j]))。时间复杂度O(n^2), 空间复杂度O(1)。 解法2 在解法1中,我们遍历了每一对挡板。其实,我们完全不必要计算每一对挡板产生的容积,我们只需要遍历一遍就能够计算出答案。例如{2,3,5,1,7},在解法1中第一次循环我们计算{<2,3>, <2,5>, <2,1>, <2,7>}。题目要求我们求得最大的容积,其实我们计算<2,7>就够了,如果我们用其他组合计算容积,首先宽度会减少;其次容积取决于短板,即使在2与7之间有更长的木板,那么我们也只能用最短的木板2来计算容积。 根据上面的分析,我们使用双指针法来解决问题。使用变量i,j指向数组height的两端。计算res = max(res, (j-i)*min(height[i], height[j])),然后将i与j中指向短板的那一个指针向内移动。即,height[i] > height[j], 则j–;如果height[i] < height[j],则i++;如果二者相等,先移动哪一个都无所谓。 解释: 首先,我们让i与j指向height的两端,能够保证容器容器的宽度(j-i)尽可能的宽。其二,容器装水量取决于两端height[i]与height[j]较短者,所以有上面的公式。其三,计算完当前容积后,我们应该淘汰二者较短的那一个,因为我们没有理由淘汰长板。如果我们淘汰长板,那么随着宽度的减少,左右挡板的高度变化趋势是下降的,这样会使得容积更小。

Read more

309. 最佳买卖股票时机含冷冻期

题目描述 给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 解法1 解法1使用到了有限状态机(FSM),在第i天我们的状态有3种,分别是hold(持股)、sold(抛售)和rest(休息)。第i天的hold状态可由第i-1天的hold状态(继续持有)和第i-1天的rest状态(买入股票)而来。第i天的rest状态可由第i-1天的rest状态(继续休息)和第i-1天的sold状态(冷冻期)而来。第i天的sold状态只能从第i-1天的hold状态而来(抛售股票)。我们在图1描述了这些状态。 对于第1天,sold状态是不合法的,因为我们还没有买进;对于hold和rest状态是合法的。题目要求计算最大利润,那么最后一天的最大利润只可能来自sold或者rest状态,而绝不可能来自于hold状态(因为我们手中持有股票)。 我们定义了3个长度为|prices|的数组来实现有限状态机,分别是hold、sold和rest。对于第1天,我们初始化hold[0] = -prices[0], sold[0] = -∞ (第1天抛售状态为不合法), rest[0]。hold[i], sold[i]与rest[i]的物理意义分别是如果选择第i持股、抛售与休息能获得的最大利益。那么我们有: hold[i] = max(hold[i-1], rest[i-1] – prices[i]) rest[i] = max(rest[i – 1], sold[i-1]) sold[i] = hold[i-1] + prices[i] 下面,我们举两个例子来解释算法执行过程。 图2中列举了算法执行过程,我们分别解释i=1(第二天)与i=4(第5天)的计算过程。 例1: (i…

Read more

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 解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润…

Read more

123. 买卖股票的最佳时机 III

题目描述 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。   随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格…

Read more

121. 买卖股票的最佳时机

题目描述 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 解法1 解法1使用动态规划方法,我们定义两个数组L和P。L[i]表示第0…i天最低的股价;P[i]表示第0…i天能获得的最大利益,那么答案 = max(P[i]), 1 <= i < |prices|。 那么我们就能够写出状态转移方程L[i] = min(L[i] –…

Read more

45. 跳跃游戏 II

题目描述 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。 https://leetcode-cn.com/problems/jump-game-ii/ 解法1 解法1是采用贪心解法,解法1很啰嗦,目的是尽可能让我们容易理解。策略是这样的,我们计算nums[i] + i,物理意义代表从当前出发能到达的最远位置。我们尽可能使下一跳落到较远的位置,这样才能使得跳到终点的步数最少。 我们以例子“[2,3,1,1,4]”为例,计算nums[i]+i -> nums[i],nums被更新为“[2,4,3,4,8]”,代表我站在第0个位置上,最远能跳到第2个位置上;站在第1个位置上,最远跳到第4个位置上(也就是终点),站在第2个位置上,最远能跳到第3个位置上……以此类推。那我们从0出发,最远能跳到第二个位置上,也就是说我们可以跳到第1个位置,也可以跳到第2个位置上。我们发现从第一个位置出发最远能到4,而从第2个位置出发最远能跳到3。我们刚刚说过,要保证下一跳落到较远到位置,所以我们选择从0跳到1,接着我们发现从1可以直接到终点,那么我们从1跳到4。 注意,不要落入一个误区:不是使本跳跳的尽可能远,而是从本跳出发,选择一个落脚点,从这个落脚点出发到达的尽可能远。以上面的为例,第一步我们从0跳到2虽然走的比0跳到1远,但是接下来从2出发最多只能到达3,而从1出发我们直接能到达终点。 根据上面的分析,我们能写出如下的代码,时间复杂度与空间复杂度均为O(n)。虽然这个代码包含双重循环,但是内层循环会改变外层循环的计数器,实际上只扫描了一次。 其实,上面的代码还可以继续优化,我们不需第一次扫描,将第一次扫描的逻辑合并到第二次扫描。 解法2 解法2很巧妙,但思想和解法1是差不多的。我们首先计算从当前位置i出发能到到达的最远距离,记为upperBound;我们还使用了另一个变量lastStepBound,记录从上一跳出发能到达的最远位置,最后我们使用res变量记录花费了几跳。我们接下来从i+1出发,继续更新upperBound,直到走到lastStepBound,然后我们更新lastStepBound = upperBound. 我们从i+1出发走到 lastStepBound,是为了寻找更远的下一跳。 我们以“[2,3,1,1,4]”为例,初始化lastStepBound = 0, upperBound = 0. 我们从i=0出发,更新upperBound = max(upperBound, i+nums[i]) = 2,然后我们更新lastStepBound = 2(第一跳起跳, res++),表示我们从0出发最远能到达2。接下来走到i=1更新upperBound = 4;走到i=2发现最远能到达3,则不更新upperBound。这时我们碰到了lastStepBound,得知我们下一跳最远能跳到4,另lastStepBound=upperBound(第一跳落地,第二跳起跳 res++)。当i=3时更新upperBound失败,此时i…

Read more