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

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

55. 跳跃游戏

题目描述 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。 https://leetcode-cn.com/problems/jump-game/ 解法1 解法1的方法是一种暴力搜索的方法,既然给出了每个位置能跳跃的最大距离,那我们就挨个尝试能落下的位置,然后以该位置为起点继续重复此过程看看能不能到达末尾。这是一种DFS方法,时间复杂度为O(n^2)。这种做法属于“人思考的少,机器思考的多”,另外代码量也很大,所以不推荐这种做法。 解法2 解法2采用贪心的做法,设置一个变量currMax,表示从当前位置之前的任意一点出发能走到的最远的位置。我们遍历每一个位置,判断i是否大于currMax。如果i>currMax,物理意义表示从i之前的任意位置出发,都到达不了i,则肯定到达不了i之后的任何位置,返回false即可。否则,我们更新currMax = max(currMax, i + nums[i])。 解法3 解法3采用回溯的方法,我们从终点向前回溯,看看终点之前有没有一个点i至少能够到达终点的,如果存在则回溯到点i;我们再看看i之前有没有一个点至少能够到达点i,如果存在我们继续回溯……直到看看能不能回溯到起点。如果能够回溯到起点,那我们从起点正向出发也一定能够到达终点;反之如果不能回溯到起点,那我们就没办法到达终点。

Read more

275. H指数 II

题目描述 给定一位研究者论文被引用次数的数组(被引用次数是非负整数),数组已经按照升序排列。编写一个方法,计算出研究者的 h 指数。 h 指数的定义: “h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)至多有 h 篇论文分别被引用了至少 h 次。(其余的 N – h 篇论文每篇被引用次数不多于 h 次。)” 示例: 输入: citations = [0,1,3,5,6] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。   由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3。 说明: 如果 h 有多有种可能的值 ,h 指数是其中最大的那个。 进阶: 这是 H指数 的延伸题目,本题中的 citations 数组是保证有序的。 你可以优化你的算法到对数时间复杂度吗? https://leetcode-cn.com/problems/h-index-ii/ 解法1 本题目和274. H指数的区别是,文章已经按照应用次数排序。此外,题目要求优化到对数时间复杂度,很自然能联想到Binary Search。…

Read more

274. H指数

题目描述 给定一位研究者论文被引用次数的数组(被引用次数是非负整数)。编写一个方法,计算出研究者的 h 指数。 h 指数的定义: “h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)至多有 h 篇论文分别被引用了至少 h 次。(其余的 N – h 篇论文每篇被引用次数不多于 h 次。)” 示例: 输入: citations = [3,0,6,1,5] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 3, 0, 6, 1, 5 次。   由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3。 说明: 如果 h 有多种可能的值,h 指数是其中最大的那个。 https://leetcode-cn.com/problems/h-index/ 解法1 解法1首先对数组排序,从大到小枚举hIndex,然后检测是否符合条件。 以“3,0,6,1,5”为例,共有5篇文章,排序后为“0,1,3,5,6”。我们假设hIndex=5,那么就要求第一篇文章的引用量就要达到5(这样从第一篇往后的文章引用量肯定都达到5),然而第一篇文章的引用量为0,我们减小hIndex。我们假设hIndex=4,那么要求第二篇文章的引用量达到4(这样第2,3,4,5篇文章的引用量都能达到4),然而并没有。我们假设hIndex=3,那么就要求第三篇的引用量达到3。发现达到了,那么就返回3作为hIndex。 全部代码如下,时间复杂度O(nlogn), 空间复杂度O 解法2 解法2使用计数排序的思想,有n篇文章,我们就创建n个桶,编号为0,1,…,n。按照文章的引用次数放入对应编号的桶中,如果引用次数大于n,那么就放入第n个桶中。 我们以“3,0,6,1,5”为例,创建编号为0-5的桶。 桶编号:0…

Read more

229. 求众数 II

题目描述 给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。 示例 1: 输入: [3,2,3] 输出: [3] 示例 2: 输入: [1,1,1,3,3,2,2,2] 输出: [1,2] https://leetcode-cn.com/problems/majority-element-ii/ 解法1 使用Map统计每种数字出现的频率,当发现元素e出现当频率大于⌊ n/3 ⌋时,将其加入到结果列表中,当扫描完数组后返回结果列表。时间复杂度与空间复杂度均为O(n)。 解法2 解法2使用169题的方法,也就是Boyer–Moore majority vote algorithm。我们首先分析下,在数组中出现频率超过⌊ n/3 ⌋最多能有几种元素。容易想到,最多我们只能找到两个元素,它的出现频率大于⌊ n/3 ⌋(如果存在3个,则3个元素频率均为n/3)。 我们还是使用Boyer-Moore算法,创建4个变量counter1、counter2、num1、num2。遍历每个元素e,如果counter1为0,则将元素e赋给num1,且将counter1置为1;如果counter2为0,则将元素e赋给num2,且将counter2置为1;如果e == num1,则counter1自增1;如果e == num2,则counter2自增1;否则(e!=num1且e!=num2),counter1与counter2自减1. 全部代码如下,需要注意的是需要将判断e == num1/2放在if(counter1/2 == 0)之前,否则出现两个相同的元素,将会分别使用counter1与counter2统计,逻辑就不正确了。

Read more

169. 求众数

题目描述 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2 https://leetcode-cn.com/problems/majority-element/ 解法1 使用Map统计每个数出现的频率,当发现元素e出现的频率超过⌊ n/2 ⌋时,返回元素e。时间复杂度与空间复杂度均为O(n) 解法2 对数组排序,然后返回中间元素。因为元素e超过了⌊ n/2 ⌋,那么排序后数组的中间位置已定是元素e。时间复杂度O(nlogn),空间复杂度O(1) 解法3 该方法被称为Boyer-Moore majority vote algorithm。设置变量majority与counter。依次遍历每个元素e,当计数器counter为0时,将e赋给majority,设置counter为1;此后的循环,当发现e==majority时,counter自增1;当发现e!=majority时,counter自减1。 该算法执行完毕时,若存在频率高于⌊ n/2 ⌋的元素,则majority存放的就是答案。如果不存在频率高于⌊ n/2 ⌋的元素,则该算法并不能识别出这种情况。需要再次扫描统计majority出现的频率。 但是本题给定了说明一定存在众数,我们就只需要扫描一次然后返回majority变量即可。全部代码如下。

Read more