做进化树的在线网站,根据图片做网站用什么,网站制作 手机,百度运营平台文章目录 零 算法介绍一 简单示例 找零钱问题Leetcode例题与思路[605. 种花问题](https://leetcode.cn/problems/can-place-flowers/)解题思路题解 [409. 最长回文串](https://leetcode.cn/problems/longest-palindrome/)解题思路题解 [121. 买卖股票的最佳时机](https://leetc… 文章目录 零 算法介绍一 简单示例 找零钱问题Leetcode例题与思路[605. 种花问题](https://leetcode.cn/problems/can-place-flowers/)解题思路题解 [409. 最长回文串](https://leetcode.cn/problems/longest-palindrome/)解题思路题解 [121. 买卖股票的最佳时机](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/)解题思路题解 [11. 盛最多水的容器](https://leetcode.cn/problems/container-with-most-water/)解题思路题解 [763. 划分字母区间](https://leetcode.cn/problems/partition-labels/)解题思路题解 零 算法介绍
首先我们需要明确什么算是贪心
通常当我们说一个人贪心时我们是指这个人过分地追求物质财富或利益常常不顾及他人利益或感受。贪心的人可能会利用他人甚至不惜损害他人来达到自己的目的。而在算法中贪心算法指的是一种解决问题的策略它总是做出在当前状态下看起来最优的选择期望通过一系列局部最优的选择达到全局最优的结果。贪心算法的优点是实现简单运行效率高但在某些问题上可能无法得到最优解。
贪心算法的基本步骤如下 对问题进行分解将其分解为一系列相互独立的子问题。 对于每个子问题找到一个最优解。 将所有子问题的最优解组合起来形成问题的最终解。
需要注意的是贪心算法并不总是能够找到最优解。在应用贪心算法时需要验证问题是否满足贪心选择性质即通过局部最优的选择可以导致全局最优的解。如果问题不满足贪心选择性质那么贪心算法可能无法找到最优解。
贪心算法的应用场景包括 Dijkstra 算法用于寻找图中的最短路径。 Huffman 编码用于构建最优前缀编码。 Kruskal 算法用于寻找最小生成树。
贪心算法在很多领域都有广泛的应用但在使用时需要注意其局限性并在必要时选择其他算法如动态规划、回溯等。
一 简单示例 找零钱问题
假设你开了间小店不能电子支付钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币如果你是售货员且要找给客户 n 分钱的硬币如何安排才能找给客人的钱既正确且硬币的个数又最少
面对贪心我们需要首先做一个证明即证明贪心的方式即为最优解。在这道题目中我们从最大数开始找零那么必然可以做到找到零钱数最少【保证每个零钱的数值尽可能大】。
既然得到这个思路那么题解便自然生成
def change(n, currency[25, 10, 5, 1]):该程序设计一个找零算法最后返回应当找回货币的个数Args:n (int): 待找零钱currency (list, optional): 货币的面值有多少. Defaults to [25, 10, 5, 1].Returns:_type_: _description_count, i 0, 0 # count 用作统计货币个数i 作为统计链表长度while n ! 0 and i len(currency): # 当还有待找零钱且货币面值可以继续找零的情况下进行循环count n // currency[i] # 当前面值货币可以获得几个n % currency[i] # 剩余待找货币的面值i 1 # 判断下一个等级面值的货币的面值return countprint(change(43))
# 6Leetcode例题与思路
接下来我们列举关于Leetcode的五道例题并通过贪心的方式进行求解
605. 种花问题
假设有一个很长的花坛一部分地块种植了花另一部分却没有。可是花不能种植在相邻的地块上它们会争夺水源两者都会死去。
给你一个整数数组 flowerbed 表示花坛由若干 0 和 1 组成其中 0 表示没种植花1 表示种植了花。另有一个数 n ****能否在不打破种植规则的情况下种入 n ****朵花能则返回 true 不能则返回 false 。
解题思路
这道题目我们考虑一下如何证明是否如果当遇到连续的3个0我们即刻在其中中间的花圃中种植一朵花。而循环遍历整个花田即可保证不能再种植新的花朵了。但需要注意这道题目中的个例即边界的时候只要两个连续的0就可以了这该怎么解决呢详情请看题解
题解
class Solution:def canPlaceFlowers(self, flowerbed: List[int], n: int) - bool:for i in range(len(flowerbed)):left 0 if i 0 else flowerbed[i-1] # 对左边界的特殊处理right 0 if i len(flowerbed)-1 else flowerbed[i1] # 对右边界的特殊处理if flowerbed[i] 0 and left 0 and right 0: # 当前节点为空且左右为空的情况下flowerbed[i] 1 # 在当前节点种花n - 1 # 剩余花朵减一return n 0409. 最长回文串
给定一个包含大写字母和小写字母的字符串 s 返回 通过这些字母构造成的 最长的回文串 。
在构造过程中请注意 区分大小写 。比如 Aa 不能当做一个回文字符串。
解题思路
关于这道题目的解题思路稍微有一些隐式。我们需要验证构建最长的回味字串需要满足什么条件即如果回文子串的长度为偶数则表示字符串中所有元素的个数都为偶数如果回文子串的长度为奇数则除了中心元素外其他元素必须为偶数。
那么构建最长的回味字串的方法是什么即对每个字符串取最大偶数的个数如果还剩下数字则在加1。转换成代码如下所示
题解
class Solution:def longestPalindrome(self, s: str) - int:static {}for i in s:static[i] static[i] 1 if i in static.keys() else 1remain, total 0, 0for count in static.values():total_, remain_ divmod(count, 2)remain remain_total total_return total * 2 (0 if remain 0 else 1)121. 买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
解题思路
在这道题目中我们需要判断什么时候买入卖出是最合适的难道是最小下标和最大下标那必然不可行。所以我们需要思考一下怎么贪心才可以呢这道题目其实有一些动态规划的思想在里面所以思考起来会稍微复杂一些
我们如何找到能买到最多钱的时候呢很简单就是卖出价格减去之前买入价格的时候差值最大。
换句话说对每个元素减去之前最便宜的价格就是当前元素的收益所以我们仅需要这个值的大小即可。
同时我们仅需要记录在当前元素之前的最小值就可以通过线性复杂度来求解这道题目。
题解
class Solution:def maxProfit(self, prices: List[int]) - int:max_value, min_index 0, 0for i in range(len(prices)):if prices[i] prices[min_index]:min_index ielse:max_value max(max_value, prices[i] - prices[min_index])return max_value11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明**你不能倾斜容器。
解题思路
这道题目的思想也比较有意思当我们下标减小的时候一定会减小容纳的水但当挡板变高的时候就有可能增大容纳的水的体积。
在有了这个假设的前提下我们从两端移动挡板向中间移动。由于容纳体积是由短板决定的所以我们每次移动短板即可。
转换成代码如下
题解
class Solution:def maxArea(self, height: List[int]) - int:i, j, res 0, len(height) - 1, 0while i j:if height[i] height[j]:res max(res, height[i] * (j - i))i 1else:res max(res, height[j] * (j - i))j - 1return res763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1
输入s ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca、defegde、hijhklij 。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。 解题思路
这道题也是非常有意思的一道题其核心句其实是**同一字母最多出现在一个片段中。**通过这句话我们就有确切的分割界限了。但如何做可以通过线性的方式来求解呢
我给出的思路是统计每个字符出现的区间如果两个字符串的区间相交即可融合。于是这就变成了融合区间的题目。由于字符出现的顺序是有序的所以在合并区间的时候顺序合并就可以了。
其题解如下
题解
class Solution:def partitionLabels(self, s: str) - List[int]:index {}for i in range(len(s)):if s[i] in index.keys():index[s[i]][1] ielse:index[s[i]] [i, i]answer []key_list list(index.keys())for i, key in enumerate(key_list):if len(answer) 0:answer.append(index[key])elif answer[-1][1] index[key][0]:answer[-1][1] max(index[key][1], answer[-1][1])else:answer.append(index[key])return [i[1] - i[0] 1 for i in answer]
