332. 重新安排行程

题目描述 给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。 说明: 1. 如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前 2. 所有的机场都用三个大写字母表示(机场代码)。 3. 假定所有机票至少存在一种合理的行程。 示例 1: 输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] 输出: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”] 示例 2: 输入: [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]] 输出: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”] 解释: 另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]。但是它自然排序更大更靠后。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reconstruct-itinerary 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 首先,我们忽略按照字典顺序排列这一条件,那么这道题本质上求得的是有向图的欧拉路径。 严谨地说,一个连通有向图G有欧拉路径,指存在一个顶点,从它出发,沿着有向边的方向,可以不重复地遍历图中所有的边。 https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98 题目中给定的机场名称是图的顶点,行程是图的边。题目要求重新安排行程,从示例可以看出每个行程都必须用到且只用一次。对应到欧拉路径的定义,每条边都要走到,且不重复。那么,这道题就转化成了给定起点,求一条字典顺序最小的欧拉路径。为了引出解法,我们先放几个例子。 图1展示了一张顶点度数都为偶数的图,首先我们忽略掉按字典顺序输出的条件。我们可以看出,如果顶点度数为偶数,那么我们先从JFK到MUC再回JFK到ATL最后返回JFK,又或是JFK先到ATL再回JFK再去MUC再回JFK,都是合法的路径。如果按照字典顺序输出,我们优先访问字典顺序小的节点ATL即可。因此,我们使用贪心策略,优先访问字典顺序小的顶点。 图2这个例子可以看出,我们别无选择必须先从JFK到NRT再回JFK,最后到达KUL作为终点。如果我们按照字典顺序先到KUL,就进入了“死路”。但是上一个例子我们提到了,优先访问字典顺序小的顶点,那么我们第一次肯定是先到KUL,这就走不通了,那怎么解决呢?当我们采用DFS方式遍历图时,需要将访问到的节点逆序插入到结果集。因此第一个访问到的节点将出现在结果集最后面,而我们是以顺序的方式来查看结果。如果第一个访问的节点是“孤岛节点”,他会出现在结果集的最后。当我们顺序读取结果集时,这种“孤岛节点”是最后遇到的,是图遍历的终点,这样就没有问题了。 我们在图3绘制了算法执行过程,黑色实线表示图的边;红色实实线表示递归调用;绿色虚线表示递归调用返回;数字代表执行顺序;文字表示执行的操作,结果集的数字表示在第几步操作加入的。我们从JFK出发,沿着边到达KUL(因为KUL字典顺序比NRT小),然后KUL没有临接点,将它放入结果集(2),然后从KUL返回到达JFK,注意这个是通过调用栈返回而不是沿着边返回。然后从JFK出发沿着边到达NRT,因为NRT到JFK有返回边,沿着边再回到JFK。此时JFK的两个临接点都访问过了,我们将JFK加入结果集(6)。然后我们从JFK返回到NRT,这是从调用栈返回。然后NRT的临接点都访问过了,我们将NRT加入结果集(8),然后退栈回到JFK。JFK的所有临接点都访问过了,将JFK加入结果集(10),然后退栈,整个流程结束。…

Read more

113. 路径总和 II

题目描述 给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] https://leetcode-cn.com/problems/path-sum-ii/ 解法1 这道题是“112. 路径总和”的升级版本,在这道题我们需要把所有可能的解都存储下来并返回。为了记录路过的节点,我们使用一个变量List<Integer> path来存储路过的节点的值。我们将每个路过的节点的值都放入path中,如果走到叶节点发现是一条可行的路径(节点值之和等于sum),我们就复制path数组,然后放入到结果变量List<List<Integer>> ans。当从节点返回时,我们需要回溯以保证path变量的正确性。 上面的思路可以使用二叉树的先序遍历来实现。我们用题目给的case来描述执行过程:我们不断地向左走,找到一条路径”5->4->11->7″,path变量的内容依次变为[5], [5, 4], [5, 4, 11], [5, 4, 11, 7]。然后我们发现这条路径的和不等与sum,我们从节点7回溯,path变量从[5,4,11,7]变为[5,4,11],回到节点11走向它的右子树,此时path变量为[5,4,11,2],发现路径和与sum相等,复制path数组的到ans。因为我们需要复用path数组,所以不能直接调用ans.add(path),而是应该调用ans.add(new ArrayList<>(path)),创建path的副本并加入到ans中。 假设我们不考虑path数组复制的过程,那么时间复杂度为O(n)(因为要遍历所有节点),空间复杂度为O(n)(空间为调用栈开销)。

