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

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的…

Read more

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,我们需要独立处理这种情况,全部代码如下所示。

Read more

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]以此类推。经过上面的分析,我们就能编写出矩阵按照螺旋遍历的代码了。

Read more

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…

Read more

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; }…

Read more

16. 最接近的三数之和

题目描述 给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). https://leetcode-cn.com/problems/3sum-closest/ 解法1 这道题目与三数之和非常相似, 不同之处在于本题要求解的是最接近目标值的三数之和而不要求三数之和为0. 另一个不同点是, 题目给定的输入能保证只存在唯一答案. 我们还是使用“三数之和”解法1的做法, 首先将数组nums排序,以降低内层循环的时间复杂度. 变量i依次访问数组nums的每个元素, 作为外层循环. 内层循环中, 我们用j, k指针分别指向i之后数组的两端. 我们将nums[i]+nums[j]+nums[k]与target之差的绝对值记为diff, diff的初值为Integer.MAX_VALUE. 如果nums[i]+nums[j]+nums[k]与target之差的绝对值小于diff, 则更新diff. 题目要求nums[i]+nums[j]+nums[k]的和, 那么我们除了记录diff之外, 还应该记录与diff对应的三个数之和, 我们计作threeSum. 现在我们分析下如何维护变量j与k. 如果三个数之和小于target, 那么说明我们要找更大的数才能使三数之和更接近target, 所以j自增1. 如果三数之和大于target, 说明我们从右边选的数太大了, 应该k自减1. 如果三数之和与target相等, 那么三数之和与target的差距是0, 这是最接近target的情况了. 注意, 如果遇到这种情况,…

Read more