-
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] –…
-
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…
-
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，如果存在我们继续回溯……直到看看能不能回溯到起点。如果能够回溯到起点，那我们从起点正向出发也一定能够到达终点；反之如果不能回溯到起点，那我们就没办法到达终点。
-
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。…
-
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…
-
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统计，逻辑就不正确了。
-
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变量即可。全部代码如下。
-
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 https://leetcode-cn.com/problems/sort-list/ 解法1 – 自顶向下的归并排序 首先，时间复杂度限定O(nlogn)，那么在常见的排序算法中，可选的排序算法只有快排、堆排序和归并排序。因为采用了链表这种数据结构，快排和堆排序需要随机访问，因此归并排序较为合适。此外，题目要求常熟级的空间复杂度，也就是说要求原地排序，我们就不能将链表转化为数组排序后再转化为链表。我们在这里贴出常见的排序算法以及相应的空间/时间复杂度。 归并排序分为自顶向下和自底向上两种实现方式，自顶向下需要使用递归来把待排序的数组拆分成两部分，这个过程持续直到待拆分的元素只剩下一个，这一个元素当然是排序好的了。然后我们逐层返回，将排序好的两部分归并，那么归并后的链表也是有序的。严格地说，自顶向下的归并排序并不是常数级空间复杂度，因为递归过程中消耗了系统栈。 下面以示例1: 4->2->1->3为例，图解自顶向下的归并排序过程。为了将链表分为相等的两部分，我们需要寻找链表的中间节点。在这里我们使用了一个技巧，只需要遍历一遍链表就能找到中间节点。 我们寻找到中间节点，记为mid。我们还需要找到中间节点的前一个节点midPrev，因为我们需要将链表断开形成左右两个独立的链表。如果不断开，在寻找中间节点的过程会形成无限递归！！！ [4->2->1->3]会被拆分成[4->2], [1->3]两部分，而[4->2]又会被拆分成[4]和[2]两部分。当链表只剩下一个元素时，自然就是排好序的。我们再返回到上一层，将排好序的元素归并。[4]与[2]归并后会形成[2->4]的链表，而[1]与[3]归并会形成[1->3]的链表，我们再返回更上一层将[2->4]与[1->3]归并得到最终结果[1->2->3->4]。全部代码如下所示。
-
876. 链表的中间结点
题目描述 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2： 输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。 https://leetcode-cn.com/problems/middle-of-the-linked-list/ 解法1 顺序遍历一次求得链表长度为n，然后从头遍历n/2个节点即为答案 解法2 解法2称为快慢指针法，快指针一次遍历两个节点，慢指针一次遍历一个节点。当快指针遍历到链表尽头时，慢指针指向的位置即为链表的中间节点。该方法只需要访问链表一次，十分精妙。快慢指针法也可被用来判断链表是否存在环路：Floyd判圈算法。链表的归并排序算法的实现也依赖于该方法寻找链表中间节点。
-
146. LRU缓存机制
题目描述 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) – 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) – 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。 进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作？ 示例: LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1…