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

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]。全部代码如下所示。

Read more

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判圈算法。链表的归并排序算法的实现也依赖于该方法寻找链表中间节点。

Read more

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…

Read more

122. 买卖股票的最佳时机 II

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

Read more

124. 二叉树中的最大路径和

题目描述 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 6 示例 2: 输入: [-10,9,20,null,null,15,7]   -10    / \   9  20     /  \    15   7 输出: 42 https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/ 解法1 – DFS(超时) 刚遇到题目时没有什么思路,根据题目描述“本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。”,发现这很像图数据结构的DFS算法。 我们可以把树转换为无向图,这通过向TreeNode数据结构添加Parent字段就能够实现。这样,每个节点有三个临接点分别是左子树、右子树、父节点。 我们从树中寻找val大于0的节点作为DFS的起点,从所有的起点出发遍历完这棵树,肯定能找到包含答案的路径。我们累积走过的每一个定点的值,用当前累积的值更新全局变量result,result就存放了最终的答案。 很遗憾,上面的方法虽然能够找到正确的答案,但是效率太低。我一时也没有找到这种方法的优化思路,先记录下来。 解法2 方法2来自于该题目的评论区。思路是:节点n向父节点汇报以下三者中的最大值;如果节点n是叶节点则仅汇报节点n自身的值。 节点n的值 节点n的值+节点n左子树汇报的值 节点n的值+节点n右子树汇报的值 我们以图2为例,红色字体给出的是节点向其父节点按照上述规则汇报的值。注意,图2与图1不相同。 有了上面的图,我们把图中每个顶点“臆想”成该顶点就是整颗树的根节点,而忽略掉该节点之上的其他节点。然后我们对每个“臆想”的根节点,按照以下规则计算出的最大值。 根节点的值 根节点的值+左子树汇报的值 根节点的值+右子树汇报的值 根节点的值+左子树汇报的值+右子树汇报的值 因为我们把每个节点“臆想”成根节点,我们才会有上面规则的第4条。需要注意的是,该问题的解并不一定来源于整颗树的根节点。我们想个反例,把图2的根节点5的值调整为-∞,那么解应该来源于节点8….

Read more

115. 不同的子序列

题目描述 给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。 一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,”ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是) 示例 1: 输入: S = “rabbbit”, T = “rabbit” 输出: 3 解释: 如下图所示, 有 3 种可以从 S 中得到 “rabbit” 的方案。 (上箭头符号 ^ 表示选取的字母) rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^ 示例 2: 输入: S = “babgbag”, T = “bag” 输出: 5 解释: 如下图所示, 有 5 种可以从 S 中得到 “bag” 的方案。 (上箭头符号 ^ 表示选取的字母) babgbag…

Read more

109. 有序链表转换二叉搜索树

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10, -3, 0, 5, 9], 一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5 https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/ 解法1 二叉搜索树(BST)是一种特殊的二叉树,他满足左子树的全部元素都小于根节点,右子树的全部元素都大于根节点。题目另外要求生成的平衡的BST,意味着在上面的基础上又添加了新条件:左右子树高度差的绝对值不超过1。 首先给定的链表是有序的,加上BST本身的特性会使我们联想到二分查找的思想。根据有序列表构建BST我们可以使用类似于二分查找的思路,用中心元素将链表划分为两部分,左半部分都小于中心元素、右半部分都大于中心元素。 采用链表作为数据结构,不容易实现随机访问。为了能够快速的获取中心元素,我们首先将链表转换为数组。我们取数组长度的一半作为中心元素的索引。中心元素作为二叉树的根节点,将左半部分与右半部分以相同的方式处理继续构建左子树与右子树。直到左半部分或右半部分没有元素时,构建过程停止。 下面以题目以“[-10, -3, 0, 5, 9]”为例,构建BST。下面的图片给出了两颗BST,他们都是合法的,但我们的处理逻辑仅能够产生左边的形态。 我们列举BST的构建过程来说明,为什么我们的逻辑只能够产生左边的形态。首先,说明下我们采用的边界都是左闭右开的形式。arr=[-10, -3, 0, 5, 9]。|arr|=5, mid = (0+5)/2 = 2,取arr[2]=0作为中间元素,左半部分为[-10, -3],右半部分为[5, 9]。我们继续利用左半部分构建根节点0的左子树。计算|[-10, -3]| = 2,mid = (0+2)/2 = 1,取arr[1]=-3作为根节点。我们可以看到,因为左子树仅有两个元素,按照我们mid=(左边界索引+右边界索引)/2的处理方式会将第二个元素-3作为子树的根节点,而不是-10作为根节点。…

Read more

89. 格雷编码

题目描述 格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。 示例 1: 输入: 2 输出: [0,1,3,2] 解释: 00 – 0 01 – 1 11 – 3 10 – 2 对于给定的 n,其格雷编码序列并不唯一。 例如,[0,2,3,1] 也是一个有效的格雷编码序列。 00 – 0 10 – 2 11 – 3 01 – 1 示例 2: 输入: 0 输出: [0] 解释: 我们定义格雷编码序列必须以 0 开头。   给定编码总位数为 n 的格雷编码序列,其长度为 2n。当 n = 0 时,长度为 20 = 1。…

Read more