-
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…
-
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.…
-
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…
-
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作为根节点。…
-
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。…
-
61. 旋转链表
题目描述 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL https://leetcode-cn.com/problems/rotate-list/ 解法1 题目要求移动链表的k个元素，我们不妨先考虑只移动一个元素的情况。对于除了最后一个节点外的每个节点，我们都做以下动作。 备份下一个节点的值 将上一个节点的值覆盖到下一个节点 下一个节点的值作为“新的上一个节点的值” 移动到下一个节点 如果遇到最后一个节点，则将该节点的值覆盖到第一个节点上。下面我们用图来描述以下过程，下图以“1->2->3->4->5->NULL”为例。 上面的图描述了移动一个节点后的结果，当p指向倒数第二个节点时循环终止，此时nextBak=5。循环结束后，我们用nextBak覆盖掉头节点的值就完成了移动一个节点的过程。 我们还可以做一个优化，这个优化很容易想到。当移动次数k超过链表长度n时，我们只需要移动n%k个位置即可。下面的代码实现了上述全部过程。 解法2 上面的算法如果使用了优化，最多要移动n-1次单个元素。而移动单个元素的代价是移动链表中所有的元素，也就是n。因此，解法1的时间复杂度为O(n^2)。我们能不能只移动一次，来降低时间复杂度呢？ 我们通过计算找到链表的一个“切点”（图3的…
-
59. 螺旋矩阵 II
题目描述 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] https://leetcode-cn.com/problems/spiral-matrix-ii/ 解法1 本题目与“54. 螺旋矩阵”相似，但本题目给出矩阵的维度，要求生成螺旋矩阵。因为题目给出的是方阵，那么我们不需要考虑54题中内部出现孤立的一行或一列的情况。但会出现孤立一个元素的情况。 我们按照顺时针的顺序一次从左到右、从上到下遍历round圈即可。通过举例子的方式，我们可以算出round=ceil(n/2)。下面我们来说如何处理孤立元素的情况。例如上述3×3的方阵，当遍历完外面一圈的数字后将会只留下一个数字。那么如何判定循环遇到这种情况了呢？以3×3的矩阵为例，当round=1时中心只剩下一个元素，而矩阵遍历完一圈会消耗掉左右两个数字。因此，我们可以推测当n-2*round=1时，矩阵遍历到中心元素。这是一个corner case，我们需要独立处理这种情况，全部代码如下所示。
-
54. 螺旋矩阵
题目描述 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8,12,11,10,9,5,6,7] https://leetcode-cn.com/problems/spiral-matrix/ 解法1 我们首先举3个例子来分析如何实现矩阵的螺旋顺序遍历. 我们分别以3×3, 3×4与4×3的矩阵为例. 我们将遍历步骤分为水平从左到右遍历、垂直从上向下遍历、水平从右向左遍历与垂直从下向上遍历。如果遇到内部只包含一行或一列的情况，那么就全部遍历该行或列。 上面只是大概思路。当时现实时，我们会遇到另一个问题：“按照环形遍历几圈结束”？如果我们多举几个例子，可以容易地推测“圈数=ceil(max(row, col)/2)”. 另一个问题：“每一圈的起点是如何计算的？”我们可以从图上看出，每次我轮都从（0，0）、（1，1）、（2，2）……为起点遍历的。因此，我们取（round，round）作为遍历的起点。我们记当前的行号列号为（row，col），如果水平向右就遍历matrix[row][col++]，如果垂直向下就遍历matrix[row++][col]以此类推。经过上面的分析，我们就能编写出矩阵按照螺旋遍历的代码了。
-
43. 字符串相乘
题目描述 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 示例 1: 输入: num1 = “2”, num2 = “3” 输出: “6” 示例 2: 输入: num1 = “123”, num2 = “456” 输出: “56088” 说明： num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头，除非是数字 0 本身。 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。 https://leetcode-cn.com/problems/multiply-strings/ 解法1 首先, 我们观察示例2中123*456的竖式计算过程, 用乘数456的每一位与被乘数123相乘, 得到的乘积依次向左“移位”、相加. 123*6的乘积为738, 向左移动0位. 123*5的乘积为615, 向左移动1位. 123*4的乘积位492, 向左移动2位. 然后我们将这三个被向左移动了0位、1位、2位的数相加, 就模拟了乘法的过程.观察123*456竖式 1 2 3 x 4…
-
23. 合并K个排序链表
题目描述 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 https://leetcode-cn.com/problems/merge-k-sorted-lists/ 解法1 题目要求合并K个有序链表, 我们不妨先考虑合并两个有序链表. 为了便于操作, 我们创建一个头节点head, 该节点的value字段没有意义. 待合并的两个链表分别记为l1与l2, 为了保持合并后的链表仍然有序, 我们每次都从l1与l2中挑选当前最小的节点, 然后将其插入到头节点head. 现有链表l1, l2, 头节点head p = head if (l1.val < l2.val) { // 选取l1, l2当前最小的节点 p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; }…