312. 戳气球

题目描述 有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。 求所能获得硬币的最大数量。 说明: 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 示例: 输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []   coins = 315 + 358…

Read more

174. 地下城游戏

题目描述 一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。 有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。 为了尽快到达公主,骑士决定每次只向右或向下移动一步。 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 例如,考虑到如下布局的地下城,如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7。 -2 (K) -3 3 -5 -10 1 10 30 -5 (P) 说明: 骑士的健康点数没有上限。 任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/dungeon-game 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DP 题目给定的数组dungeon存放了走入每个房间造成的血量变化,为了救出公主,要求到达右下角(P)时扣除外血量至少为1,因此我们可以从P点逆行回到起点K,求出起点K要求的最少血量。我们定义一个二维数组dp[|dungeon|+1][|dungeon[0]|+1],dp数组比原数组“大了一圈“,这样做能够方便我们统一地处理逻辑,否则需要判断边界条件。到达P点以后还会扣除或者增加血量,所以走过P点到达右方或下方的血量至少需要1。 图1展示了题目的例子计算dp数组后的结果。要想求出到达位置i,j需要的最少血量,那么可以从位置i+1,j与i,j+1逆推而来。例如dp[2][1]=1,dp[1][2]=5,dungeon[1][1] = -10,说明我们只需要在位置1,1有血量11,就能够到达[2][1]。还有一点要注意,血量不可能为负数。例如在2,1处能够加血30,那我们不能说到达2,1时只需要-29点血量,然后再给我加上30变成1,这是不对的,血量不能为负值。所以在计算完min(dp[i+1][j], dp[i][j+1])+dungeon[i][j]还需要对1取最大。 该解法时间复杂度为O(m*n),m与n为dungeon数组长与宽。全部代码如下:

Read more

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