贪心算法 力扣

### 关于贪心算法在 LeetCode 平台上的题目解析 #### 1. **最长回文串** 此题的目标是从给定字符串中找到可以构成的最大长度的回文子序列。通过贪心策略，我们可以尝试尽可能多地匹配字符来构建回文结构。 实现方式如下： - 使用 `Counter` 来统计每个字符出现的次数。 - 对于偶数次出现的字符可以直接计入回文中；对于奇数次出现的字符，最多只能取其最大偶数值加入到回文中[^1]。 ```python from collections import Counter def longestPalindrome(s: str) -> int: counts = Counter(s) length = 0 odd_found = False for count in counts.values(): if count % 2 == 0: length += count else: length += count - 1 odd_found = True if odd_found: length += 1 return length ``` --- #### 2. **柠檬水找零** 该问题描述了一个场景：顾客购买价值 $5 的商品并支付不同面额的钱币 ($5, $10, 和 $20)，我们需要判断能否成功完成所有交易而不缺少找零。 解决方法基于贪心原则——优先处理大金额钱币以便保留更多小额硬币用于后续操作[^3]： ```java class Solution { public boolean lemonadeChange(int[] bills) { int five = 0; int ten = 0; for (int bill : bills) { if (bill == 5) { five++; } else if (bill == 10) { if (five == 0) return false; five--; ten++; } else { // bill == 20 if (ten > 0 && five > 0) { ten--; five--; } else if (five >= 3) { five -= 3; } else { return false; } } } return true; } } ``` --- #### 3. **分发饼干** 目标是将若干大小不同的饼干分配给孩子，使得尽可能多的孩子感到满意（即孩子的胃口需求小于等于饼干尺寸）。采用排序加双指针的方法能够高效解决问题[^4]。 代码示例如下： ```python from typing import List class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() child, cookie = 0, 0 while child < len(g) and cookie < len(s): if g[child] <= s[cookie]: child += 1 cookie += 1 return child ``` --- #### 4. **根据身高重建队列** 这道题要求按照特定规则重新排列一组人员的位置。先按高度降序排列再插入对应索引位置即可达成目的。 以下是 Python 版本解决方案： ```python class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: people.sort(key=lambda x: (-x[0], x[1])) result = [] for p in people: result.insert(p[1], p) return result ``` --- #### 5. **摆动序列** 定义一个数组中的“峰值”和“谷值”，并通过遍历一次数组计算出可能存在的波峰数量作为最终答案的一部分[^5]。 具体做法如下所示： ```python class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: if not nums: return 0 up, down = 1, 1 for i in range(1, len(nums)): if nums[i] > nums[i - 1]: up = down + 1 elif nums[i] < nums[i - 1]: down = up + 1 return max(up, down) ``` --- ### 总结 上述各例展示了如何利用贪心算法有效求解实际编程竞赛中的经典难题。每种情况都遵循局部最优决策从而达到全局较佳效果的原则[^2]。