Leetcode题解 - 贪心算法

Posted on | Post modified: | In
Words count in article: 6.8k

本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站，刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是贪心算法相关题目题解总结。

[TOC]

贪心思想

概念

  • 最优子结构：最优子结构反映了分解问题的方式，我们在解决问题的时候，都会尝试将问题分解进行解决，产生的子问题，进而会产生局部解（总体解的子结构）。通常而言局部解也不仅只有一个，当局部解是局部最优解，并且该局部最优解是全局最优解的一部分时，我们称子问题的最优解为最优子结构。
  • 最优子结构的性质：问题的最优解由相关自问题的最优解组合而成，而这些子问题可以独立求解。（需要注意这里独立求解的含义：当前最优，不考虑后面的步骤）；
    最优子结构的形式（或者是否有最优子结构）取决于你分解问题的方式。合理的分解达到的效果是：与最终问题的目标存在紧密的关系。如果分解问题之后却无法导出最终问题的解，那么这种问题分解的方式就是无意义的。

基本思想

  • 贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：
  1. 整体的最优解可以通过局部的最优解来求出；
  2. 一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。

主要步骤

  1. 建立对问题精确描述的数学模型，包括定义最优解的模型；
  2. 将问题分解为一系列子问题，同时定义子问题的最优解结构；
  3. 应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用子问题的局部最优解堆叠出全局最优解。

0.1 拼接所有字符串产生字典顺序最小的字符串

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lowerString(self, strs):

        for i in range(len(strs)):
            for j in range(i+1, len(strs)):
                if strs[i] + strs[j] > strs[j] + strs[i]:
                    strs[i], strs[j] = strs[j], strs[i]
        return ''.join(strs)

if __name__ == '__main__':
    res = Solution().lowerString(['b','ba','abc'])
    print(res)

0.2 分金条

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金 条，怎么分最省铜板？

例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长度60的金条分成10和50，花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。
但是如果， 先把长度60的金条分成30和30，花费60 再把长度30金条分成10和20，花费30 一共花费90铜板。

输入一个数组，返回分割的最小代价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from heapq import *
class Solution:
    def gold(self, nums):
        heap = []
        for x in nums :
            heappush(heap, x)
        res = 0
        while len(heap) > 1:
            cur = heappop(heap) + heappop(heap)
            res += cur
            heappush(heap, cur)
        return res


if __name__ == '__main__':
    res = Solution().gold([10,20,30])
    print(res)

0.3 IPO

解题思路

以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

输出: 4

解释:
由于你的初始资本为 0，你尽可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

注意:

假设所有输入数字都是非负整数。
表示利润和资本的数组的长度不超过 50000。
答案保证在 32 位有符号整数范围内。

解题思路

用两个堆。
所有项目进入按照启动资金进小根堆。
每一次做项目时，先将当前资本能做的项目从小根堆中弹出，进入大根堆，大根堆按照最大利润组织，然后从大根堆中弹出利润最大的项目，将所得利润加到资本中。
这样可以保证每次先做当前资本所有能做的项目中利润最大的项目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from heapq import *

class Solution(object):
    def findMaximizedCapital(self, k, W, Profits, Capital):
        """
        :type k: int
        :type W: int
        :type Profits: List[int]
        :type Capital: List[int]
        :rtype: int
        """

        minCHeap = []
        # 项目启动资金的小根堆
        for i in range(len(Profits)):
            heappush(minCHeap, [Capital[i], Profits[i]])

        # 资本大于项目启动资金的所有项目按利润大根堆
        maxPHeap = []
        while k > 0:
            while minCHeap and W >= minCHeap[0][0]:
                pair = heappop(minCHeap)
                heappush(maxPHeap, -pair[1])
            if maxPHeap:
                W += -heappop(maxPHeap)
            k -= 1

        return W
`

0.4 最多的会议场数

一些项目要占用一个会议室宣讲， 会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间(给你一个数组， 里面 是一个个具体的项目)，
你来安排宣讲的日程， 要求会议室进行 的宣讲的场次最多。
返回这个最多的宣讲场次。
输入：
n 代表有n个会议需要安排
之后的 n 行，每行有两个数子，代表会议的开始和结束的时间

思路：
我们只需要按照会议结束的时间进行排序，然后依次安排，就能够安排最多的场数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Meeting(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end

class Solution(object):
    def Main (self):
        """
        :type k: int
        :type W: int
        :type Profits: List[int]
        :type Capital: List[int]
        :rtype: int
        """

        n = int(input())
        # 按结束时间排序
        meeting = [None]*n
        for i in range(n):
            pair = [int(x) for x in input().split()]
            meeting[i] = Meeting(pair[0], pair[1])

        meeting = sorted(meeting, key = lambda x:x.end)
        res = 1
        lastEnd = meeting[0].end
        for i in range(len(meeting)):
            if meeting[i].start < lastEnd:
                continue
            res += 1
            lastEnd = meeting[i].end

        return res


if __name__ == '__main__':
    res = Solution().Main ()
    print(res)
`

