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

15. 三数之和

题目描述 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] https://leetcode-cn.com/problems/3sum/ 解法1 首先对原数组nums进行排序, 用指针i指向nums的每个元素, 然后另指针j=i+1, k=|nums|-1. 指针j与k相向而行, 直到nums[i]+nums[j]+nums[k] == 0我们就找到了一个解, 此时需要继续相向而行直到k>=j. 将数组排序可以把算法的时间复杂度降低到O(n^2). 若不对数组排序, 为了寻找j, k使得nums[i]+nums[j]+nums[k] == 0, 需要使用双重循环遍历nums, 这样会使复杂度达到O(n^3). 因为题目要求“不可以包含重复的三元组”, 这就需要我们一旦找到符合条件的i, j, k. 就需要跳过nums中相同的元素(代码中被标记的部分), 以避免寻找重复的解. 例如…

Read more

9. 回文数

题目描述 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例 1: 输入: 121 输出: true 示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。进阶:你能不将整数转为字符串来解决这个问题吗? https://leetcode-cn.com/problems/palindrome-number/ 解法 我们按照进阶的要求,不将整数转化为字符串。代码模板中,变量x是int类型的。那么,将其反转结果使用long类型存放是不会溢出的。题目提到了一个case为“-121”,逆序读“121-”不是回文串。那么我们就可以推测,负数一定不是回文数。 我们按照“7.整数反转”这道题的技巧,判断反转后的数字与原数字是否一致来判定是否为回文数字即可。

Read more