代码编织梦想

目录

leetcode5.最长回文子串

leetcode718.最长重复子数组

leetcode300.最长递归子序列

leetcode72.编辑距离

leetcode10.正则表达式匹配

leetcode122.买卖股票的最佳时机II

leetcode714.买卖股票的最佳时机含手续费

leetcode121.买卖股票的最佳时机

leetcode123.买卖股票的最佳时机III

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

leetcode309.买卖股票的最佳时机含冷冻期

leetcode322.零钱兑换


字符串大多都二维的,见多了就会了。

i:长度为i或者以i结尾。

leetcode5.最长回文子串

5. 最长回文子串 - 力扣(LeetCode)

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成
class Solution {
 /* 动态规划三部曲
        s = "cba"
        dp[i][j]:字符串[i...j]是否为回文串=》长度:j - i + 1
        2、关系式
        s[i] == s[j]=>dp[i][j] = dp[i+1][j-1]=>
        s[i] != s[j] =>dp[i][j] false。

        3、初始值
        dp[0..i][0] = true.
*/
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        char[] c = s.toCharArray();
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0;
        int end = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (c[i] != c[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i + 1 < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}

leetcode718.最长重复子数组

718. 最长重复子数组 - 力扣(LeetCode)

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 

示例 1:

输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3,2,1] 。

示例 2:

输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出:5

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100
//最长重复子数组和最长重复子串是同一种问题,我们当作字符串来做哦
/*
定义:dp[i][j]:s1中以i结尾的子数组和s2中以j结尾的最长公共子数组的长度

关系式:s1[i] == s2[j] => dp[i][j] = dp[i - 1][j - 1] + 1; 
              !=      => dp[i][j] = 0;

初始化:dp[0][j] = 0  dp[i][0] = 0   0表示的是第0个字符,即没有字符,表示第i个字符
*/
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;

        int[][] dp = new int[n1+1][n2+1];//int的初始值本身就是0,所以不用初始化了
        int max = 0;

        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                if(nums1[i-1] == nums2[j-1]){
                   //这里不太懂的话可以自己画两个字符串数组举例子
                    dp[i][j] = dp[i-1][j-1] + 1;
                }

                max = Math.max(max, dp[i][j]);
            }
        }

        return max;
    }
}

leetcode300.最长递归子序列

300. 最长递增子序列 - 力扣(LeetCode)

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 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 <= nums.length <= 2500
  • -104 <= nums[i] <= 10的4次方
/*
 dp[i] = 以s[i]结尾的数组最长子序列为dp[i]
 j: 0...j - 1  s[j] < s[i]
 dp[i] = max(dp[j] + 1, dp[i])
 dp[0] = 1
*/
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        dp[0] = 1;
        int max = 1;

        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = i - 1; j >= 0; j--){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

leetcode72.编辑距离

72. 编辑距离 - 力扣(LeetCode)

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成
class Solution {
    /*
    1.dp[i][j]:表示长度为 i 的word1(0...i)转为长度为 j 的word2(0...j)所需要的最少操作次数为dp[i][j]。
    2. 关系式
            word1 = hor
            word2 =  ho
        dp[i][j] = 
        (1). w1[i] == w2[j]=>dp[i][j] = dp[i-1][j-1]。
        (2).如果 w1[i] != w2[j]
        a.插入:dp[i][j] = dp[i][j-1] + 1。
        b.删除 :dp[i][j] = dp[i-1][j] + 1
        c.替换: dp[i][j] = dp[i-1][j-1] + 1.

        dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

    3、初始值
    dp[0][j] = j
    dp[i][0] = i
    */
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();

        int[][] dp = new int[n1+1][n2+1];

        // 初始化
        for(int i = 0; i <= n1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n2; j++){
            dp[0][j] = j;
        }

        //
        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                //如果最后的两个字符相等
                if(word1.charAt(i-1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    //min()方法只能比较两个数 所以叠加
                    dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                }
            }
        }

        return dp[n1][n2];
    }

}

leetcode10.正则表达式匹配

10. 正则表达式匹配 - 力扣(LeetCode)

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖整个字符串 s的,而不是部分字符串。

示例 1:

输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa", p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:s = "ab", p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。

提示:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母,以及字符 . 和 *
  • 保证每次出现字符 * 时,前面都匹配到有效的字符
