1. 零钱兑换
- 零钱兑换 (Medium)
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
输入: coins = [2], amount = 3
输出: -1
题目描述：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
时间复杂度：O(Sn)，其中 SS 是金额，nn 是面额数。我们一共需要计算 O(S) 个状态，SS 为题目所给的总金额。对于每个状态，每次需要枚举 nn 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
空间复杂度：O(S)。DP 数组需要开长度为总金额 SS 的空间。
public int coinChange(int[] coins, int amount) {
int dp[] = new int[amount+1];
Arrays.fill(dp,amount+1);
dp[0] = 0;
for(int i = 1; i <=amount; i++){
for(int coin : coins){
if(!(coin > i)){
dp[i] = Math.min(dp[i],dp[i-coin]+1);
}
}
}
return dp[amount] == amount+1 ? -1 : dp[amount];
}
2. 最长上升子序列
- 最长上升子序列
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。
时间复杂度：时间复杂度 O(N^2)
public int lengthOfLIS(int[] nums) {
int[] dp = new int [nums.length];
Arrays.fill(dp,1);
if(nums.length==0){
return 0 ;
}
for(int i =0; i < nums.length; i++){
for(int j=0; j< i; j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
}
int max = 1;
for(int num : dp){
max = Math.max(max, num);
}
return max;
}
3. 最大子序和
- 最大子序和
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
时间复杂度：时间复杂度是 O(N)，空间复杂度也是 O(N)
public int maxSubArray(int[] nums) {
int dp[] = new int[nums.length];
dp[0] = nums[0];
for(int i =1; i< nums.length; i++){
dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
}
int sum=Integer.MIN_VALUE;
for(int num :dp){
sum = Math.max(sum,num);
}
return sum;
}
4. 分割等和子集
- 分割等和子集
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
时间复杂度：时间复杂度是 O(N)，空间复杂度也是 O(N)
public boolean canPartition(int[] nums) {
int sum = 0;
for( int num :nums){
sum+=num;
}
int mid = sum/2;
if (sum % 2 != 0) return false;
boolean dp[][] = new boolean[nums.length+1][mid+1];
for (int i = 0; i <= nums.length; i++)
dp[i][0] = true;
for(int i =1;i<=nums.length;i++){
for(int j=1;j<=mid;j++){
if(j<nums[i-1]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
}
}
}
return dp[nums.length][mid];
}
5. 零钱兑换 II
- 零钱兑换 II
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
题目描述：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
时间复杂度：时间复杂度是 O(N)，空间复杂度也是 O(N)
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length+1][amount+1];
for(int i =0;i<=coins.length;i++){
dp[i][0]=1;
}
for(int i = 1;i<=coins.length;i++){
for(int j = 1;j <= amount; j++){
if(j>=coins[i-1]){
dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[coins.length][amount];
}
6. 编辑距离
- 编辑距离
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
题目描述：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
时间复杂度：时间复杂度是 O(N)，空间复杂度也是 O(N)
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(int i =1;i<=word1.length();i++){
dp[i][0] = i;
}
for(int i =1;i<=word2.length();i++){
dp[0][i] = i;
}
for(int i = 1;i<=word1.length();i++){
for(int j =1;j<=word2.length();j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));
}
}
}
return dp[word1.length()][word2.length()];
}
7. 最长公共子序列
- 最长公共子序列
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length()+1][text2.length()+1];
for(int i =1;i <=text1.length();i++){
for(int j =1;j <=text2.length();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[text1.length()][text2.length()];
}
8. 最长回文子序列
- 最长回文子序列
示例 1:
输入:
"bbbab"
输出:
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:
"cbbd"
输出:
一个可能的最长回文子序列为 "bb"。
题目描述：给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for(int i=n-1;i>=0;i--){
for(int j =i+1;j<n;j++){
if(s.charAt(i)==s.charAt(j)){
dp[i][j] = dp[i+1][j-1]+2;
}else{
dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][s.length()-1];
}
9. 最长回文子串
- 最长回文子串
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
时间复杂度：O(n^2)，其中 n 是字符串的长度。长度为 111 和 222 的回文中心分别有 n 和 n−1个，每个回文中心最多会向外扩展 O(n) 次。
空间复杂度：O(1)。
public String longestPalindrome(String s) {
if(s.length()<2){
return s;
}
String maxStr = "";
for(int i =0; i < s.length(); i++){
String odd = help(s,i,i);
String even = help(s,i,i+1);
maxStr = odd.length()>maxStr.length()?odd:maxStr;
maxStr = even.length()>maxStr.length()?even:maxStr;
}
return maxStr;
}
String help(String s, int i, int j){
while(i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)){
i--;
j++;
}
return s.substring(i+1,i+1+j-i-1);
}
网友评论