chapter7-greedy-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 2.3k | Reading time ≈ 10

chapter7-greedy-algorithm

[TOC]

贪心思想
1. 分配饼干

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
def findContentChildren():
    g, s = [ 1, 2, 3 ], [ 1, 1 ]
    # 由题意 “目标是尽可能满足越多数量的孩子”
    # 而饼干是有限的，所以首先满足胃口小的孩子，这样才能，尽可能满足较多数量的孩子
    cnt = 0
    g.sort()
    s.sort()
    for n in s:
        if n >= g[cnt]:
            cnt += 1
        if cnt >= len(g): break
    print(cnt)
findContentChildren()
2. 不重叠的区间个数

Leetcode / 力扣

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
def eraseOverlapIntervals():
    intervals = [ [1,2], [3,5], [2,5], [2,3], [1,3] ]
    # 又题意可知 有intervals[i][j],要删除最少重叠的区间个数
    # 而不重叠区间满足
    # intervals[i][1] > intervals[i][0] and intervals[i-1][1] <= intervals[i][0]
    # 即整理的intervals[i][1] > intervals[i][0] >= intervals[i-1][1] >intervals[i-1][0]
    # 其中如果有intervals[i][0] >= intervals[i-1][1],必定是联系最紧密的区间
    # 因此，首先通过intervals[i][1]进行从小到大排序，保证整体区间的正确性
    # 然后依次计算能够满足的区间，满足intervals[i][0] >= intervals[i-1][1]就进行加1
    # 这样就能够很好满足，找到最多的满足区间

    res = 1
    if not intervals: return 0
    def cmp( a, b ):
        if (a[1]-b[1]) < 0:
            return -1
        if (a[1]-b[1]) == 0:
            return 0
        else:
            return 1
    import functools
    # it2 = sorted(intervals,key = functools.cmp_to_key(cmp))
    it2 = sorted(intervals,key = lambda x:x[1])
    print(it2)
    end = it2[0][1]
    for i in range(1,len(it2)):
        if it2[i][0] < end :
           continue
        end = it2[i][1]
        res += 1

    print(len(intervals) , res)
    return  len(intervals) - res

eraseOverlapIntervals()
3. 投飞镖刺破气球

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findMinArrowShots():
    points = [[10,16],[2,8],[1,6],[7,12]]
    # 又题意可知，要用最小的次数去打破全部气球
    # 意味着找出最多有公共空间的气球的为一组，就是直径能够重叠的气球
    # 因此，为能够保证打气球包住小气球，首先通过Xend进行从小到大排序
    # 然后通过当前Xend与下一个气球Xstart进行比较，判断气球是否重叠
    # 所以对于气球组points[i][j]来说，满足points[i][0] >= points[i][1] 就意味着气球重叠
    # 当气球不重叠时，需要更新当前比较的Xend，因为说明气球，已经到了另一个气球的边缘(因为是通过Xend排序了)
    # 因此代码逻辑如下：

    points.sort(key = lambda x:x[1])
    print(points)
    res = 1
    end = points[0][1]
    for p in range(1, len(points)):
        if points[p][0] <= end:
            continue
        end = points[p][1]
        res += 1
    print(res)
    return res

findMinArrowShots()
4. 根据身高和序号重组队列

Leetcode / 力扣

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
def reconstructQueue():
    people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

    # you题意可知
    # 身高越高的人，前面比他高的人数，就是当前队列的索引。比如上述people->[[7,0] [7,1]]
    # 如果比他矮的人(身高最高的人)，如[5,0]，前面比他高的人，应是当前索引最前面的一个数，如[[5,0]，[7,0] [7,1]]
    # 因此总结规律如下：
    # 1. 队列应从身高降序排列。如果身高相同者，升序排序
    # 然后依次遍历，按当前比他高身高人数为索引插入新建队列
    # 注意，身高最高者，他的索引"必定"有0，并且才有1，意味着(身高比他矮的，且索引相同时，必定在他前面)
    # 因此从身高降序排列，不会影响身高矮插入队列是，出现队列乱序的错误。
    def cmp( a, b ):
        if (a[0]-b[0]) == 0:
            return a[1]-b[1]
        else:
            return b[0]-a[0]
    import functools
    # people.sort(key = functools.cmp_to_key(cmp))
    people.sort(key = lambda x:(-x[ 0 ], x[ 1 ]))
    print(people)
    output = []
    for p in people:
        output.insert(p[1],p)
    print(output)