class Solution {
    /*
    1、dp[i][j]:表示字符串长度为 i 的字符s和长度为 j 字符p是否匹配。

    s = "aaaa"
    p = "abca*"

    2、求关系式 dp[i][j]
    在匹配的时候,肯定需要关注 s[i] 和 p[j]
    (1)、如果 p[j] 是普通字符:s[i] == p[j]=>dp[i][j] = dp[i-1][j-1]
                           s[i] != p[j]=>dp[i][j] = false.
    (2)、如果 p[j] = '.' =>dp[i][j] = dp[i-1][j-1]

    (3)、如果 p[j] = '*',那么我们需要关注p[j-1]
        a.如果 P[j-1] != s[i] => dp[i][j] = dp[i][j-2]
        b.如果 p[j-1] == s[i]:
            1).匹配0个=》dp[i][j] = dp[i][j-2]
            2).匹配1个=〉dp[i][j] = dp[i-1][j-2]
            3).匹配多个,相当于抵消了s[i]=》dp[i][j] = dp[i-1][j]。

    dp[i][j] = dp[i][j-2] or dp[i-1][j-2] or dp[i-1][j]

    3、求初始值
    dp[0][j] = dp[0][j] = dp[0][j-2]。
    dp[0][0] = true.



    return dp[n][m]
    */
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();

        boolean[][] dp = new boolean[n+1][m+1];
        // 初始值
        dp[0][0] = true;
        for(int j = 2; j <= m; j++){
            if(p.charAt(j - 1) == '*'){
                dp[0][j] = dp[0][j-2];
            }
        }

        // 进入正题
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                // 如果不是 *
                if(p.charAt(j-1) != '*'){
                    if(p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i-1)){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }else{
                    // 如果是 *
                    // 匹配0个
                    if(p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.'){
                        dp[i][j] = dp[i][j-2];
                    }else{
                        dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
}

leetcode122.买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

 

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买,然后在同一天出售。

返回 你能获得的最大利润 。

示例 1:

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

示例 2:

输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。

示例 3:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。

提示:

  • 1 <= prices.length <= 3 * 10的4次方
  • 0 <= prices[i] <= 10的4次方
class Solution {
    /*
    1、dp[i][j]:表示在第 i 天结束后,股票的状态为 j,此时我们手上拥有的最大现金为 dp[i][j]。
    j = 0:表示不持有股票
    j = 1:表示持有股票
    最终要求的:dp[n-1][0]。

    2、求关系式
    (1). dp[i][0]:第 i 天结束后,我们不持有股票,且现金为 dp[i][0]。
        a. 第 i 天什么也没操作:dp[i][0] = dp[i-1][0].
        b. 第 i 天卖出了股票:dp[i][0] = dp[i-1][1] + price[i]。
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]);

    (2). dp[i][1]:第 i 天结束后,我们持有股票,且现金为 dp[i][1]。

        a. 第 i 天什么也没操作:dp[i][1] = dp[i-1][1].
        b. 第 i 天买出了股票:dp[i][1] = dp[i-1][0] - price[i].

    dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i]);

    3、初始值
    dp[0][0] = 0;
    dp[0][1] = -price[0].

    */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];

        dp[0][1] = -prices[0];

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }
}

leetcode714.买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)

给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

示例 1:

输入:prices = [1, 3, 2, 8, 4, 9], fee = 2
输出:8
解释:能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2:

输入:prices = [1,3,7,5,10,3], fee = 3
输出:6

提示:

  • 1 <= prices.length <= 5 * 10的4次方
  • 1 <= prices[i] < 5 * 10的4次方
  • 0 <= fee < 5 * 10的4次方
class Solution {
    /*
    1、dp[i][j]:表示在第 i 天结束后,股票的状态为 j,此时我们手上拥有的最大现金为 dp[i][j]。
    j = 0:表示不持有股票
    j = 1:表示持有股票
    最终要求的:dp[n-1][0]。

    2、求关系式
    (1). dp[i][0]:第 i 天结束后,我们不持有股票,且现金为 dp[i][0]。
        a. 第 i 天什么也没操作:dp[i][0] = dp[i-1][0].
        b. 第 i 天卖出了股票:dp[i][0] = dp[i-1][1] + price[i] - fee。(唯一的区别)
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]);

    (2). dp[i][1]:第 i 天结束后,我们持有股票,且现金为 dp[i][1]。

        a. 第 i 天什么也没操作:dp[i][1] = dp[i-1][1].
        b. 第 i 天买进了股票:dp[i][1] = dp[i-1][0] - price[i].

    dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i]);

    3、初始值
    dp[0][0] = 0;
    dp[0][1] = -price[0].

    */
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];

        dp[0][1] = -prices[0];

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }

}

