算法入门-贪心1

第八部分：贪心

409.最长回文串（简单）

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的最长的回文串 的长度。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输出:1
解释：可以构造的最长回文串是"a"，它的长度是 1。

第一种思路：

看到这种需要统计数量的，不自然的会想到使用字典的数据结构，按照这种思路，我考虑如下：

1. 空字符串检查：

• 首先检查输入字符串 s 是否为空。如果为空，直接返回0，因为没有字符可以构成回文串。

1. 字符计数：

• 使用一个 HashMap 来统计字符串中每个字符的出现次数。遍历字符串中的每个字符，更新其在 map 中的计数。

1. 计算回文串长度：

• 初始化 sum 为0，用于存储可以构成的最长回文串的长度。

• 遍历map中的每个字符及其出现次数：

  • 如果出现次数是偶数，则可以完全加入到回文串中，直接加到 sum。

  • 如果出现次数是奇数，则将其减一后加入到 sum，并标记存在奇数值的键，以便后续可以在回文串的中心添加一个字符。

1. 中心字符处理：

• 如果存在奇数值的键，说明可以在回文串的中心添加一个字符，因此在 sum 上加1。

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/

1. 字符计数：

   • 使用一个长度为128的数组 count 来统计字符串中每个字符的出现次数。数组的索引对应字符的ASCII值。

   • 遍历字符串 s，对于每个字符 c，增加 count[c] 的值。

2. 计算回文串长度：

   • 初始化 ans 为0，用于存储可以构成的最长回文串的长度。

   • 遍历count数组，对于每个字符的出现次数v：

     • 使用 v / 2 * 2 计算出可以组成的偶数部分，并加到 ans 中。这样可以确保回文串的左右两边是对称的。

     • 如果 v 是奇数，并且当前的 ans 是偶数，说明可以在回文串的中心添加一个字符（即使得回文串的长度增加1），因此将 ans 加1。

3. 返回结果：

   • 最后返回 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。

第一种思路： 首先采用之前刷题的经验，先把这两个数组进行排序，减少工作量。

然后使用双指针的方法遍历两个数组，避免双重循环。

具体而言：

1. 排序：首先对孩子的胃口数组 g 和饼干的大小数组 s 进行排序。这是为了能够从最小的胃口和最小的饼干开始进行比较，确保尽可能多的孩子能够得到满足。

2. 双指针法：使用两个指针 childIndex 和 cookieIndex 分别指向孩子和饼干的当前索引。childIndex 用于遍历孩子，cookieIndex 用于遍历饼干。

3. 满足条件：

   • 如果当前饼干可以满足当前孩子的胃口，即 g[childIndex] <= s[cookieIndex]，则增加满足的孩子计数 contentChildrenCount，并同时移动到下一个孩子和下一个饼干。

   • 如果当前饼干不能满足当前孩子，则只移动到下一个饼干，继续尝试满足当前孩子。

4. 结束条件：当遍历完所有孩子或所有饼干时，循环结束，返回满足的孩子数量。

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; // 返回满足的孩子数量  }  
}

后面发现官方的解答和我类似，但是他就是使用双重循环的，想了一下。

贪心算法的贪心在这里面体现在哪？

在这个问题中，贪心算法的贪心策略体现在以下几个方面：

1. 局部最优选择：

   • 每次选择当前最小的饼干来满足当前最小的孩子的胃口。这种选择是基于局部最优的原则，即在每一步中都选择能够立即满足当前孩子的最小饼干。通过这种方式，尽可能多的孩子能够得到满足。

2. 排序：

   • 通过对孩子的胃口和饼干的大小进行排序，确保我们可以从最小的开始进行比较。这种排序使得我们能够有效地找到最小的满足条件的饼干，从而实现贪心选择。

3. 不回溯：

   • 一旦选择了一个饼干来满足一个孩子，就不会回头去尝试用这个饼干去满足其他孩子。每次都向前推进，确保每个孩子都尽可能得到满足，而不去重新考虑之前的选择。

4. 全局最优解的构建：

   • 通过不断地做出局部最优选择（即用当前最小的饼干满足当前最小的孩子），最终构建出全局最优解（即最大数量的孩子得到满足）。这种策略在许多贪心算法中都是常见的。

总结

贪心算法在这个问题中的核心思想是通过局部最优选择（最小饼干满足最小胃口）来达到全局最优解（最大数量的孩子得到满足）。这种方法简单高效，适合解决此类问题。