Leetcode题解 - 贪心算法部分简单题目代码+思路（860、944、1005、1029、1046、1217、1221）

leetcode真的是一个学习阅读理解的好地方

860. 柠檬水找零

"""

因为用户支付的只会有5、10、20

对于10元的用户必须找一个5

对于20元的用户可以找（三个5）或者（一个10一个5），每次都从大的开始找起来

"""

class Solution:

    def lemonadeChange(self, bills) -> bool:

        five = 0

        ten = 0

        for i in bills:

            if i == 5:

                five += 1

            if i == 10:

                if five == 0:

                    return False

                five -= 1

                ten += 1

            if i == 20:

                if ten == 0:

                    if five < 3:

                        return False

                    five -= 3

                else:

                    if not five:

                        return False

                    ten -= 1

                    five -= 1

        return True

---

944. 删列造序

class Solution:

    def minDeletionSize(self, A) -> int:

        if len(A[0]) == 1 or not A[0]:

            return 0

        sequence = 0

        minus = 0

        while sequence < len(A[0]):

            preTmp = 0

            i = 1

            # 判断该列是否应该被删除，即后一个是否大于等于前一个

            while i != len(A):

                if A[i][sequence] < A[preTmp][sequence]:

                    minus += 1

                    break

                preTmp = i

                i += 1

            sequence += 1

        return minus

---

1005. K 次取反后最大化的数组和

"""

因为可以对同一个进行多次处理，所以先把负的都变成正数，然后就一直对最小的进行取反操作

"""

class Solution:

    def largestSumAfterKNegations(self, A, K: int) -> int:

        A = sorted(A)

        tmp = K

        # 将负数先变成正数

        for i in range(K):

            if A[i] < 0:

                A[i] = -A[i]

            else:

                tmp = i

                break

        A = sorted(A)

        # 一直处理最小值

        while tmp < K:

            A[0] = -A[0]

            tmp += 1

        return sum(A)

---

1029. 两地调度

"""

先将所有人全部安排飞往B市，再选择N个人改变它们的行程，让它们飞往A市，那么每改变一个人就会额外付出priceA-priceB的费用，

谁的priceA-priceB最小（因为priceA-priceB是可正可负的），我们就让谁去。

"""

class Solution:

    def twoCitySchedCost(self, costs) -> int:

        costs = sorted(costs, key=lambda x:x[0] - x[1])

        s = 0

        n = len(costs)//2

        for i in range(n):

            s += costs[i][0] + costs[i + n][1]

        return s

---

1046. 最后一块石头的重量

"""

每次都找最大的两块出来，然后进行粉碎操作，开始下一次操作前仍然需要重新排序

"""

class Solution:

    def lastStoneWeight(self, stones) -> int:

        if len(stones) == 1:

            return stones[0]

        while stones:

            if len(stones) == 1:

                return stones[0]

            stones = sorted(stones, reverse=True)

            a = stones.pop(0)

            b = stones.pop(0)

            if a != b:

                stones.append(abs(a - b))

        return 0

---

1217. 玩筹码

"""

已知单数筹码移至单数筹码所在位置，或双数筹码移至双数筹码所在位置上时， 将不用付出代价。

但如果是单数筹码移至双数筹码的位置上，或双->单， 将需要付出 1 的代价,成堆的筹码移动时，也需要付出对应筹码个数的代价。

那就先把奇数位置的全部移动到A，偶数位置的全部移动到B，然后比较A和B那个点的筹码多，再把筹码少的移动过去。

奇数移动到偶数（偶数移动到奇数）的代价为少的一个的数量

"""

class Solution:

    def minCostToMoveChips(self, chips) -> int:

        odd = 0

        even = 0

        for i in range(chips):

            if chips[i] % 2 == 0:

                even += 1

                continue

            odd += 1

        return min(even, odd)

---

1221. 分割平衡字符串

"""

直观思路，为遇到的每一个R（L）找到配对的。

"""

class Solution:

    def balancedStringSplit(self, s: str) -> int:

        vis = set()

        res = 0

        for i in range(len(s)):

            if i in vis:

                continue

            sign = 0

            vis.add(i)

            for j in range(i+1, len(s)):

                # 如果遇到了同类，那么等下即使遇到了配对的，也不能立即配对

                if s[j] == s[i]:

                    sign += 1

                    vis.add(j)

                else:

                    sign -= 1

                    vis.add(j)

                    if sign == -1:

                        res += 1

                        break

        return res

Leetcode题解 - 贪心算法部分简单题目代码+思路（860、944、1005、1029、1046、1217、1221）的相关教程结束。