leetcode121.买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣(LeetCode)

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4
class Solution {

    /*
    1.什么也没有操作
    2.第一次买进来
    3.第一次卖出去

    dp[i][0]:什么也没有操作过=》dp[i][0] = 0
    dp[i][1]:在第 i 天结束后,第一次买进股票,此时最大现金为 dp[i][1]
    dp[i][2]:在第 i 天结束后,第一次卖出股票,此时最大现金为 dp[i][2]

    2、求关系式
    (1). dp[i][1]:第 i 天结束后,第一次买进股票,此时最大现金为 dp[i][1]。
        a. 第 i 天什么也没操作:dp[i][1] = dp[i-1][1]。
        b. 第 i 天第一次买进了股票:dp[i][0] = - price[i]。
    dp[i][1] = max(dp[i-1][1], - price[i]);

    (2). dp[i][2]:在第 i 天结束后,第一次卖出股票,此时最大现金为 dp[i][2]

        a. 第 i 天什么也没操作:dp[i][2] = dp[i-1][2].
        b. 第 i 天第一次卖出了股票:dp[i][2] = dp[i-1][1] + price[i].

    dp[i][2] = max(dp[i-1][2], dp[i-1][1] + price[i]);

    3、初始值
    dp[0][0] = 0;
    dp[0][1] = -price[0].

    */

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];

        dp[0][1] = -prices[0];

        for(int i = 1; i < n; i++){
            dp[i][1] = Math.max(dp[i-1][1], - prices[i]);
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
        }

        return dp[n-1][2];
    }
}

leetcode123.买卖股票的最佳时机III

 123. 买卖股票的最佳时机 III - 力扣(LeetCode)

 

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
     随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入:prices = [7,6,4,3,1] 
输出:0 
解释:在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4:

输入:prices = [1]
输出:0

提示:

  • 1 <= prices.length <= 10的5次方
  • 0 <= prices[i] <= 10的5次方
class Solution {

    /*
    1.什么也没有操作
    2.第一次买进来
    3.第一次卖出去
    4.第二次买进来
    5.第二次卖出去

    dp[i][0]:什么也没有操作过=》dp[i][0] = 0
    dp[i][1]:在第 i 天结束后,第一次买进股票,此时最大现金为 dp[i][1]
    dp[i][2]:在第 i 天结束后,第一次卖出股票,此时最大现金为 dp[i][2]
    dp[i][3]:在第 i 天结束后,第二次买进股票,此时最大现金为 dp[i][3]
    dp[i][4]:在第 i 天结束后,第二次卖出股票,此时最大现金为 dp[i][4]

    2、求关系式
    (1). dp[i][1]:第 i 天结束后,第一次买进股票,此时最大现金为 dp[i][1]。
        a. 第 i 天什么也没操作:dp[i][1] = dp[i-1][1]。
        b. 第 i 天第一次买进了股票:dp[i][0] = - price[i]。
    dp[i][1] = max(dp[i-1][1], - price[i]);

    (2). dp[i][2]:在第 i 天结束后,第一次卖出股票,此时最大现金为 dp[i][2]

        a. 第 i 天什么也没操作:dp[i][2] = dp[i-1][2].
        b. 第 i 天第一次卖出了股票:dp[i][1] = dp[i-1][1] + price[i].

    dp[i][2] = max(dp[i-1][2], dp[i-1][1] + price[i]);


    (3). dp[i][3]:在第 i 天结束后,第二次买进股票,此时最大现金为 dp[i][3]
        a. 第 i 天什么也没操作:dp[i][3] = dp[i-1][3].
        b. 第 i 天第一次买进了股票:dp[i][4] = dp[i-1][2] - price[i].

    dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - price[i])

    (4). dp[i][4]:在第 i 天结束后,第二次卖出股票,此时最大现金为 dp[i][4]
        a. 第 i 天什么也没操作:dp[i][4] = dp[i-1][4].
        b. 第 i 天第二次卖出了股票:dp[i][4] = dp[i-1][3] + price[i].
    dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + price[i])


    3、初始值
    dp[0][0] = 0;
    dp[0][1] = -price[0]
    dp[0][2] = 0
    dp[0][3] = -price[0]
    dp[0][4] = 0
    //dp[0][2] = 

    */

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][5];

        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];

        for(int i = 1; i < n; i++){
            dp[i][1] = Math.max(dp[i-1][1], - prices[i]);
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
        }

        return dp[n-1][4];
    }

}

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

