本文共 5542 字，大约阅读时间需要 18 分钟。

贪心算法

标题122. 买卖股票的最佳时机 II

题目描述

给定一个数组 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 。示例 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。 提示：1 <= prices.length <= 3 * 1040 <= prices[i] <= 104

代码

• 语言支持：Java
• 我是计算了所有第二天上涨的日子，然后把他们上涨的值都加起来。

Java Code:

class Solution {    public int maxProfit(int[] prices) {        int lenp = prices.length;        int[] detap = new int[lenp-1];        for(int i=0; i
   
     0 ){                res += detap[i];            }        }        return res;    }}
   

复杂度分析

令 n 为数组长度。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

题目地址(455. 分发饼干)

https://leetcode-cn.com/problems/assign-cookies/

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 示例 1:输入: g = [1,2,3], s = [1,1]输出: 1解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。示例 2:输入: g = [1,2], s = [1,2,3]输出: 2解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2. 提示：1 <= g.length <= 3 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1

代码

• 语言支持：Java

Java Code:

// 这是自己写的  109-128msclass Solution {
       public int findContentChildren(int[] g, int[] s) {
           Arrays.sort(g);        Arrays.sort(s);        int res = 0;        for(int i=0; i
   
    = g[i]){
                       res += 1;                    s[j] = -1;                    break;                }            }        }        //System.out.println(s[0]);        return res;    }}// 这是官方的，7=9msclass Solution {
       public int findContentChildren(int[] g, int[] s) {
           Arrays.sort(g);        Arrays.sort(s);        int numOfChildren = g.length, numOfCookies = s.length;        int count = 0;        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
               while (j < numOfCookies && g[i] > s[j]) {
                   j++;            }            if (j < numOfCookies) {
                   count++;            }        }        return count;    }}// 优化了一下自己的，因为排了序，所以有很多是不需要比较的class Solution {
       public int findContentChildren(int[] g, int[] s) {
           Arrays.sort(g);        Arrays.sort(s);        int slen = s.length, glen = g.length;        int res = 0, i=0, j=0;        while( i
    
     = g[j]){
                   res++;                j++;                }            i++;//不管这个饼干满不满足当前这个小孩，都要+1，因为是排好序的                //如果满足了就被吃掉了，如果满足不了的话，后面的小孩胃口还更大        }        return res;    }}
    
   

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(nlogn)$

题目地址(921. 使括号有效的最少添加)

https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/

题目描述

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。从形式上讲，只有满足下面几点之一，括号字符串才是有效的：它是一个空字符串，或者它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者它可以被写作 (A)，其中 A 是有效字符串。给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。 示例 1：输入："())"输出：1示例 2：输入："((("输出：3示例 3：输入："()"输出：0示例 4：输入："()))(("输出：4 提示：S.length <= 1000S 只包含 '(' 和 ')' 字符。

思路

用 栈，栈是 先进后出的。

代码

• 语言支持：Java

Java Code:

class Solution {
       public int minAddToMakeValid(String s) {
           int slen = s.length(), res = 0;        Stack sk = new Stack();        for(int i=0; i
   
    0 && (sk.peek().toString() == "(")  && s.charAt(i) == ")"){
               if( i>0 && !(sk.empty()) && sk.peek().toString().equals("(")  && s.charAt(i) == ')' ){
               // if( i>0 && sk.peek().toString().equals('(')  && s.charAt(i) == ')'){
                   sk.pop(); // 把'('弹出栈                res += 2;            }            else{
               sk.push( s.charAt(i) );            }        }        // System.out.println( sk.pop().toString() );        return slen - res ;    }}
   

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题目地址(714. 买卖股票的最佳时机含手续费)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

题目描述

给定一个整数数组 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.注意:0 < prices.length <= 50000.0 < prices[i] < 50000.0 <= fee < 50000.

代码

• 语言支持：Java

Java Code:

class Solution {
       public int maxProfit(int[] prices, int fee) {
           int buyPrice = prices[0] + fee;        int res = 0;        for(int i=1; i
   
     buyPrice ){
                   res += ( prices[i] - buyPrice );                // buyPrice = prices[i] + fee; 这是错的                buyPrice = prices[i];// 为了让自己反悔，因为比较贪心啊，比如下面这个例子                // [1, 3, 2, 8, 9, 10]                // 2                // 从1买到8，可能不是全局最优的方案，然后把当前购买价格buyPrice = 8                // 如果第二天的价格还更高，就接着买，但是不算手续费，不用加fee手续费                // 就等于我反悔了，8的那天我不卖了！从1买到9了，嘿嘿。同理，9的第二天是10，还更高，可以继续反悔                // System.out.println("prices[i]:" + prices[i]);            }        }        return res;    }}
   

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

转载地址：https://blog.csdn.net/qq_39555841/article/details/117589127 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！