算法入门-贪心1
第八部分：贪心
409.最长回文串（简单）
给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的最长的回文串 的长度。
在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
示例 1:
输入:s = "abccccdd" 输出:7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:
输入:s = "a" 输出:1 解释：可以构造的最长回文串是"a"，它的长度是 1。
第一种思路：
看到这种需要统计数量的，不自然的会想到使用字典的数据结构，按照这种思路，我考虑如下：
空字符串检查：
首先检查输入字符串
s是否为空。如果为空，直接返回0，因为没有字符可以构成回文串。
字符计数：
使用一个
HashMap来统计字符串中每个字符的出现次数。遍历字符串中的每个字符，更新其在map中的计数。
计算回文串长度：
初始化
sum为0，用于存储可以构成的最长回文串的长度。遍历map中的每个字符及其出现次数：
如果出现次数是偶数，则可以完全加入到回文串中，直接加到
sum。如果出现次数是奇数，则将其减一后加入到
sum，并标记存在奇数值的键，以便后续可以在回文串的中心添加一个字符。
中心字符处理：
如果存在奇数值的键，说明可以在回文串的中心添加一个字符，因此在
sum上加1。
返回结果：
最后返回
sum，即为通过给定字符串构造的最长回文串的长度。
import java.util.HashMap;
import java.util.Map; class Solution { public int longestPalindrome(String s) { // 检查字符串是否为空 if (s.length() == 0) { return 0; // 如果字符串为空，直接返回0 } int sum = 0; // 用于存储可以构成的最长回文串的长度 boolean hasOddValue = false; // 用于跟踪是否存在奇数值的键 Map<Character, Integer> map = new HashMap<>(); // 创建一个HashMap来存储字符及其出现次数 // 遍历字符串中的每个字符 for (char ch : s.toCharArray()) { // 更新字符的出现次数 map.put(ch, map.getOrDefault(ch, 0) + 1); } // 遍历字符计数的映射 for (Map.Entry<Character, Integer> entry : map.entrySet()) { int value = entry.getValue(); // 获取当前字符的出现次数 if (value % 2 == 0) { // 如果出现次数是偶数 sum += value; // 偶数部分可以完全加入到回文串中 } else { // 如果出现次数是奇数 sum += (value - 1); // 奇数部分减一后加入到回文串中 hasOddValue = true; // 标记存在奇数值的键 } } // 如果存在奇数值的键，则可以在回文串的中心添加一个字符 if (hasOddValue) { sum += 1; // 增加1以考虑中心字符 } return sum; // 返回计算得到的最长回文串长度 } // 辅助方法：检查字符串中的所有字符是否相同 private boolean allCharactersSame(String s) { char firstChar = s.charAt(0); // 获取第一个字符 for (int i = 1; i < s.length(); i++) { if (s.charAt(i) != firstChar) { return false; // 如果发现不同的字符，返回false } } return true; // 所有字符相同，返回true }
}第二种思路： 采用官方的贪心思路（不管我暂时还没有从官方的解释中体会到贪心体现在哪里）
解释：那么我们如何通过给定的字符构造一个回文串呢？我们可以将每个字符使用偶数次，使得它们根据回文中心对称。在这之后，如果有剩余的字符，我们可以再取出一个，作为回文中心。
于每个字符 ch，假设它出现了 v 次，我们可以使用该字符 v / 2 * 2 次，在回文串的左侧和右侧分别放置 v / 2 个字符 ch，其中 / 为整数除法。例如若 "a" 出现了 5 次，那么我们可以使用 "a" 的次数为 4，回文串的左右两侧分别放置 2 个 "a"。
如果有任何一个字符 ch 的出现次数 v 为奇数（即 v % 2 == 1），那么可以将这个字符作为回文中心，注意只能最多有一个字符作为回文中心。在代码中，我们用 ans 存储回文串的长度，由于在遍历字符时，ans 每次会增加 v / 2 * 2，因此 ans 一直为偶数。但在发现了第一个出现次数为奇数的字符后，我们将 ans 增加 1，这样 ans 变为奇数，在后面发现其它出现奇数次的字符时，我们就不改变 ans 的值了。
详情见：409. 最长回文串 - 力扣（LeetCode）
https://leetcode.cn/problems/longest-palindrome/
字符计数：
使用一个长度为128的数组
count来统计字符串中每个字符的出现次数。数组的索引对应字符的ASCII值。遍历字符串
s，对于每个字符c，增加count[c]的值。计算回文串长度：
初始化
ans为0，用于存储可以构成的最长回文串的长度。遍历count数组，对于每个字符的出现次数v：
使用
v / 2 * 2计算出可以组成的偶数部分，并加到ans中。这样可以确保回文串的左右两边是对称的。如果
v是奇数，并且当前的ans是偶数，说明可以在回文串的中心添加一个字符（即使得回文串的长度增加1），因此将ans加1。返回结果：
最后返回
ans，即为通过给定字符串构造的最长回文串的长度。
class Solution { public int longestPalindrome(String s) { // 创建一个长度为128的数组，用于统计字符的出现次数 int[] count = new int[128]; int length = s.length(); // 遍历字符串，统计每个字符的出现次数 for (int i = 0; i < length; ++i) { char c = s.charAt(i); count[c]++; // 增加字符c的计数 } int ans = 0; // 用于存储最长回文串的长度 // 遍历计数数组，计算可以构成的回文串长度 for (int v : count) { ans += v / 2 * 2; // 将偶数部分直接加到ans中 // 如果当前字符的出现次数为奇数，并且ans是偶数，则可以加1 if (v % 2 == 1 && ans % 2 == 0) { ans++; // 可以在回文串的中心添加一个字符 } } return ans; // 返回计算得到的最长回文串长度 }
}455.分发饼干（简单）
题目：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。
示例 2:
输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出 2。
第一种思路： 首先采用之前刷题的经验，先把这两个数组进行排序，减少工作量。
然后使用双指针的方法遍历两个数组，避免双重循环。
具体而言：
排序：首先对孩子的胃口数组
g和饼干的大小数组s进行排序。这是为了能够从最小的胃口和最小的饼干开始进行比较，确保尽可能多的孩子能够得到满足。双指针法：使用两个指针
childIndex和cookieIndex分别指向孩子和饼干的当前索引。childIndex用于遍历孩子，cookieIndex用于遍历饼干。满足条件：
如果当前饼干可以满足当前孩子的胃口，即
g[childIndex] <= s[cookieIndex]，则增加满足的孩子计数contentChildrenCount，并同时移动到下一个孩子和下一个饼干。如果当前饼干不能满足当前孩子，则只移动到下一个饼干，继续尝试满足当前孩子。
结束条件：当遍历完所有孩子或所有饼干时，循环结束，返回满足的孩子数量。
class Solution { public int findContentChildren(int[] g, int[] s) { // 对孩子的胃口和饼干的大小进行排序 Arrays.sort(g); Arrays.sort(s); int contentChildrenCount = 0; // 记录满足的孩子数量 int childIndex = 0; // 当前孩子的索引 int cookieIndex = 0; // 当前饼干的索引 // 遍历孩子和饼干，直到其中一个数组遍历完 while (childIndex < g.length && cookieIndex < s.length) { // 如果当前饼干可以满足当前孩子的胃口 if (g[childIndex] <= s[cookieIndex]) { contentChildrenCount++; // 满足一个孩子 childIndex++; // 移动到下一个孩子 } // 无论饼干是否满足孩子，都要移动到下一个饼干 cookieIndex++; } return contentChildrenCount; // 返回满足的孩子数量 }
}后面发现官方的解答和我类似，但是他就是使用双重循环的，想了一下。
贪心算法的贪心在这里面体现在哪？
在这个问题中，贪心算法的贪心策略体现在以下几个方面：
局部最优选择：
每次选择当前最小的饼干来满足当前最小的孩子的胃口。这种选择是基于局部最优的原则，即在每一步中都选择能够立即满足当前孩子的最小饼干。通过这种方式，尽可能多的孩子能够得到满足。
排序：
通过对孩子的胃口和饼干的大小进行排序，确保我们可以从最小的开始进行比较。这种排序使得我们能够有效地找到最小的满足条件的饼干，从而实现贪心选择。
不回溯：
一旦选择了一个饼干来满足一个孩子，就不会回头去尝试用这个饼干去满足其他孩子。每次都向前推进，确保每个孩子都尽可能得到满足，而不去重新考虑之前的选择。
全局最优解的构建：
通过不断地做出局部最优选择（即用当前最小的饼干满足当前最小的孩子），最终构建出全局最优解（即最大数量的孩子得到满足）。这种策略在许多贪心算法中都是常见的。
总结
贪心算法在这个问题中的核心思想是通过局部最优选择（最小饼干满足最小胃口）来达到全局最优解（最大数量的孩子得到满足）。这种方法简单高效，适合解决此类问题。