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