188. 买卖股票的最佳时机 IV - 力扣(LeetCode)

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示:

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
class Solution {

    /*
    1.什么也没有操作
    2.第一次买进来
    3.第一次卖出去
    4.第二次买进来
    5.第二次卖出去
    6.第三次买进来
    7.第三次卖出去

    2 * k + 1;

    dp[i][0]:什么也没有操作过=》dp[i][0] = 0
    dp[i][1]:在第 i 天结束后,第一次买进股票,此时最大现金为 dp[i][1]
    dp[i][2]:在第 i 天结束后,第一次卖出股票,此时最大现金为 dp[i][2]
    dp[i][3]:在第 i 天结束后,第二次买进股票,此时最大现金为 dp[i][3]
    dp[i][4]:在第 i 天结束后,第二次卖出股票,此时最大现金为 dp[i][4]

    2、求关系式
    (1). dp[i][1]:第 i 天结束后,第一次买进股票,此时最大现金为 dp[i][1]。
        a. 第 i 天什么也没操作:dp[i][1] = dp[i-1][1]。
        b. 第 i 天第一次买进了股票:dp[i][0] = - price[i]。
    dp[i][1] = max(dp[i-1][1], - price[i]);

    (2). dp[i][2]:在第 i 天结束后,第一次卖出股票,此时最大现金为 dp[i][2]

        a. 第 i 天什么也没操作:dp[i][2] = dp[i-1][2].
        b. 第 i 天第一次卖出了股票:dp[i][1] = dp[i-1][1] + price[i].

    dp[i][2] = max(dp[i-1][2], dp[i-1][1] + price[i]);


    (3). dp[i][3]:在第 i 天结束后,第二次买进股票,此时最大现金为 dp[i][3]
        a. 第 i 天什么也没操作:dp[i][3] = dp[i-1][3].
        b. 第 i 天第二次买进了股票:dp[i][3] = dp[i-1][2] - price[i].

    dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - price[i])

    (4). dp[i][4]:在第 i 天结束后,第二次卖出股票,此时最大现金为 dp[i][4]
        a. 第 i 天什么也没操作:dp[i][4] = dp[i-1][4].
        b. 第 i 天第二次卖出了股票:dp[i][4] = dp[i-1][3] + price[i].
    dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + price[i])


    j = [0.....k*2]
    a.这一天什么也不操作:dp[i][j] = dp[i-1][j];
    b. 如果这一天买进来/卖出去
    if(j == 奇数){
        dp[i][j] = dp[i-1][j-1] - price[i];
    }else{
        dp[i][j] = dp[i-1][j-1] + price[i];
    }


    3、初始值
    dp[0][0] = 0;
    dp[0][1] = -price[0]
    dp[0][2] = 0
    dp[0][3] = -price[0]
    dp[0][4] = 0
    //dp[0][2] = 

    */

    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2*k+1];


        for(int i = 1; i < n; i++){
            for(int j = 1; j <= k * 2; j++){
                if(j % 2 == 1){
                    dp[0][j] = -prices[0];
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] + prices[i]);
                }
            }
        }

        return dp[n-1][2*k];
    }

}

leetcode309.买卖股票的最佳时机含冷冻期

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给定一个整数数组prices,其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

提示:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000
class Solution {
    /*
    1、dp[i][j]:表示在第 i 天结束后,股票的状态为 j,此时我们手上拥有的最大现金为 dp[i][j]。
    j = 0:表示不持有股票且不处于冷却期,(代表第 i+1 可以买卖股票)
    j = 1:表示不持有股票且处于冷却期,(代表第 i+1 不可以买卖股票)
    j = 2:表示我们持有股票,此时我们手上拥有的最大现金为 dp[i][j]
    最终要求的:dp[n-1][0]。

    2、dp[i][0]:表示不持有股票且不处于冷却期
        a.说明今天肯定不能卖出股票:说明,昨天不持有股票
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);

    dp[i][1]:表示不持有股票且处于冷却期
        a.说明今天卖出了股票 dp[i][1] =  dp[i- 1][2] + prices[i];

    dp[i][2]:表示我们持有股票
        a.今天什么也没做,说明昨天就拥有了股票:dp[i][2] = dp[i-1][2]
        b.今天买进这个股票,说明昨天是没有股票的:dp[i][2] = dp[i-1][0]  - prices[i]

    dp[i][2] = Math.max(dp[i-1][2], dp[i-1][0]  - prices[i]);


    3、初始值
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = -prices[0];
    */

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];

        dp[0][2] = -prices[0];

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] =  dp[i- 1][2] + prices[i];
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][0]  - prices[i]);
        }

        return Math.max(dp[n-1][0], dp[n-1][1]);


    }
}

