Posted on | Post modified:
Words count in article: 1.2k

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

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)

分金条

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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)

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
`

最多的会议场数

一些项目要占用一个会议室宣讲， 会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间(给你一个数组， 里面 是一个个具体的项目)，
你来安排宣讲的日程， 要求会议室进行 的宣讲的场次最多。
返回这个最多的宣讲场次。
输入：
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)
`
Donate comment here
------------The End------------
0%