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

188. 买卖股票的最佳时机 IV

题目描述 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。 示例 2: 输入: [3,2,6,5,0,3], k = 2 输出: 7 解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润…

Read more

45. 跳跃游戏 II

题目描述 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。 https://leetcode-cn.com/problems/jump-game-ii/ 解法1 解法1是采用贪心解法,解法1很啰嗦,目的是尽可能让我们容易理解。策略是这样的,我们计算nums[i] + i,物理意义代表从当前出发能到达的最远位置。我们尽可能使下一跳落到较远的位置,这样才能使得跳到终点的步数最少。 我们以例子“[2,3,1,1,4]”为例,计算nums[i]+i -> nums[i],nums被更新为“[2,4,3,4,8]”,代表我站在第0个位置上,最远能跳到第2个位置上;站在第1个位置上,最远跳到第4个位置上(也就是终点),站在第2个位置上,最远能跳到第3个位置上……以此类推。那我们从0出发,最远能跳到第二个位置上,也就是说我们可以跳到第1个位置,也可以跳到第2个位置上。我们发现从第一个位置出发最远能到4,而从第2个位置出发最远能跳到3。我们刚刚说过,要保证下一跳落到较远到位置,所以我们选择从0跳到1,接着我们发现从1可以直接到终点,那么我们从1跳到4。 注意,不要落入一个误区:不是使本跳跳的尽可能远,而是从本跳出发,选择一个落脚点,从这个落脚点出发到达的尽可能远。以上面的为例,第一步我们从0跳到2虽然走的比0跳到1远,但是接下来从2出发最多只能到达3,而从1出发我们直接能到达终点。 根据上面的分析,我们能写出如下的代码,时间复杂度与空间复杂度均为O(n)。虽然这个代码包含双重循环,但是内层循环会改变外层循环的计数器,实际上只扫描了一次。 其实,上面的代码还可以继续优化,我们不需第一次扫描,将第一次扫描的逻辑合并到第二次扫描。 解法2 解法2很巧妙,但思想和解法1是差不多的。我们首先计算从当前位置i出发能到到达的最远距离,记为upperBound;我们还使用了另一个变量lastStepBound,记录从上一跳出发能到达的最远位置,最后我们使用res变量记录花费了几跳。我们接下来从i+1出发,继续更新upperBound,直到走到lastStepBound,然后我们更新lastStepBound = upperBound. 我们从i+1出发走到 lastStepBound,是为了寻找更远的下一跳。 我们以“[2,3,1,1,4]”为例,初始化lastStepBound = 0, upperBound = 0. 我们从i=0出发,更新upperBound = max(upperBound, i+nums[i]) = 2,然后我们更新lastStepBound = 2(第一跳起跳, res++),表示我们从0出发最远能到达2。接下来走到i=1更新upperBound = 4;走到i=2发现最远能到达3,则不更新upperBound。这时我们碰到了lastStepBound,得知我们下一跳最远能跳到4,另lastStepBound=upperBound(第一跳落地,第二跳起跳 res++)。当i=3时更新upperBound失败,此时i…

Read more

55. 跳跃游戏

题目描述 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。 https://leetcode-cn.com/problems/jump-game/ 解法1 解法1的方法是一种暴力搜索的方法,既然给出了每个位置能跳跃的最大距离,那我们就挨个尝试能落下的位置,然后以该位置为起点继续重复此过程看看能不能到达末尾。这是一种DFS方法,时间复杂度为O(n^2)。这种做法属于“人思考的少,机器思考的多”,另外代码量也很大,所以不推荐这种做法。 解法2 解法2采用贪心的做法,设置一个变量currMax,表示从当前位置之前的任意一点出发能走到的最远的位置。我们遍历每一个位置,判断i是否大于currMax。如果i>currMax,物理意义表示从i之前的任意位置出发,都到达不了i,则肯定到达不了i之后的任何位置,返回false即可。否则,我们更新currMax = max(currMax, i + nums[i])。 解法3 解法3采用回溯的方法,我们从终点向前回溯,看看终点之前有没有一个点i至少能够到达终点的,如果存在则回溯到点i;我们再看看i之前有没有一个点至少能够到达点i,如果存在我们继续回溯……直到看看能不能回溯到起点。如果能够回溯到起点,那我们从起点正向出发也一定能够到达终点;反之如果不能回溯到起点,那我们就没办法到达终点。

Read more

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…

Read more