45. 跳跃游戏 II

题目描述

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

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

说明:

假设你总是可以到达数组的最后一个位置。

解题思路

需要知道每一步能跳的范围，然后遍历这个范围，根据该位置上的跳力来预测下一步能跳到的最远范围，贪的是一个能达到的最远范围。一旦这个范围达到了末尾，则返回。
cur表示当前能达到的最远位置，初始为0
pre表示之前能达到的最远位置，初始为0
在每一次循环中， pre = cur，表示上一次循环后能达到的最远位置，在范围内求解当前位置能达到的最远距离cur。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) <= 1:
            return 0
        res = 0
        cur = 0
        i = 0
        while cur < len(nums) - 1:
            res += 1
            pre = cur
            while i < pre+1:
                cur = max(cur, i+nums[i])
                if cur >= len(nums)-1:
                    return res
                i += 1
        
        return res
`

53. 最大子序和

题目描述

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

  • 示例:

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

  • 进阶:

    如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

设置最大和maxsub = nums[0]，中间和temp = 0；
遍历数组加到temp中，若temp > maxsub，则更新最大和maxsun；
若temp < 0，则置为0从新开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        maxsub = nums[0]
        temp = 0
        for i in range(len(nums)):
            temp += nums[i]
            if temp > maxsub:
                maxsub = temp
            if temp < 0:
                temp = 0
        return maxsub

55. 跳跃游戏

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

1
2
3
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

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

解题思路

贪心。使用一个变量保存当前能到达的最后位置的索引，向后遍历每个位置，如果该位置大于前面能到达的最大位置，则返回False，如果这个位置可以达到，则更新能达到的最后位置索引，更新策略是当前位置索引+这个数字能走多少步和原来能到的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) <= 0:
            return True
        
        reach = 0
        for i in range(len(nums)):
            if i > reach:
                return False
            reach = max(reach, i+nums[i])
        
        return True

121. 买卖股票的最佳时机

题目描述

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

  • 示例 1:

    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

  • 示例 2:

    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

  • 对数组进行遍历，定义到目前为止最大利润maxsum和加上当前利润的中间利润temp；
  • 如果temp>maxsum，则到目前最大利润maxsum = temp；
  • 如果temp小于0，舍弃，temp = 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        maxsum = 0
        temp = 0
        for i in range(1,len(prices)):
            temp += prices[i] - prices[i-1]
            if temp > maxsum:
                maxsum = temp 
            if temp < 0:
                temp = 0
        return maxsum

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。

解题思路

  • 对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ；
  • 因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加到收益中，从而在局部最优的情况下也保证全局最优。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        maxp = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                maxp += prices[i] - prices[i-1]
        return maxp

134. 加油站

题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

  • 如果题目有解，该答案即为唯一答案。
  • 输入数组均为非空数组，且长度相同。
  • 输入数组中的元素均为非负数。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 
gas  = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        
        if len(gas) != len(cost) or len(gas) == 0:
            return -1
        
        start = 0
        rest = 0
        overall = 0
        for i in range(len(gas)):
            rest += gas[i]-cost[i]
            overall += gas[i]-cost[i]
            if rest < 0:
                rest = 0
                start = i+1
        
        return start if overall >= 0 else -1

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.

  • 后续挑战 :

    如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

解题思路

双指针，遍历两个序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if not s:
            return True
        if not t or len(s) > len(t):
            return False
        i = j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)
if __name__ == '__main__':
    result = Solution().isSubsequence("ace","abcde")
    print(result)

406. 根据身高重建队列

题目描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

  • 注意：

    总人数少于1100人。

  • 示例

    输入:
    [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    输出:
    [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

  • 对people进行排序，h越大k越小的在前；
  • 然后按顺序给个高的先排序，因为个高的排好后，再怎么对矮个排序，都不会影响个高人的相对位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        if len(people) <= 1:
            return people
        people.sort(key = lambda x:[-x[0],x[1]])
        res = []
        for i in range(len(people)):
            res.insert(people[i][1],people[i])
        return res

435. 无重叠区间

题目描述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

  • 注意:

    可以认为区间的终点总是大于它的起点。
    区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

  • 示例 1:

    输入: [ [1,2], [2,3], [3,4], [1,3] ]
    输出: 1
    解释: 移除 [1,3] 后，剩下的区间没有重叠。

  • 示例 2:

    输入: [ [1,2], [1,2], [1,2] ]
    输出: 2
    解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

  • 示例 3:

    输入: [ [1,2], [2,3] ]
    输出: 0
    解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解题思路

区间题目一般按照排序+贪心去求解：

  • 先将区间按照起点升序；
  • 令第一个区间为起始老区间，然后从第二个起进行遍历，如果遍历到的区间的起点比老区间的终点小，说明有重叠；

    此时计数并移除区间，移除的为终点大的区间，即将老区间设置为终点小的区间；

  • 如果没有重叠，则更新老区间为当前遍历到的区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if len(intervals) <= 1:
            return 0
        intervals = sorted(intervals, key = lambda interval:interval.start)
        last = 0
        count = 0 
        for i in range(1,len(intervals)):
            if intervals[i].start < intervals[last].end:
                count += 1
                if intervals[i].end <intervals[last].end:
                    last = i
            else:
                last = i
        return count

452. 用最少数量的箭引爆气球

题目描述

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

  • Example:

    输入:
    [[10,16], [2,8], [1,6], [7,12]]
    输出:
    2
    解释:
    对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

解题思路

  • 使用排序+贪心。把所有坐标按照右边界进行排序，因为每个气球都要被打破，初始当前最远的位置curr_pos为第一个坐标的右边界，对坐标进行遍历；
  • 如果当前遍历到的坐标左边界小于curr_pos，则说明有重叠，继续；
  • 否则说明没有重叠，修改curr_pos为当前坐标的右边界，计数加1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if not points:
            return 0
        points.sort(key=lambda x: x[1])
        curr_pos = points[0][1]
        ans = 1
        for i in range(len(points)):
            if curr_pos >= points[i][0]:
                continue
            curr_pos = points[i][1]
            ans += 1
        return ans
if __name__ == '__main__':
    result = Solution().findMinArrowShots([[10,16], [2,8], [1,6], [7,12]])
    print(result)

455. 分发饼干

题目描述

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

  • 注意：

    你可以假设胃口值为正。
    一个小朋友最多只能拥有一块饼干。

  • 示例 1:

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

  • 示例 2:

    输入: [1,2], [1,2,3]
    输出: 2
    解释:
    你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
    你拥有的饼干数量和尺寸都足以让所有孩子满足。
    所以你应该输出2.

解题思路

对孩子胃口值g和饼干尺寸s排序，先用最小的饼干满足最小胃口值的孩子，如果最小饼干满足不了最小胃口值的孩子，则加大饼干值去满足该孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        if len(g)==0 or len(s)==0:
            return 0
        g.sort()
        s.sort()
        child = i = 0
        while child < len(g) and i < len(s):
            if s[i] >= g[child]:
                child += 1
            i += 1
        return child
if __name__ == '__main__':
    result = Solution().findContentChildren([10,9,8,7],[5,6,7,8])
    print(result)

763. 划分字母区间

题目描述

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

  • 示例 1:

    输入: S = “ababcbacadefegdehijhklij”
    输出: [9,7,8]
    解释:
    划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
    每个字母最多出现在一个片段中。
    像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

  • 注意:

    S的长度在[1, 500]之间。
    S只包含小写字母’a’到’z’。

解题思路

  • 用字典记录每个字母在字符串中出现的最右位置；
  • 然后对每个字母和位置进行遍历，找到最靠右位置end；
  • 如果遍历到的当前位置和最靠右位置重合，说明已经找到了一个划分；
  • 更新开始位置start，继续。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        if not S:
            return []
        charIndex = {c: i for i, c in enumerate(S)}
        end = start = 0
        ans = []
        for i, c in enumerate(S):
            end = max(end,charIndex[c])
            if i == end:
                ans.append(end-start+1)
                start = end + 1
        return ans
if __name__ == '__main__':
    result = Solution().partitionLabels("ababcbacadefegdehijhklij")
    print(result)

502. IPO

解题思路

以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

输出: 4

解释:
由于你的初始资本为 0，你尽可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

注意:

假设所有输入数字都是非负整数。
表示利润和资本的数组的长度不超过 50000。
答案保证在 32 位有符号整数范围内。

解题思路

用两个堆。
所有项目进入按照启动资金进小根堆。
每一次做项目时，先将当前资本能做的项目从小根堆中弹出，进入大根堆，大根堆按照最大利润组织，然后从大根堆中弹出利润最大的项目，将所得利润加到资本中。
这样可以保证每次先做当前资本所有能做的项目中利润最大的项目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from heapq import *

class Solution(object):
    def findMaximizedCapital(self, k, W, Profits, Capital):
        """
        :type k: int
        :type W: int
        :type Profits: List[int]
        :type Capital: List[int]
        :rtype: int
        """

        minCHeap = []
        # 项目启动资金的小根堆
        for i in range(len(Profits)):
            heappush(minCHeap, [Capital[i], Profits[i]])

        # 资本大于项目启动资金的所有项目按利润大根堆
        maxPHeap = []
        while k > 0:
            while minCHeap and W >= minCHeap[0][0]:
                pair = heappop(minCHeap)
                heappush(maxPHeap, -pair[1])
            if maxPHeap:
                W += -heappop(maxPHeap)
            k -= 1

        return W
`
Donate comment here
------------The End------------
0%