@

• 1. 分割平衡字符串

• 2.最少操作使数组递增

• 3.打折购买糖果的最小开销

• 4.构造 K 个回文字符串

前言

        第四天：贪心算法
        贪心算法采用贪心策略，即保证每次操作都是局部最优，从而使结果全局最优。

一、练习题目

二、思路与代码

1. 分割平衡字符串

遍历字符串，设置计数器，遇到L，变量pos加一，遇到R，变量pos减一，若变量为零，则计数器加一，返回计数器。

class Solution(object):
    def balancedStringSplit(self, s):
        """
        :type s: str
        :rtype: int
        """
        pos = 0
        count = 0
        if len(s) == 0:
            return 0
        for i in s:
            if i == 'L':
                pos += 1
            if i == 'R':
                pos -= 1
            if pos == 0:
                count += 1
        return count

2.最少操作使数组递增

遍历数组，后一个数组比起哪一个小，则加上一个数，使后一个数大于前一个数；若后一个数比前一个数大，则不变。

class Solution(object):
    def minOperations(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        n = len(nums)
        for i in range(n-1):
            if nums[i+1] <= nums[i]:
                count += nums[i] - nums[i+1] + 1
                nums[i+1] = nums[i] + 1
            else:
                nums[i+1] = nums[i+1]
        return count

3.打折购买糖果的最小开销

贪心算法，对价格降序排序后，算出最大的折扣，再用总开销减去它即可得到答案。

class Solution(object):
    def minimumCost(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        cost.sort(reverse = True)
        n = len(cost)
        discount = 0
        for i in range(n):
            if i % 3 == 2:
                discount += cost[i]
        return sum(cost) - discount

4.构造 K 个回文字符串

1、创建长度为26的哈希表，遍历给定的字符串，记录每个字母出现的次数；
2、对于长度大于等于2的偶数回文串，能与任意的回文串组成一个新的回文串，而偶数的回文子串也可以继续拆分。因此，确定偶数回文子串十分重要，我们可以将相同的字符两两配对，计为twoCount个，剩下的单字符没有配对成功的有oneCount个；
3、twoCount回文子串可以全部拆成单个字符再加上单字符oneCount，共可以组合出最多2*twoCount+oneCount个回文串；
4、回文串最小组合数取决于单个字符oneCount的数量，即oneCount个回文串；
5、判别给定的k是否在回文子串个数区间内即可。

class Solution(object):
    def canConstruct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        hash = [0] * 26 #构造哈希表
        twoCount = 0 
        oneCount = 0 
        s.lower()
        for i in s:
            hash[ord(i) - ord('a')] += 1
        for i in range(26):
            twoCount += hash[i] // 2
            oneCount += hash[i] % 2
        if k >= oneCount and k <= 2 * twoCount + oneCount:
            return True
        else:
            return False

CSDN版链接二维码：