Read more

257. 二叉树的所有路径

题目描述 给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: [“1->2->5”, “1->3”] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 https://leetcode-cn.com/problems/binary-tree-paths/ 解法1 这道题目很简单,我们只需要先序遍历二叉树,把经过的节点都记录下来就可以了。唯一需要注意的是问题是,我们需要使用“->”连接路过的节点,当遇到叶节点时,我们不应该添加“->”。 我们要遍历全部节点,所以时间复杂度为O(n);当树为链表形态时,栈当深度最深,空间复杂度为O(n)。全部代码如下:

Read more

226. 翻转二叉树

题目描述 翻转一棵二叉树。 示例: 输入: 4 / \ 2 7 / \ / \ 1 3 6 9 输出: 4 / \ 7 2 / \ / \ 9 6 3 1 备注:这个问题是受到 Max Howell 的 原问题 启发的 : 谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。 https://leetcode-cn.com/problems/invert-binary-tree/ 解法1 这道题很简单,我们就把每一层节点的左子节点和右子节点交换,递归执行到叶节点即可。我们在图1绘制了节点交换的执行过程,首先我们交换跟节点4的左右子树,这里的交换不是指节点值的交换,而是引用的交换,这样才能让被交换节点的所有子树也都一同交换。接下来,我们递归交换节点7与2的左右子树。 时间复杂度为O(n),空间复杂度为O(n)。全部代码如下: 解法2 – 待续

Read more

352. 将数据流变为多个不相交区间

题目描述 给定一个非负整数的数据流输入 a1,a2,…,an,…,将到目前为止看到的数字总结为不相交的区间列表。 例如,假设数据流中的整数为 1,3,7,2,6,…,每次的总结为: [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7] 进阶:如果有很多合并,并且与数据流的大小相比,不相交区间的数量很小,该怎么办? 提示:特别感谢 @yunhong 提供了本问题和其测试用例。 https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/ 解法1 这道题我们使用TreeMap来解决。TreeMap的底层实现是R-B Tree,它的平衡性很好,对于get、put、remove、contains等操作都能够达到O(logn)的时间复杂度。我们使用的TreeMap的Key为插入操作的值,Value为能够表示插入值的最小区间。例如,我们向map中插入2,用[2,2]能够表示,用[1,3]能够表示,用[-1000,1000]也能够表示,但是我们选择最小的区间[2, 2],这样做能做到题目要求的“目前为止看到的数字总结为不相交的区间列表“。 这里我们还用到了TreeMap提供的两个重要的操作floorEntry与ceilingEntry。floorEntry(k)返回小于等于k的最大元组;ceilingEntry(k)返回大于等于k的最小元组。我们记leftValInterval = map.floorEntry(val),rightValInterval = map.ceilingEntry(val)。 我们将插入的值与区间已有的值的关系分为图1的6种情况。case1、case3、case5表示已有的区间能够表示插入的值,其实case5能够和case1或case3合并。case2与case4表示插入值与已有的区间连续,那么将已有的区间扩大一个单元就能够表示插入值,例如向[1, 3]插入4,向[3, 4]插入2。case6表示如果有了插入值,就能够使得已有的左右区间连续,例如向[1, 4]和[6, 9]插入5。 如果我们清晰的分析出来这些情况,编写代码就不难了。对于新插入的值val,我们首先判断他们在TreeMap中是否存在,如果存在则返回。否则,查询val的floorEntry与ceilingEntry。如果floorEntry的右边界等于val-1,就说明我们可以将val合并到floorEntry对应的区间,将区间扩大,如图1中case2所示。对于ceilingEntry的处理同理,如图1中case4所示。如果floorEntry的右边界等于val-1且ceilingEntry的左边界等于val+1,说明我们将val插入到这两个区间后,能够使得这两个区间连续,如图1中case6所示。如果不满足图1中任何一个case,说明val无法被TreeMap中已有的区间无法表示,我们需要向TreeMap插入新区间[val, val]。 全部代码如下所示,时间复杂度O(nlogn),空间复杂度O(n)。

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

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

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