牛客网---贪心算法（python实现）

缺乏、安全感 2022-11-05 08:52 203阅读 0赞

### 不贪心如何拿Offer ###

*   *  一：股票交易的最大收益：
     *  二：换酒问题：
     *  三：分发饼干：

## 一：股票交易的最大收益： ##

假定你知道某只股票每一天价格的变动。  
你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。  
请设计一个函数，计算你所能获得的最大收益。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]  
**根据题意我们可以分析出来，只要是明天比今天涨了，我们就要这个收益。(贪心)**

class Solution:
        def maxProfit(self , prices ):
            res = 0
            length = len(prices)
            for i in range(1, length):
                if prices[i] > prices[i-1]:
                    res += prices[i] - prices[i-1]
            return res

## 二：换酒问题： ##

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

class Solution:
        def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
            res = 0
            count = 0
            while(numBottles):
                # 1： 喝酒数量增加
                res = numBottles + res
                # 2： 酒瓶子数量更新
                count = count + numBottles
                # 3: 酒数量更新
                numBottles = count // numExchange
                # 4: 剩余酒瓶子数量更新
                count = count % numExchange
            return res

## 三：分发饼干： ##

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

class Solution:
        def findContentChildren(self, g: List[int], s: List[int]) -> int:
            # 将胃口和饼干尺寸进行排序
            g.sort()
            s.sort()
            # 计算数量
            n, m = len(g), len(s)
            i = j = count = 0
            # 没有到边界就继续走
            while i < n and j < m:
                # 如果胃口比饼大，则j后移动
                while j < m and g[i] > s[j]:
                    j += 1
                # 如果胃口小于饼了，数量加一
                if j < m:
                    count += 1
                i += 1
                j += 1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]: /images/20221023/b2adeeee54f54de6bf8308239adf127f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 1]: /images/20221023/6ba70c4dfe99421e935a042c08da827c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 2]: /images/20221023/2b6c27a10d36405db1d1a1fe503f5161.png