leetcode322.零钱兑换

322. 零钱兑换 - 力扣(LeetCode)

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 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 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 10的4次方
class Solution {
    /*
        1、dp[i]:我们凑成金额为 i 所需要的最少硬币个数为 dp[i];

        2、关系式
        dp[i]:我们凑成金额为 i 所需要的最少硬币个数为 dp[i];

        比如说,我们选一个硬币 coins[j].

        金额本来是 i 的,现在变成了 i - coins[j]=>需要凑成 i-coins[j] 的硬币个数


        dp[i] = dp[i - coins[j]] + 1

        for(int j = 0; j < conis.length; j++){
            dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
        }

        3、初始值
        dp[0] = 0;
        dp[1...i] = Max



    */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        int max = amount + 1;
        for(int i = 1; i <= amount; i++){
            dp[i] = max;
        }

        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.length; j++){
                if(i >= coins[j] && dp[i-coins[j]] != max)
                dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
            }
        }

        return dp[amount] == max ? -1 : dp[amount];
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xiaoliii0401/article/details/135705972

leetcode解法java:5. longest palindromic substring_wangdatiancai的博客-爱代码爱编程

思路: 对整个string的每一个字母都做一个查询最长回文数操作,回文数分奇偶,首先进行奇数回文数查询,如果该字母和下一个字母相同,则也进行偶数回文数查询,然后用end-start记录最长length,返回即可。最简单的解法,应该还有优化空间。 public String longestPalindrome(String s) { int sta

leetcode|5.最长回文子串(java)_sandwichsauce的博客-爱代码爱编程

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb" 正确代码: package LeetCode; public class A5最长回文子串 {

leetcode 刷题记录(5,6,7)—java语言__traveler的博客-爱代码爱编程

5. 最长回文子串 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba”也是一个有效答案。 示例 2:

leetcode——5.longest palindromic substring(java)_菜鸡程序员的进阶的博客-爱代码爱编程

题目:找到最大的回文子串 首先,回文串就是左右对称的字符串。要解这道题首先应该知道如何判断一个字符串是否是回文串。 我的思想很简单,就是定义两个指针i,j,初始指向字符串头和尾,依次向里收缩。长度为奇数的字符串最后两个指针相遇,即i=j。长度为偶数的字符串最后相邻,即j=i+1。直到最后,若i和j满足上面的这个条件,则说明该字符串是回文串。然后再通过遍

leetcode第十题(java解法)_爱格格的小黄鸭的博客-爱代码爱编程

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the

leetcode 5. 最长回文子串(java版)_l__ear的博客-爱代码爱编程_leetcode最长回文子串java

题目描述(题目难度,中等) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。

【java】【leetcode】5. longest palindromic substring-爱代码爱编程

题目: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is a

leetcode5——最长回文子串——java实现_烛承幻的博客-爱代码爱编程

题目要求: 分析: 看到这种回文的题目,就会想到:以某一个数字为中心来进行处理。 我们抽取一个方法,用以实现下面所述的功能: 在babad中,首先以第一个b为中心,来判断它距它等距离的左边和右边的字母是否是相等的。当然第

【经典算法】leetcode 5: 最长回文子串(java/c/python3实现含注释说明,medium)-爱代码爱编程

目录 题目描述思路及实现方式一:动态规划法思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式二:中心扩展法思路代码实现Java版本C语言版本Python3版本 复

java程序员面试宝典第四版,leetcode 5,java面试线程池_leetcode java 5-爱代码爱编程

// 奇回文 for(int i = 1; i <= n ; i ++ ){ int l = 0 , r = min(i-1,n-i); while(l<r){ int mid = l+(r-l+1)/2