Greedy Algorithm EASY 21.11.05

Greedy Algorithm EASY 21.11.05

Greedy Algorithm EASY 21.11.05

• • 409.最长回文串
  • • 什么是贪心算法？
    • 解题思路
    • 代码实现
    • • Python代码
      • Java代码
  • 455.分发饼干
  • • 解题思路
    • 代码实现
    • • 自己写的python代码
      • 改进的Python代码
      • Java代码
  • 次回预告

---

409.最长回文串

题目说明

---

什么是贪心算法？

贪心算法是指总是做出在当前看来是最好的选择。如果你是第一次听说贪心算法，那么你可以去阅读《算法图解》第八章。

• 注意，题目难易程度为简单，只要求返回最长串的长度，没要求返回具体回文串序列，因为最长串有很多组合，这也说明贪心算法一般用来求解近似解，没有唯一解。

---

解题思路

1. 一般看到这种需要统计字母个数的，直接想到用哈希表，也称为散列表，在Python里对应的是字典。
2. 考虑两种情况：
   – 如果目标最长串为奇数，那么只能是正中间只有一个孤单的字母（也可能是3个5个…）
   – 如果目标最长串为偶数，那么就是正中间两个是相同的字母
3. 在得到第1步的散列表后，对字典进行遍历，如果某个字母的个数为
   – 偶数，那太省事了，直接全部拿来在两边坐好
   – 奇数，这里就又要分两次情况了：
   • 如果是第一次遇到奇数，那也很省事，拿出一个放中间，剩下的在两边坐好
   • 如果不是第一次遇到奇数，那就取偶数个该字母出来在两边坐好

---

代码实现

---

Python代码

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        dic = {}
        for item in s:
            if item not in dic:
                dic[item] = 1
            else:
                dic[item] += 1
        flag = True
        length = 0
        for item in dic:
            if dic[item] % 2 == 0:
                length = length + dic[item]
            elif flag:
                length = length + dic[item]
                flag = False
            else:
                length = length + dic[item] - 1
        return length

---

Java代码

class Solution {
    public int longestPalindrome(String s) {

    }
}

---

455.分发饼干

题目说明

---

解题思路

注意题目信息：饼干不用切开，且每个孩子最多只能给一块饼干。那么一句话就完事了：最大尺寸的饼干给胃口最大的孩子。

1. 取出一块最大尺寸的饼干，如果有孩子的胃口比该饼干小，那把这块饼干发给那些胃口比该饼干小的孩子们中胃口最大的那个
2. 让那个拿到饼干的孩子到一边吃饼干去
3. 取出下一块最大尺寸的饼干，和第1步同样的做法
4. 终止条件：如果最大尺寸的饼干都不能满足孩子们的胃口，那没事了，你不愿意要我还不愿意给呢，我可以下班了。

---

代码实现

---

自己写的python代码

(自己写的，执行用时9000ms)

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        num = 0
        while s != [] and g != []:
            if max(s) < min(g):
                break
            if max(s) >= max(g):
                num += 1
                s.remove(max(s))
                g.remove(max(g))
            else:
                g.remove(max(g))
        return num

官方题解先对g和s进行排序。

改进的Python代码

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        s.sort()
        g.sort()
        num = 0
        i = len(s) - 1
        j = len(g) - 1
        while i >= 0 and j >= 0:
            if s[i] < g[0]:
                break
            if s[i] >= g[j]:
                num += 1
                i = i - 1
                j = j - 1
            else:
                j = j - 1
        return num

---

Java代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = g.length - 1;
        int j = s.length - 1;
        int num = 0;
        while (i>=0 && j>=0){
            if (g[0] > s[j]){
                break;
            }
            if (g[i] <= s[j]){
                i = i - 1;
                j = j - 1;
                num = num + 1;
            }else {
                i = i - 1;
            }
        }
        return num;
    }
}

执行时间7ms，惊了。

---

次回预告

1. 补充455题python改进代码（完成）
2. 继续贪婪(简单)算法：561.数组拆分I；605.种花问题