leetcode贪心算法题集锦（持续更新中）

绝地灬酷狼 2022-10-19 12:39 191阅读 0赞

# leetcode贪心算法题集锦 #

leetcode贪心算法题集锦（持续更新中）。python 和C++编写。

--------------------

### 文章目录 ###

*  leetcode贪心算法题集锦
 *  一、贪心算法
 *   *  1.盛最多水的容器
     *  2.买股票的最佳时机||
     *  3.跳跃游戏
     *  4.跳跃游戏||
     *  5.最长回文串
     *  6.种花问题
     *  7.分发饼干
     *  8.最大数
     *  9.将数组分成和相等的三个部分
 *  总结

--------------------

提示：以下是本篇文章正文内容，下面案例可供参考

# 一、贪心算法 #

## 1.盛最多水的容器 ##

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。  
![20210710163016510.png_pic_center][]

图中垂直线代表输入数组 \[1,8,6,2,5,4,8,3,7\]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：  
    设立一个最大面积res  
设一个左指针i一个右指针j，每次取左指针和右指针中小的值min(height\[i\],height\[j\])，乘以它们之间的坐标差(j-1)，算出来一个面积，如果比最大面积大，就更新最大面积，然后再比较height\[i\]和height\[j\]，如果height\[i\]比height\[j\]小，则i++，反之则j–，一直循环到i>=j为止  
    我们每次计算的都是的面积，若长是x，宽是y，则进行下一次计算时x会减1，即x会减少，为了获得更大的面积，我们需要更新短的那一根柱子，保有长的那一根柱子，这样才有几率获得更大的宽y，这样x\*y才可能比最大的值大.

C++ 版代码

class Solution { 
    public:
        int maxArea(vector<int>& height) { 
            int l = 0, r = height.size() - 1;
            int ans = 0;
            while (l < r) { 
                int area = min(height[l], height[r]) * (r - l);
                ans = max(ans, area);
                if (height[l] <= height[r]) { 
                    ++l;
                }
                else { 
                    --r;
                }
            }
            return ans;
        }
    };

python 版代码

class Solution:
        def maxarea(self,height=[1,2,3,4,5,9,8]):
            L=0
            R=len(height)-1
    
            ans=0 #初始面积
            while (L<R):
                area=min(height[L],height[R])*(R-L)
                ans=max(ans,area)
    
                if (height[L]<=height[R]):
                    L+=1
                else:
                    R-=1
            return ans
    
    
    if __name__ =='__main__':
        a=Solution()
        ans=a.maxarea(height=[1,8,6,2,5,4,8,3,7])
        print(ans)

--------------------

## 2.买股票的最佳时机|| ##

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。  
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。  
示例

> 输入: \[7,1,5,3,6,4\]  
> 输出: 7  
> 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
> 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

![20210711102355542.png_pic_center][]

C++ 版代码

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

python 版代码

class Solution:
        def maxProfit(self,price):
            ans=0
            n=len(price)
            for i in range(1,n):
                ans+=max(0,price[i]-price[i-1])
            return ans
    
    if __name__ =='__main__':
        a=Solution()
        ans=a.maxProfit(price=[7,1,5,3,6,4])
        print(ans)

--------------------

## 3.跳跃游戏 ##

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。  
示例1

> 输入：nums = \[2,3,1,1,4\]  
> 输出：true  
> 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

> 输入：nums = \[3,2,1,0,4\]  
> 输出：false  
> 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

思路：

> 我们可以用贪心的方法解决这个问题。  
> 设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x +nums\[x\]，这个值大于等于 y，即 x+nums\[x\]≥y，那么位置 y 也可以到达。

> 换句话说，对于每一个可以到达的位置 x，它使得 x+1, x+2, ,⋯,x+nums\[x\] 这些连续的位置都可以到达。  
> 这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置xx，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x + +nums\[x\] 更新 最远可以到达的位置。  
> 在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

C++版代码

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

python版代码

