本文解决的问题: 按主题归纳 贪心算法、动态规划、多维动态规划 相关高频题型与通用解法。
适用范围: LeetCode 中文站题目,示例主要使用 Java。
阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。
贪心算法 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
提示:
1 <= prices.length <= 105
0 <= prices[i] <= 104
示例 1:
1 2 3 4 输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
1 2 3 输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution { public int maxProfit (int prices[]) { int minprice = Integer.MAX_VALUE; int maxprofit = 0 ; for (int i = 0 ; i < prices.length; i++) { if (prices[i] < minprice) { minprice = prices[i]; } else if (prices[i] - minprice > maxprofit) { maxprofit = prices[i] - minprice; } } return maxprofit; } }
给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 105
示例 1:
1 2 3 输入:nums = [2,3,1,1,4] 输出:true 解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
1 2 3 输入:nums = [3,2,1,0,4] 输出:false 解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 public boolean canJump (int [] nums) { int max = 0 ; for (int i = 0 ; i < nums.length; i++) { max = Math.max(max, i + nums[i]); if (max <= i) { return false ; } } return true ; }
给定一个长度为 n 的 0 索引 整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
示例 1:
1 2 3 4 输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:
1 2 输入: nums = [2,3,0,1,4] 输出: 2
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 public int jump (int [] nums) { if (nums == null || nums.length == 0 ) { throw new IllegalArgumentException ("Input array is null or empty" ); } int n = nums.length; if (n == 1 ) { return 0 ; } int currentEnd = 0 ; int farthest = 0 ; int steps = 0 ; for (int i = 0 ; i < n - 1 ; i++) { farthest = Math.max(farthest, i + nums[i]); if (i == currentEnd) { steps++; currentEnd = farthest; if (currentEnd >= n - 1 ) { return steps; } } } return -1 ; }
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。例如,字符串 "ababcc" 能够被分为 ["abab", "cc"],但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
提示:
1 <= s.length <= 500
s 仅由小写英文字母组成
示例 1:
1 2 3 4 5 6 输入:s = "ababcbacadefegdehijhklij" 输出:[9,7,8] 解释: 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。
示例 2:
1 2 输入:s = "eccbbbbdec" 输出:[10]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public List<Integer> partitionLabels (String s) { int n=s.length(); int [] cnt=new int [26 ]; for (int i=0 ;i<n;i++) cnt[s.charAt(i)-'a' ]=i; List<Integer> ans=new ArrayList <>(); int end=0 ,start=0 ; for (int i=0 ;i<n;i++){ end=Math.max(cnt[s.charAt(i)-'a' ],end); if (end==i){ ans.add(end-start+1 ); start=end+1 ; } } return ans; }
动态规划 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
进阶: 提示:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
示例:
1 2 3 4 5 6 7 8 9 10 11 12 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。 示例 2: 输入:nums = [0,1,0,3,2,3] 输出:4 示例 3: 输入:nums = [7,7,7,7,7,7,7] 输出:1
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int lengthOfLIS (int [] nums) { if (nums.length == 0 ) { return 0 ; } int [] dp = new int [nums.length]; dp[0 ] = 1 ; int maxans = 1 ; for (int i = 1 ; i < nums.length; i++) { dp[i] = 1 ; for (int j = 0 ; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1 ); } } maxans = Math.max(maxans, dp[i]); } return maxans; }
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
示例:
1 2 3 4 5 6 7 8 9 10 11 12 示例 1: 输入:coins = [1, 2, 5], amount = 11 输出:3 解释:11 = 5 + 5 + 1 示例 2: 输入:coins = [2], amount = 3 输出:-1 示例 3: 输入:coins = [1], amount = 0 输出:0
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public int coinChange (int [] coins, int amount) { int max = amount + 1 ; int [] dp = new int [amount + 1 ]; Arrays.fill(dp, amount + 1 ); dp[0 ] = 0 ; for (int i = 0 ; i <= amount; i++) { for (int j = 0 ; j < coins.length; j++) { if (coins[j] <= i) { dp[i] = Math.min(dp[i - coins[j]] + 1 , dp[i]); } } } return dp[amount] == amount + 1 ? -1 : dp[amount]; }
给定一个非负整数 numRows, 生成「杨辉三角」的前 *numRows *行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1:
1 2 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
1 2 输入: numRows = 1 输出: [[1]]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public List<List<Integer>> generate (int numRows) { List<List<Integer>> ret = new ArrayList <List<Integer>>(); for (int i = 0 ; i < numRows; ++i) { List<Integer> row = new ArrayList <Integer>(); for (int j = 0 ; j <= i; ++j) { if (j == 0 || j == i) { row.add(1 ); } else { row.add(ret.get(i - 1 ).get(j - 1 ) + ret.get(i - 1 ).get(j)); } } ret.add(row); } return ret; } }
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 ** 不触动警报装置的情况下 ** ,一夜之内能够偷窃到的最高金额。
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 400
示例 1:
1 2 3 4 输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
1 2 3 4 输入:[2,7,9,3,1] 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
代码:
1 2 3 4 5 6 7 8 9 10 11 class Solution { public int rob (int [] nums) { int [] dp = new int [nums.length + 1 ]; dp[0 ] = 0 ; dp[1 ] = nums[0 ]; for (int i = 2 ; i <= nums.length; i++) { dp[i] = Math.max(dp[i - 1 ], dp[i - 2 ] + nums[i - 1 ]); } return dp[nums.length]; } }
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
提示:
示例 1:
1 2 3 输入:n = 12 输出:3 解释:12 = 4 + 4 + 4
示例 2:
1 2 3 输入:n = 13 输出:2 解释:13 = 4 + 9
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int numSquares (int n) { int [] dp = new int [n +1 ]; for (int i = 1 ; i <= n; i ++ ) { int l = Integer.MAX_VALUE; for (int j = 1 ; j *j <= i; j++) { l = Math.min(dp[i - j * j], l); } dp[i] = l + 1 ; } return dp[n]; } }
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
提示:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同
示例 1:
1 2 3 输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
1 2 3 4 输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意,你可以重复使用字典中的单词。
示例 3:
1 2 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class Solution { public boolean wordBreak (String s, List<String> wordDict) { Set<String> wordDictSet = new HashSet (wordDict); boolean [] dp = new boolean [s.length() + 1 ]; dp[0 ] = true ; for (int i = 1 ; i <= s.length(); i++) { for (int j = 0 ; j < i; j++) { if (dp[j] && wordDictSet.contains(s.substring(j, i))) { dp[i] = true ; break ; } } } return dp[s.length()]; } }
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
**子序列 **是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
提示:
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
示例 1:
1 2 3 输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
1 2 输入:nums = [0,1,0,3,2,3] 输出:4
示例 3:
1 2 输入:nums = [7,7,7,7,7,7,7] 输出:1
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public int lengthOfLIS (int [] nums) { int len = 1 , n = nums.length; if (n == 0 ) { return 0 ; } int [] d = new int [n + 1 ]; d[len] = nums[0 ]; for (int i = 1 ; i < n; ++i) { if (nums[i] > d[len]) { d[++len] = nums[i]; } else { int l = 1 , r = len, pos = 0 ; while (l <= r) { int mid = (l + r) >> 1 ; if (d[mid] < nums[i]) { pos = mid; l = mid + 1 ; } else { r = mid - 1 ; } } d[pos + 1 ] = nums[i]; } } return len; } }
给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续 子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
提示:
1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都 保证 是一个 32-位 整数
示例 1:
1 2 3 输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
1 2 3 输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 class Solution { public int maxProduct (int [] nums) { int length = nums.length; long [] maxF = new long [length]; long [] minF = new long [length]; for (int i = 0 ; i < length; i++) { maxF[i] = nums[i]; minF[i] = nums[i]; } for (int i = 1 ; i < length; ++i) { maxF[i] = Math.max(maxF[i - 1 ] * nums[i], Math.max(nums[i], minF[i - 1 ] * nums[i])); minF[i] = Math.min(minF[i - 1 ] * nums[i], Math.min(nums[i], maxF[i - 1 ] * nums[i])); if (minF[i] < (-1 << 31 )) { minF[i] = nums[i]; } } int ans = (int ) maxF[0 ]; for (int i = 1 ; i < length; ++i) { ans = Math.max(ans, (int ) maxF[i]); } return ans; } } class Solution {public : int maxProduct (vector<int >& nums) { long maxF = nums[0 ], minF = nums[0 ], ans = nums[0 ]; for (int i = 1 ; i < nums.size(); ++i) { long mx = maxF, mn = minF; maxF = max(mx * nums[i], max((long )nums[i], mn * nums[i])); minF = min(mn * nums[i], min((long )nums[i], mx * nums[i])); if (minF<INT_MIN) { minF=nums[i]; } ans = max(maxF, ans); } return ans; } };
给你一个 **只包含正整数 **的 **非空 **数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
示例 1:
1 2 3 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
1 2 3 输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 class Solution { public boolean canPartition (int [] nums) { int n = nums.length; if (n < 2 ) { return false ; } int sum = 0 , maxNum = 0 ; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } if (sum % 2 != 0 ) { return false ; } int target = sum / 2 ; if (maxNum > target) { return false ; } boolean [][] dp = new boolean [n][target + 1 ]; for (int i = 0 ; i < n; i++) { dp[i][0 ] = true ; } dp[0 ][nums[0 ]] = true ; for (int i = 1 ; i < n; i++) { int num = nums[i]; for (int j = 1 ; j <= target; j++) { if (j >= num) { dp[i][j] = dp[i - 1 ][j] | dp[i - 1 ][j - num]; } else { dp[i][j] = dp[i - 1 ][j]; } } } return dp[n - 1 ][target]; } } class Solution { public boolean canPartition (int [] nums) { int n = nums.length; if (n < 2 ) { return false ; } int sum = 0 , maxNum = 0 ; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } if (sum % 2 != 0 ) { return false ; } int target = sum / 2 ; if (maxNum > target) { return false ; } boolean [] dp = new boolean [target + 1 ]; dp[0 ] = true ; for (int i = 0 ; i < n; i++) { int num = nums[i]; for (int j = target; j >= num; --j) { dp[j] |= dp[j - num]; } } return dp[target]; } }
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
提示:
0 <= s.length <= 3 * 10^4
s[i] 为 '(' 或 ')'
示例 1:
1 2 3 输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"
示例 2:
1 2 3 输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"
示例 3:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public int longestValidParentheses (String s) { if (s == null || s.isEmpty()) { return 0 ; } int maxans = 0 ; Stack<Integer> stack = new Stack <>(); stack.push(-1 ); for (int i = 0 ; i < s.length(); i++) { char c = s.charAt(i); if (c == '(' ) { stack.push(i); } else if (c == ')' ) { if (!stack.isEmpty()) { stack.pop(); if (!stack.isEmpty()) { maxans = Math.max(maxans, i - stack.peek()); } else { stack.push(i); } } } else { continue ; } } return maxans; } }
多维动态规划 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
提示:
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 示例 1: 输入:text1 = "abcde", text2 = "ace" 输出:3 解释:最长公共子序列是 "ace" ,它的长度为 3 。 示例 2: 输入:text1 = "abc", text2 = "abc" 输出:3 解释:最长公共子序列是 "abc" ,它的长度为 3 。 示例 3: 输入:text1 = "abc", text2 = "def" 输出:0 解释:两个字符串没有公共子序列,返回 0 。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int longestCommonSubsequence (String text1, String text2) { int m = text1.length(); int n = text2.length(); int [][] dp = new int [m + 1 ][n + 1 ]; for (int i = 1 ; i <= m; i++) { for (int j = 1 ; j <= n; j++) { if (text1.charAt(i - 1 ) == text2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i][j -1 ]); } } } return dp[m][n]; }
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
提示:
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 输入:m = 3, n = 7 输出:28 示例 2: 输入:m = 3, n = 2 输出:3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下 示例 3: 输入:m = 7, n = 3 输出:28 示例 4: 输入:m = 3, n = 3 输出:6
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int uniquePaths (int m, int n) { int [][] dp = new int [m][n]; for (int i = 0 ; i < m; i++) { dp[i][0 ] = 1 ; } for (int i = 0 ; i < n; i++) { dp[0 ][i] = 1 ; } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ]; } } return dp[m - 1 ][n - 1 ]; }
给你一个字符串 s,找到 s 中最长的 回文 子串。
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
示例 1:
1 2 3 输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 public String longestPalindrome (String s) { int len = s.length(); if (len < 2 ) { return s; } int maxLen = 1 ; int begin = 0 ; boolean [][] dp = new boolean [len][len]; for (int i = 0 ; i < len; i++) { dp[i][i] = true ; } char [] charArray = s.toCharArray(); for (int L = 2 ; L <= len; L++) { for (int i = 0 ; i < len; i++) { int j = L + i - 1 ; if (j >= len) { break ; } if (charArray[i] != charArray[j]) { dp[i][j] = false ; } else { if (j - i < 3 ) { dp[i][j] = true ; } else { dp[i][j] = dp[i + 1 ][j - 1 ]; } } if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1 ; begin = i; } } } return s.substring(begin, begin + maxLen); }
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明: 每次只能向下或者向右移动一步。
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
示例 1:
1 2 3 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
1 2 输入:grid = [[1,2,3],[4,5,6]] 输出:12
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int minPathSum (int [][] grid) { if (grid == null || grid.length == 0 || grid[0 ].length == 0 ) { return 0 ; } int rows = grid.length, columns = grid[0 ].length; int [][] dp = new int [rows][columns]; dp[0 ][0 ] = grid[0 ][0 ]; for (int i = 1 ; i < rows; i++) { dp[i][0 ] = dp[i - 1 ][0 ] + grid[i][0 ]; } for (int j = 1 ; j < columns; j++) { dp[0 ][j] = dp[0 ][j - 1 ] + grid[0 ][j]; } for (int i = 1 ; i < rows; i++) { for (int j = 1 ; j < columns; j++) { dp[i][j] = Math.min(dp[i - 1 ][j], dp[i][j - 1 ]) + grid[i][j]; } } return dp[rows - 1 ][columns - 1 ]; } }
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
提示:
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
示例 1:
1 2 3 4 5 6 输入:word1 = "horse", word2 = "ros" 输出:3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2:
1 2 3 4 5 6 7 8 输入:word1 = "intention", word2 = "execution" 输出:5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public int minDistance (String word1, String word2) { int n = word1.length(); int m = word2.length(); if (n * m == 0 ) { return n + m; } int [][] D = new int [n + 1 ][m + 1 ]; for (int i = 0 ; i < n + 1 ; i++) { D[i][0 ] = i; } for (int j = 0 ; j < m + 1 ; j++) { D[0 ][j] = j; } for (int i = 1 ; i < n + 1 ; i++) { for (int j = 1 ; j < m + 1 ; j++) { int left = D[i - 1 ][j] + 1 ; int down = D[i][j - 1 ] + 1 ; int left_down = D[i - 1 ][j - 1 ]; if (word1.charAt(i - 1 ) != word2.charAt(j - 1 )) { left_down += 1 ; } D[i][j] = Math.min(left, Math.min(down, left_down)); } } return D[n][m]; } }
参考资料