reconstructQueue()
5. 买卖股票最大的收益

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maxProfit():
    prices = [7,1,5,3,6,4]
    # you题意可知
    # 难点在于股票买入卖出是有先后顺序的
    # 意味着，卖出股票index=i，买入的股票，区间只能在[0,i)
    # 因此使用贪婪算法：
    # 代码逻辑如下：

    if len(prices) <= 1:
        return 0

    maxv,minv = 0, prices[0]
    for p in range(1,len(prices)):
        if minv > prices[p]:
            minv = prices[p]
        maxv = max(maxv, prices[p]-minv)
    print(maxv)
    return maxv
maxProfit()
6.买卖股票的最大收益 II

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
def maxProfit2():
    prices = [7,1,5,3,6,4]
    # you题意可知
    # 最大收益，就是求累计的最大收益，即为累加(卖出-买入>0)的股票
    # 优化逻辑，如果股票时段内单调递增的，只求第一只和最后一只股票即可
    # 代码逻辑如下
    maxv = 0
    for i in range(1,len(prices)):
        if prices[i] > prices[i-1]:
            maxv += (prices[i] - prices[i-1])
    print(maxv)
    return maxv
maxProfit2()
7. 种植花朵

Leetcode / 力扣

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def canPlaceFlowers():
    flowerbed = [1,0,0,0,1]
    n = 2

    # 又题意可知
    # 要想能够种植花朵，必须满足不相邻
    # 因此当在地flowerbed[i]中，只有满足
    # flowerbed[ i ] == 0 and flowerbed[ i - 1 ] == 0 and flowerbed[ i - 2 ] == 0
    # 才能种植。
    # 注意： 当一块地的边界(前后)，边上是没有花朵的，意味着边界也是0(只需两个地方等0 就可以种植).
    # 代码逻辑如下：
    def slove1(n):
        if n == 0: return True
        if n == 1 and len(flowerbed) <= 1 and flowerbed != 0: return False
        if n == 1 and len(flowerbed) <= 1 and flowerbed == 0: return True


        if flowerbed[ 0 ] == 0 and flowerbed[ 1 ] == 0:
            flowerbed[ 0 ] = 1
            n -= 1
            if n == 0:
                return True

        if flowerbed[ -2 ] == 0 and flowerbed[ -1 ] == 0:
            flowerbed[ -1 ] = 1
            n -= 1
            if n == 0:
                return True

        for i in range(2, len(flowerbed)):
            if flowerbed[ i ] == 0 and flowerbed[ i - 1 ] == 0 and flowerbed[ i - 2 ] == 0:
                flowerbed[ i - 1 ] = 1
                n -= 1
            if n == 0:
                return True
        return False


    # 上述直接通过规则判断
    # 这根据上诉规则优化，计算能够安放花朵的个数，直接与n判断即可

    def slove2(n):
        flowerbed.insert(0,0)
        flowerbed.append(0)

        cnt = 0
        for i in range(1, len(flowerbed)-1):
            if flowerbed[i] == 1:
                continue
            if flowerbed[i-1] == 0 and flowerbed[i+1] == 0:
                cnt += 1
                flowerbed[i] = 1
        print(cnt >= n)
        return cnt >= n
    slove1(n)
    slove2(n)
canPlaceFlowers()
8. 判断是否为子序列