class Solution:
        def canJump(self,nums):
            """ :param nums: int型数组 :return: bool型数据 """
            n, rightmost = len(nums), 0
            for i in range(n):
                if i<=rightmost:
                    rightmost=max(rightmost,i+nums[i])
                    if rightmost>=n-1:
                        return True
            return False
    
    
    if __name__ =='__main__':
        a=Solution()
        ans=a.canJump(nums=[3, 2, 1, 0, 4])
        print(ans)

--------------------

## 4.跳跃游戏|| ##

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

示例1：

> 入: \[2,3,1,1,4\]  
> 输出: 2  
> 解释: 跳到最后一个位置的最小跳跃数是 2。  
> 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

思路：

> 如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。  
> 例如，对于数组 \[2,3,1,2,4,2,3\]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。  
> 从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。  
> ![20210713145424392.png_pic_center][]  
> 在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。  
> 在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

C++版代码

class Solution { 
    public:
        int jump(vector<int>& nums) { 
            int maxPos = 0, n = nums.size(), end = 0, step = 0;
            for (int i = 0; i < n - 1; ++i) { 
                if (maxPos >= i) { 
                    maxPos = max(maxPos, i + nums[i]);
                    if (i == end) { 
                        end = maxPos;
                        ++step;
                    }
                }
            }
            return step;
        }
    };

python版代码

class Solution:
        def jump(self, nums):
            """ :param nums: list[int] :return: """
            n = len(nums)
            maxPos, end, step = 0, 0, 0
            for i in range(n - 1):
                if maxPos >= i:
                    maxPos = max(maxPos, i + nums[i])
                    if i == end:
                        print('i:',i)
                        end = maxPos
                        step += 1
            return step
    
    
    if __name__=='__main__':
        a=Solution()
        step=a.jump([2,3,1,2,4,2,3])
        print(step)

![20210713150920886.png_pic_center][]

--------------------

## 5.最长回文串 ##

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。  
注意:  
假设字符串的长度不会超过 1010。

> 输入:  
> “abccccdd”  
> 输出:  
> 7  
> 解释:  
> 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

> 思路  
> 回文串是一个正着读和反着读都一样的字符串。以回文中心为分界线，对于回文串中左侧的字符 ch，在右侧对称的位置也会出现同样的字符。例如在字符串 “abba” 中，回文中心是 “ab|ba” 中竖线的位置，而在字符串 “abcba” 中，回文中心是 “ab©ba” 中的字符 “c” 本身。我们可以发现，在一个回文串中，只有最多一个字符出现了奇数次，其余的字符都出现偶数次。  
> 那么我们如何通过给定的字符构造一个回文串呢？我们可以将每个字符使用偶数次，使得它们根据回文中心对称。在这之后，如果有剩余的字符，我们可以再取出一个，作为回文中心。

> 算法  
> 对于每个字符 ch，假设它出现了 v 次，我们可以使用该字符 v / 2 \* 2 次，在回文串的左侧和右侧分别放置 v / 2 个字符 ch，其中 / 为整数除法。例如若 “a” 出现了 5 次，那么我们可以使用 “a” 的次数为 4，回文串的左右两侧分别放置 2 个 “a”。  
> 如果有任何一个字符 ch 的出现次数 v 为奇数（即 v % 2 == 1），那么可以将这个字符作为回文中心，注意只能最多有一个字符作为回文中心。在代码中，我们用 ans 存储回文串的长度，由于在遍历字符时，ans 每次会增加 v / 2 \* 2，因此 ans 一直为偶数。但在发现了第一个出现次数为奇数的字符后，我们将 ans 增加 1，这样 ans 变为奇数，在后面发现其它出现奇数次的字符时，我们就不改变 ans 的值了。

C++版代码

class Solution { 
    public:
        int longestPalindrome(string s) { 
            unordered_map<char, int> count;
            int ans = 0;
            for (char c : s)
                ++count[c];
            for (auto p : count) { 
                int v = p.second;
                ans += v / 2 * 2;
                if (v % 2 == 1 and ans % 2 == 0)
                    ++ans;
            }
            return ans;
        }
    };

python 版代码

