贪心算法

409. 最长回文串给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 1234输入:s = "abccccdd"输出:7解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。 示例 2: 123输入:s = "a"输出:1解释：可以构造的最长回文串是"a"，它的长度是 1。 解题思路核心思路是统计字符频率，利用回文串的特性计算最大长度： 回文串特性： 回文串对称位置的字符相同； 偶数长度的回文串：所有字符出现次数均为偶数； 奇数长度的回文串：仅有一个字符出现奇数次（位于中心），其余均为偶数次。 频率统计： 统计字符串中每个字符的出现次数； 累计所有字符的最大偶数次（例如，出现 5 次的字符可贡献 4 次）； 若存在出现奇数次的字符，可在结果中加 1（作为中心字符）。 计算逻辑： 初始化结果...

45. 跳跃游戏 II给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处： 0 <= j <= nums[i] 且 i + j < n 返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。 示例 1: 1234输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2: 12输入: nums = [2,3,0,1,4]输出: 2 解题思路核心思路是贪心算法，通过跟踪 “当前跳跃的最远边界” 和 “下一次跳跃的最远可达位置”，在每一步跳跃时选择最优范围，实现最少跳跃次数： 贪心策略： 用 end 表示当前跳跃能到达的最远边界（初始为 0）； 用 max_reach 表示从当前位置到 end 之间的所有位置能跳到的最远位置； 用...

55. Jump GameYou are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Example 1: 123Input: nums = [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: 123Input: nums = [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter...

53. Maximum SubarrayGiven an integer array nums, find the subarray with the largest sum, and return its sum. Example 1: 123Input: nums = [-2,1,-3,4,-1,2,1,-5,4]Output: 6Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: 123Input: nums = [1]Output: 1Explanation: The subarray [1] has the largest sum 1. Example 3: 123Input: nums = [5,4,-1,7,8]Output: 23Explanation: The subarray [5,4,-1,7,8] has the largest sum 23. 题目大意给定一个整数数组...

455. Assign CookiesAssume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number. Example...