Leetcode / 力扣

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
def isSubsequence():
    s = "abc"; t = "ahbgdc"

    # 序列，必须满足一定的先后顺序
    # 即s中，如果第一个数‘a’找到了,t中所以为i，那么下一个数一定是在‘a’在t中的索引(i,len(t))后面继续寻找
    # 因此代码逻辑如下
    def slove1():
        if not s: return True
        cnt, right = 0, 0
        for a in s:
            for b in range(right, len(t)):
                if a == t[ b ]:
                    cnt += 1
                    right = b + 1
                    break

            if cnt == len(s):
                return True
        return False

    # 通过Python3自带索引方法
    # 直接寻找字符串t是否有这个字符，如果有，就返回当前第一个值的索引i
    # 如果没有就报错，就说明没有这个子序列
    def slove2(t):
        if not s: return True
        idx = 0
        for a in s:
            try:
                idx = t.index(a, idx)
                idx += 1
            except ValueError:
                return False
        return True
    slove1()
    print(slove2(t))
isSubsequence()
9. 修改一个数成为非递减数组

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def checkPossibility():
    # you题意可知
    # 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。
    # 那点在于，开始当i<2的时候，如何去处理
    # 因为当i>=2时，因为要满足单调递增，所以不满足时，这个值只能够改为与前面相同的值
    # 当i<2时，由于前面有没有出现单调的趋势，i=0(前面没有值)，所以此错误值，是可以把前面的值，改为后面的一个值相同
    # 因此代码逻辑如下
    nums = [3,4,2,3]
    n  = 1
    for i in range(1, len(nums)):
        if nums[i] >= nums[i-1]:
            continue
        else:
            if i - 2 >= 0 and nums[i-2] > nums[i]:
                nums[i] = nums[i - 1]
            else:
                nums[i - 1] = nums[i]
            n -= 1
        if n < 0:
            return False
    return True

print(checkPossibility())
10. 子数组最大的和

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maxSubArray():
    nums = [-2,1,-3,4,-1,2,1,-5,4]

    # 又题意可知，就子数组最大的和，这和肯定数数组中连续一段的子数组
    # 如果全部都为负数，那么最大和即为数组中最大的值
    # 那么如果数组中有和为正数：
    # 1. 最大和，必定是以>=0为开头的数，进行加和，这样累计才有最大值。
    # 2. 如果前面有负值累计一定不是，因此累计结束条件，即为当累计下一个值为负值时，直接重新赋值为0，再累计
    # 每次取累计中最大值，最终结果为最大和
    # 代码逻辑如下：
    maxv = float('-inf')
    s = 0
    for n in nums:
        s = s + n
        maxv = max(maxv, s)
        if s < 0:
            s = 0
    print(maxv)
maxSubArray()
11. 分隔字符串使同种字符出现在一起

Leetcode / 力扣

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
40
41
def partitionLabels():
    S = "vhaagbqkaq"

    # you题意可知
    # 规则为：1. 同一个字母只会出现在其中的一个片段
    # 因此，我们只需要记住每一种字母，最后出现的索引位置。
    # 每次遍历到当前字符串最末索引，就是满足字符串长度最小的片段
    # 因此代码逻辑如下：
    def slove1():
        send = [ float('inf') for i in range(26) ]
        for c in range(len(S)):
            send[ ord(S[ c ]) - ord('a') ] = c

        res = [ ]
        maxv = float('-inf')
        for c in range(len(S)):
            maxv = max(maxv, send[ ord(S[ c ]) - ord('a') ])
            if c == maxv:
                if not res:
                    res.append(c + 1)
                else:
                    res.append(c - sum(res) + 1)
        print(res)
        return res

    # 代码优化
    def slove2():
        send = {c:i for i, c in  enumerate(S)}
        print(send)
        sentry, res, maxv = 0, [], float('-inf')
        for i, c in enumerate(S):
            maxv = max(maxv, send[c])
            if maxv == i:
                res.append(i-sentry + 1)
                sentry += res[-1]
        print(res)
        return res
    slove1()
    slove2()

partitionLabels()