import collections
    str='ABCDEFABC'
    class Solution:
        def longestPalindrome(s):
            ans = 0
            count = collections.Counter(s)
            for v in count.values():
                ans += v // 2 * 2
                if ans % 2 == 0 and v % 2 == 1:
                    ans += 1
            return ans
    
    
    a=Solution
    ans=a.longestPalindrome(s=str)
    print(ans)

![20210714090748628.png][]

--------------------

## 6.种花问题 ##

&nbsp假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

> 输入：flowerbed = \[1,0,0,0,1\], n = 1  
> 输出：true

> 输入：flowerbed = \[1,0,0,0,1\], n = 2  
> 输出：false

思路：  
从左向右遍历花坛，在可以种花的地方就种一朵，能种就种（因为在任一种花时候，不种都不会得到更优解），就是一种贪心的思想  
这里可以种花的条件是：

*  自己为空
 *  左边为空 或者 自己是最左
 *  右边为空 或者 自己是最右
 *  最后判断n朵花是否有剩余，为了效率起见，可以在种花的过程中做判断，一旦花被种完就返回true

C++版代码

class Solution { 
        public boolean canPlaceFlowers(int[] flowerbed, int n) { 
            for(int i=0; i<flowerbed.length; i++) { 
                if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) { 
                    n--;
                    if(n <= 0) return true;
                    flowerbed[i] = 1;
                }
            }
    
            return n <= 0;
        }
    }

python版代码

class Solution:
        def canPlaceFlowers(flowerbed,n):
            for i in range(len(flowerbed)):
                if (flowerbed[i]==0) and ((i==0) or (flowerbed[i-1] == 0)) and ((i==len(flowerbed)-1) or (flowerbed[i+1] == 0)):
                    n-=1
                    if (n <= 0):
                        return True
                    flowerbed[i] = 1
            return n<=0
    
    
    a=Solution
    ans=a.canPlaceFlowers(flowerbed=[1,0,0,0,1],n=2)
    print(ans)

--------------------

## 7.分发饼干 ##

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s\[j\] 。如果 s\[j\] >= g\[i\]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

> 输入: g = \[1,2,3\], s = \[1,1\]  
> 输出: 1  
> 解释:  
> 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。  
> 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。  
> 所以你应该输出1。

> 思路：  
> 为了满足更多的小孩，就不要造成饼干尺寸的浪费。  
> 大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。  
> 这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。  
> 可以尝试使用贪心策略，先将饼干数组和小孩数组排序。  
> 然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。  
> ![2021071715321099.png][]

C++版代码

// 时间复杂度：O(nlogn)
    // 空间复杂度：O(1)
    class Solution { 
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) { 
            sort(g.begin(), g.end());// 小孩
            sort(s.begin(), s.end());// 饼干
            int index = s.size() - 1; // 饼干数组的下表
            int result = 0;
            for (int i = g.size() - 1; i >= 0; i--) { 
                if (index >= 0 && s[index] >= g[i]) { 
                    result++;
                    index--;
                }
            }
            return result;
        }
    };

python版代码

class Solution :
        def findContentChildren(self,g,s):
            """ :param g: 小孩胃口阈值list[int] :param s: 饼干尺寸 list[int] :return: """
            g.sort()#小孩胃口阈值排序
            s.sort()#饼干尺寸 排序
            index = len(s)-1 #饼干尺寸的小标
    
            result = 0 #存储结果
            for i in range(len(g)-1,-1,-1):#遍历每一个小孩
                if index>=0 and s[index]>=g[i]:
                    result+=1 #结果加一
                    index-=1 #消耗掉一个饼干
            return result
    
    if __name__=='__main__':
        a=Solution()
        ans=a.findContentChildren(g=[1,2,3],s=[1,1])
        print(ans)

--------------------

## 8.最大数 ##

给定一组非负整数nums,重新排列每个数的顺序（每个数不可拆分）使之组成一个更大的数。  
注意：输出结果可能非常大，所有你需要返回的是一个字符串而不是一个整数。  
示例1：  
输入:nums=\[3,30,34,5,9\]  
输出：“9534330”

方法：选择排序

> l两个数字对应的字符串a和b,如果字典序a+b>b+a,此时a排在b前面即可获得更夫值  
> 示例：a=3,b=32，两者拼接 332>323,所有3排在32前面。

