455. 分發(fā)餅干

難度簡單

假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子 i，都有一個胃口值 g[i]_，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j]。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。

示例 1:

輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。
</pre>

示例 2:

輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2.

提示：

• 1 <= g.length <= 3 * 10<sup>4</sup>
• 0 <= s.length <= 3 * 10<sup>4</sup>
• 1 <= g[i], s[j] <= 2<sup>31</sup> - 1

問題分析

1. 滿足最多的孩子那么可以理解為先滿足胃口最小的孩子，再滿足胃口大的。
2. 可以對餅干的大小和孩子的食量進行排序，然后依次進行滿足。

3. 代碼輸出

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        """
        貪心算法，
        """
        if not g or not s:
            return 0

        #  分別進行排序
        g.sort()
        s.sort()
        
        gi = 0
        si = 0
        ans = 0
        while gi < len(g) and si < len(s):
            # 當??可以滿足時
            if g[gi] <= s[si]:
                gi += 1
                si += 1
                ans += 1
            else:
               # ??不能滿足時，需要向后找更大塊的餅干
                si += 1
        
        return ans

1221. 分割平衡字符串

難度簡單177

在一個 平衡字符串 中，'L' 和 'R' 字符的數(shù)量是相同的。

給你一個平衡字符串 s，請你將它分割成盡可能多的平衡字符串。

注意：分割得到的每個字符串都必須是平衡字符串，且分割得到的平衡字符串是原平衡字符串的連續(xù)子串。

返回可以通過分割得到的平衡字符串的 最大數(shù)量 。

示例 1：

輸入：s = "RLRRLLRLRL"
輸出：4
解釋：s 可以分割為 "RL"、"RRLL"、"RL"、"RL" ，每個子字符串中都包含相同數(shù)量的 'L' 和 'R' 。

示例 2：

輸入：s = "RLLLLRRRLR"
輸出：3
解釋：s 可以分割為 "RL"、"LLLRRR"、"LR" ，每個子字符串中都包含相同數(shù)量的 'L' 和 'R' 。

示例 3：

輸入：s = "LLLLRRRR"
輸出：1
解釋：s 只能保持原樣 "LLLLRRRR".
</pre>

示例 4：

輸入：s = "RLRRRLLRLL"
輸出：2
解釋：s 可以分割為 "RL"、"RRRLLRLL" ，每個子字符串中都包含相同數(shù)量的 'L' 和 'R' 。

提示：

• 1 <= s.length <= 1000
• s[i] = 'L' 或 'R'
• s 是一個 平衡 字符串

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        """
        貪心算法, 做法類似找字符串的括號數(shù)量是否合法
        """
        balance = 0
        ans = 0
        
        if not s:
            return 0
        
        for i in s:
            if i == "L":
                balance += 1
            elif i == "R":
                balance -= 1
            
            if balance == 0:
                ans += 1
        
        return ans