当前位置：首页 > article >正文

算法入门-贪心1

article 2024/9/23 19:19:25

第八部分：贪心

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

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

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

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

局部最优选择：

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

排序：

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

不回溯：

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

全局最优解的构建：

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

总结

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