LeetCode题解——贪心算法（四）

清疚 2023-06-06 12:25 1阅读 0赞

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

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

示例 1:
    
    输入: [7,1,5,3,6,4]
    输出: 7
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
         随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
    示例 2:
    
    输入: [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
         注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
         因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
    示例 3:
    
    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

### 贪心算法 ###

![format_png][]  
这种解法的理论依据是，跳过中间峰谷最大总利润会降低，数学上可以证明。

class Solution {
        
    public:
        int maxProfit(vector<int>& prices) {
        
            if(prices.empty())
                return 0;
            int maxprofit = 0; 
            for(int i = 1; i < prices.size(); ++i)
                if(prices[i] > prices[i - 1])
                    maxprofit += prices[i] - prices[i - 1];
            return maxprofit;
        }
    };

## 605. 种花问题 ##

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:
    
    输入: flowerbed = [1,0,0,0,1], n = 1
    输出: True
    示例 2:
    
    输入: flowerbed = [1,0,0,0,1], n = 2
    输出: False

注意:

数组内已种好的花不会违反种植规则。  
输入的数组长度范围为 \[1, 20000\]。  
n 是非负整数，且不会超过输入数组的大小。

### 解题思路 ###

遍历flowerbed\[\]数组，依次判断各位置是否适合种花，判断的标准是当前位置为0，且前一位置为0或其下标为-1，且后一位置为0或其下标为flowerbed.length。若判断为真，则修改flowerbed\[\]数组当前位置为1，n–。最后若n<=0,则能种下所有花。

class Solution {
        
    public:
        bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        
            if(flowerbed.empty())
                return false;
            if(n == 0)
                return true;
            for(int i = 0; i < flowerbed.size(); ++i)
            {
        
                if(flowerbed[i]==0 && (i==0 || flowerbed[i-1]==0) && (i+1==flowerbed.size() || flowerbed[i+1]==0))
                {
        
                    n--;
                    if(n==0)
                        return true;
                    flowerbed[i] = 1;
                }
            }
            return false;
        }
    };

## 392. 判断子序列 ##

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:
    s = "abc", t = "ahbgdc"
    
    返回 true.
    
    示例 2:
    s = "axc", t = "ahbgdc"
    
    返回 false.

### 贪心算法 ###

思路很简单，直接看代码。

class Solution {
        
    public:
        bool isSubsequence(string s, string t) {
        
            if(s.length() == 0)
                return true;
            int j = 0;
            for(int i = 0; i < t.length() && j < s.length(); ++i)
            {
        
                if(t[i] == s[j])
                    j++;
            }
            if(j == s.length())
                return true;
            return false;
        }
    };

## 665. 非递减数列 ##

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array\[i\] <= array\[i + 1\]。

示例 1:
    
    输入: [4,2,3]
    输出: True
    解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
    示例 2:
    
    输入: [4,2,1]
    输出: False
    解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
    说明:  n 的范围为 [1, 10,000]。

### 解题思路 ###

#### 倒序遍历 ####

class Solution {
        
    public:
        bool checkPossibility(vector<int>& nums) {
        
            if(nums.size() <= 2)
                return true;
            int count = 0;
            for(int i = nums.size() - 2; i >= 0; --i)
            {
        
                if(count > 1)
                    return false;
                if(nums[i] <= nums[i+1])
                    continue;
                if(i+2 < nums.size() && nums[i] > nums[i+2])
                    nums[i] = nums[i+1];
                count++;
            }
            return count < 2;
        }
    };

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

#### 正序遍历 ####

![format_png 1][]

class Solution {
        
    public:
        bool checkPossibility(vector<int>& nums) {
        
            if(nums.size() <= 2)
                return true;
            int count = 0;
            for(int i = 0; i < nums.size() - 1; ++i)
            {
        
                if(nums[i] > nums[i+1])
                {
        
                    count++;
                    if(count > 1)
                        return false;
                    if(i >= 1 && nums[i-1] > nums[i+1])
                        nums[i+1] = nums[i];
                    else
                        nums[i] = nums[i+1];
                }
            }
            return count < 2;
        }
    };

## 53. 最大子序和 ##

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
    
    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

### 解题思路 ###

#### 暴力法 ####

class Solution {
        
    public:
        int maxSubArray(vector<int>& nums) {
        
            int temp = INT_MIN;
            for(int i = 0; i < nums.size() - 1; ++i)
            {
        
                int max1 = nums[i];
                temp = max(temp, max1);
                for(int j = i+1; j < nums.size(); ++j)
                {
        
                    max1 += nums[j];
                    temp = max(temp, max1);
                }
            }
            temp = max(temp, nums[nums.size() - 1]);
            return temp;
        }
    };

#### 动态规划 ####

首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans  
如果 sum + nums\[i\] > nums\[i\]，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字  
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字  
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果  
时间复杂度：O(n)

class Solution {
        
    public:
        int maxSubArray(vector<int>& nums) {
        
            if(nums.empty())
                return 0;
            if(nums.size() == 1)
                return nums[0];
            int ans = nums[0];
            int sum = 0;
            for(int i = 0; i < nums.size(); ++i)
            {
        
                sum = max(sum + nums[i], nums[i]);
                ans = max(ans, sum);
            }
            return ans;
        }
    };

## 763. 划分字母区间 ##

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例 1:
    
    输入: S = "ababcbacadefegdehijhklij"
    输出: [9,7,8]
    解释:
    划分结果为 "ababcbaca", "defegde", "hijhklij"。
    每个字母最多出现在一个片段中。
    像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
    注意:
    
    S的长度在[1, 500]之间。
    S只包含小写字母'a'到'z'。

### 解法 ###

class Solution {
        
    public:
        vector<int> partitionLabels(string S) {
        
            int N = S.size();
            vector<int> ends(26, -1); //大小为26,都赋值为-1
            for(int i = 0; i < N; ++i)
            {
        
                ends[S[i] - 'a'] = i; //记录每个字母最后一次出现的位置
            }
            vector<int> res;
            int i = 0;
            while(i < N)
            {
        
                int r = ends[S[i] - 'a'];
                for(int j = i; j < r; j++)
                {
        
                    r = max(r, ends[S[j] - 'a']);
                }
                res.push_back(r - i + 1);
                i = r + 1;
            }
            return res;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]

[format_png]: /images/20230601/73eca30094424b9e8e6c68e85eb95f20.png
[format_png 1]: /images/20230601/ecc8fea8560047d1b14196e423f3303a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]: /images/20230601/3fdcc03fa35a424c98f31e67cd674ca9.png