python代码

class Solution :
        def largestNumber(self,nums):
            """ :param nums: list[int] :return: str """
            n=len(nums)
            nums=list(map(str,nums)) 
            """ #map(func, seq1[, seq2,…]) 第一个参数接受一个函数名，后面的参数接受一个或多个可迭代的序列，返回的是一个集合。 Python函数编程中的map()函数是将func作用于seq中的每一个元素，并将所有的调用的结果作为一个list返回 """
            #冒泡排序
            for i in range(n):
                for j in range(i+1,n):
                    if nums[i]+nums[j]<nums[j]+nums[i]:
                        nums[i],nums[j]=nums[j],nums[i]
            return str(int("".join(nums)))
    if __name__=='__main__':
        a=Solution()
        ans=a.largestNumber([3,30,34,5,9])
        print(ans)

--------------------

## 9.将数组分成和相等的三个部分 ##

给你一个整数数组 arr，只有可以将其划分为三个和相等的 非空 部分时才返回 true，否则返回 false。形式上，如果可以找出索引 i + 1 < j 且满足 (arr\[0\] + arr\[1\] + … + arr\[i\] == arr\[i + 1\] + arr\[i + 2\] + … + arr\[j - 1\] == arr\[j\] + arr\[j + 1\] + … + arr\[arr.length - 1\]) 就可以将数组三等分。

示例 1：  
输入：arr = \[0,2,1,-6,6,-7,9,1,2,0,1\]  
输出：true  
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

思路  
![20210719165944704.png_pic_center][]

C++版代码

class Solution { 
    public:
        bool canThreePartsEqualSum(vector<int>& A) { 
            int s = accumulate(A.begin(), A.end(), 0);
            if (s % 3 != 0) { 
                return false;
            }
            int target = s / 3;
            int n = A.size(), i = 0, cur = 0;
            while (i < n) { 
                cur += A[i];
                if (cur == target) { 
                    break;
                }
                ++i;
            }
            if (cur != target) { 
                return false;
            }
            int j = i + 1;
            while (j + 1 < n) {   // 需要满足最后一个数组非空
                cur += A[j];
                if (cur == target * 2) { 
                    return true;
                }
                ++j;
            }
            return false;
        }
    };

python版代码

class Solution:
        def canThreePartsEqualSum(self, A) :
            """ :param A: : List[int] :return: bool """
            s = sum(A)
            if s % 3 != 0:
                return False
            target = s // 3
            n, i, cur = len(A), 0, 0
            while i < n:
                cur += A[i]
                if cur == target:
                    break
                i += 1
            if cur != target:
                return False
            j = i + 1
            while j + 1 < n:  # 需要满足最后一个数组非空
                cur += A[j]
                if cur == target * 2:
                    return True
                j += 1
            return False
    
    if __name__=="__main__":
        a=Solution()
        ans=a.canThreePartsEqualSum(A=[0,2,1,-6,6,-7,9,1,2,0,1])
        print(ans)

--------------------

# 总结 #

本文通过大量算例，讲解了贪心算法。  
![20210712085204824.png_pic_center][]

作者：电气-余登武

[20210710163016510.png_pic_center]: /images/20221005/b5a38d6d827c485497cace6a7aab2f3e.png
[20210711102355542.png_pic_center]: /images/20221005/765f1d804e7947dca5a19a6e63158b68.png
[20210713145424392.png_pic_center]: /images/20221005/d2be4f3c8cdd460a8aa714bcd9843369.png
[20210713150920886.png_pic_center]: /images/20221005/b71ed9cd9e3048bebdfa81c8ee7404b7.png
[20210714090748628.png]: /images/20221005/8621f640a6e44af1b125679422c83278.png
[2021071715321099.png]: /images/20221005/d1e436fb30c04b95875961906fa9b5af.png
[20210719165944704.png_pic_center]: /images/20221005/c442abeeae2d4fc6bd4cb661d17b23f6.png
[20210712085204824.png_pic_center]: /images/20221005/4d6588cbe6be49188a6ebb1a64d50b05.png