39. 组合总和

题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [   [2,2,2,2],   [2,3,3],   [3,5] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 在上一篇文章“代码模版-排列与组合”我们介绍了排列与组合的实现方法,在这道题中,我们将会在组合算法上进行一些修改来解这道题目。我们先观察下组合算法的实现。 在这道题目中,要求数字可以重复选取,但是上面的代码每次都会选取新的一个数字。我们将递归调用combination(arr, depth + 1, i + 1, curr, result)改成combination(arr, depth + 1, i, curr,…

Read more

代码模版 – 排列与组合

有的时候题目想不出来,或者只能用搜索来解决(如Leetcode – 39题),我们就可以用排列/组合搜索答案。下面的排列与组合模板都使用DFS来实现,非常易懂且方便记忆。 1. 排列 方法private void permutation(int[] arr, int depth, int[] curr, boolean[] visited, List<int[]> result)实现了求arr的所有排列,并且将结果保存的result中。depth表示目前正在填充curr的第几位,visited数组记录了之前已经访问的元素。在for循环中,我们遍历每个之前没有访问过位置,并在visited标记为true,防止下一次递归调用访问同一元素。当depth达到数组arr的长度时,我们复制curr的内容到result中。 2. 组合 这里的组合指的是从n个元素中挑选c个元素,而不考虑元素的顺序。方法void combination(int[] arr, int depth, int start, int[] curr, List<int[]> result)实现了从arr中挑选|curr|个元素。depth表示我们正在填充curr的第几位,start参数表明我们从arr中第几个位置开始挑选元素。与排列算法相比,我们不需要visited数组。因为我们总是从start之后挑选元素,所以不会出现挑选重复元素的情况。

Read more

307. 区域和检索 – 数组可修改

题目描述 给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。 update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。 示例: Given nums = [1, 3, 5] sumRange(0, 2) -> 9update(1, 2)sumRange(0, 2) -> 8说明: 数组仅可以在 update 函数下进行修改。 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/range-sum-query-mutable著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Prefix sum 我们可以预先计算出前缀和存储在数组中,prefix[i] = num[0]+…+nums[i]。这样,当需要求得范围[i,j]的和时,我们可以通过prefix[j]-prefix[i-1]在O(1)的时间计算出结果。但是当nums[i]发生更新操作,那么我们不得不重新计算prefix[i]之后的前缀和,时间复杂度为O(n)。 全部代码如下: 解法2 – Fenwick Tree(树状数组) Fenwick Tree也称为树状数组,它可以在O(logn)的时间得到任意前缀和,并同时支持在O(logn)时间内支持动态单点值的修改。空间复杂度O(n)。为了实现Fenwick Tree,我们需要一个函数lowbit(x),他是用来求得数值x最低位第一个1所代表到数值,例如x = 0110,lowbit(x) = 0010; x = 0101, lowbit(x) = 0001。…

Read more

337. 打家劫舍 III

题目描述 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。 计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。 示例 1: 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 示例 2: 输入: [3,4,5,1,3,null,1]   3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9. 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/house-robber-iii著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1…

Read more

110. 平衡二叉树

题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 https://leetcode-cn.com/problems/balanced-binary-tree/ 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/balanced-binary-tree著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Top-down 我们就按照定义来,求得节点左右子树的高度(在实现时用的深度),如果相差不超过1,这个子树就是平衡二叉树。我们递归地对每一个节点都进行这样的判断,直到最后轮到判断跟节点。如果跟节点也满足这样的定义,那么这棵树就是平衡二叉树。 对于求得一个顶点的深度的算法,时间复杂度为O(n)。但是二叉树有n个节点,总体时间复杂度为O(n^2)。如果树是链式结构,那么空间复杂度最高,为O(n)。全部代码如下: 解法2 – Bottom-up Bottom-up算法自下而上地求得每个顶点的高度,根据左右子树的高度差判断是否平衡。如果某个顶点的左右子树的高度之差已经超过1了,那么我们也不必要继续向上判断了。这样,我们发现有任何一颗子树是不平衡的,我们就可以提前终止算法。就算了所有的子树都是平衡点,所有顶点也只扫描一次。 因此Bottom-up算法的时间复杂度O(n),空间复杂度O(n)。全部代码如下:

Read more

104. 二叉树的最大深度

题目描述 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DFS 这是道经典的BinaryTree的模版题,我们声明函数private int helper(TreeNode node, int depth) ,当node是叶子结点时返回depth,如果node的左子树非空则递归调用helper(node.left, depth+1);当node的右子树非空,则递归调用helper(node.right, depth+1); 当node为空,则返回0。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – BFS 当然这道题也可以用BFS来做,我们需要一个队列,还有一个Map<TreeNode, Integer>用来存放节点对应的深度。如果node的左子树非空,就将它如队列,然后depth+1放入map中;右子树同理。然后还需要一个存放答案的变量ans,如果取出节点的深度大于ans就更新它,最后返回ans。 复杂度和解法1相同,但因为用到了Map导致overhead比较大,实际运行时间比解法1慢很多。全部代码如下:

Read more

133. 克隆图

题目描述 给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。 示例: 输入: {“$id”:”1″,”neighbors”:[{“$id”:”2″,”neighbors”:[{“$ref”:”1″},{“$id”:”3″,”neighbors”:[{“$ref”:”2″},{“$id”:”4″,”neighbors”:[{“$ref”:”3″},{“$ref”:”1″}],”val”:4}],”val”:3}],”val”:2},{“$ref”:”4″}],”val”:1} 解释: 节点 1 的值是 1,它有两个邻居:节点 2 和 4 。 节点 2 的值是 2,它有两个邻居:节点 1 和 3 。 节点 3 的值是 3,它有两个邻居:节点 2 和 4 。 节点 4 的值是 4,它有两个邻居:节点 1 和 3 。 提示: 节点数介于 1 到 100 之间。 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点p 的邻居。 必须将给定节点的拷贝作为对克隆图的引用返回。 来源:力扣(LeetCode)…

Read more

684. 冗余连接

题目描述 在本问题中, 树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点u 和v的无向图的边。 返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。 示例 1: 输入: [[1,2], [1,3], [2,3]] 输出: [2,3] 解释: 给定的无向图为: 1 / \ 2 – 3 示例 2: 输入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4] 解释: 给定的无向图为: 5 – 1 – 2 | | 4 -…

Read more

111. 二叉树的最小深度

题目描述 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最小深度  2. 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DFS 解法1简单的很,我们就用DFS遍历二叉树,声明一个辅助函数用来遍历private int helper(TreeNode node, int depth)。node是当前节点,depth是当前节点深度。如果当前节点是叶节点,就返回depth;如果node左子树非空,就递归遍历左子树求最小深度;如果node右子树非空,就递归遍历右子树求最小深度,然后取左右子树最小深度的min并返回。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – BFS 解法2用队列实现BFS,但是还需要用一个辅助的Map<TreeNode, Integer>记录节点与它的深度。首先从队列出队一个节点,然后从Map取出该节点深度currLevel。每当下一层的节点入队,就将被入队的节点作为key,currLevel+1作为value存入Map中。当发现出队的节点为叶节点时,就终止BFS过程,返回currLevel作为结果。 BFS遍历的好处是,如果首先碰到了叶节点就可以终止遍历过程。而DFS方式需要遍历所有节点才能够知道最小深度。但是最坏情况下BFS和DFS的时间复杂度是一样的,此外BFS还需要用Map存储节点与深度的对应关系,耗费额外的空间;而访问Map还会有一些开销,因此性能并没有DFS好。

Read more

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