java实现贪心算法

介绍

贪心算法是一种在每一步决策时都采取当前状态下的最优选择，从而希望导致全局最优解的算法策略，它总是做出在当前看来是最好的选择，但不会考虑这个选择对未来可能产生的影响，也不会回溯去改变之前的决策，就像是一个贪婪的人，在每一个选择点只考虑眼前的最大利益。

Java是面向对象的编程语言，具有丰富的类库和数据结构，这使得在实现贪心算法时，可以方便地利用已有的数据结构，如数组、列表、集合等，来存储和操作数据。

题目1

假设有一个花坛，部分地块已经种了花，用数组 flowerbed 表示， 1 表示已种花， 0 表示未种花。另有一个整数 n 代表还能种的花的数量，要求相邻地块不能同时种花，判断能否种下 n 朵花。

例如，flowerbed = [1, 1, 1, 0, 0] ，n = 1，在这个例子中，可以在索引为 4的位置种下一朵花，所以返回 true 。

解题思路
 
贪心策略在于每次选择当前情况下能种花的位置就种下花，尽可能地利用可种花的机会，以达到种下最多花的目的，然后判断可种花的数量，得出答案。

代码实现

public class Main {
    public static boolean Flowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            // 当前地块为空（即flowerbed[i] == 0）
            // 前一个地块为空（i == 0或者flowerbed[i - 1] == 0）
            // 后一个地块为空（i == flowerbed.length - 1或者flowerbed[i + 1] == 0）
            // 满足以上三个条件则使count++
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;
                count++;
            }
            // 如果已经种下了足够数量的花，就返回true
            if (count >= n) {
                return true;
            }
        }
        return count >= n;
    }
    public static void main(String[] args) {
        int[] flowerbed = {1,0,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,0,1,1};
        int n = 5;
        boolean result = Flowers(flowerbed, n);
        System.out.println("能否种下指定数量的花: " + result);
    }

}

代码中定义了一个变量 count ，用于记录已经种下的花的数量，初始为 0 ，然后通过一个循环遍历整个花坛数组 flowerbed，对于每一个位置 i ，判断是否满足种花的条件，种花的条件是当前地块为空（flowerbed[i] == 0），并且前一个地块为空（i == 0 或者 flowerbed[i - 1] == 0），并且后一个地块为空（ i == flowerbed.length - 1或者flowerbed[i + 1] == 0），这是因为种植规则要求相邻地块不能同时种花，如果满足这些条件，就将当前地块标记为已种花（flowerbed[i] = 1），并将 count 加 1。在每次种下花后，检查是否已经种下了足够数量的花（ count >= n ），如果是，就直接返回 true 。

（取自leedcode605)

题目2

给定一个表示书籍难度的整数数组 books ，以及学生的数量 m 。要求找到一种书籍分配方案，使得每个学生分配到的书的难度总和的最大值尽可能小。例如，有5本书难度分别为 {1, 2, 3, 4, 5} ，如果学生数量 m 为2，那么可能的分配方案有多种，但要找到那种能让两个学生所分配到的书籍难度总和中较大的那个值最小的分配方式。

那么答案为9（4+5）

解题思路

看上去像是数学中的隔板问题，其实不然，我们要在所有可能的分配方案中，找到满足学生数量限制且能使每个学生分配到的书的难度总和的最大值最小的那个方案，这里采取逐步尝试的思路。

import java.util.Arrays;

public class Main {
    // 检查是否能以给定的最大难度分配书籍给学生
    private static boolean canAllocate(int[] books, int m, int maxDifficulty) {
        int studentCount = 1;
        int currentSum = 0;

        for (int bookDifficulty : books) {
            if (currentSum + bookDifficulty > maxDifficulty) {
                studentCount++;
                currentSum = bookDifficulty;
            } else {
                currentSum += bookDifficulty;
            }
        }

        return studentCount <= m;
    }
    // 找到每个学生分配到的书的难度总和的最大值最小的分配方案
    public static int minDifficulty(int[] books, int m) {
        if (m > books.length) {
            return -1;
        }
        int maxBookDifficulty = Arrays.stream(books).max().getAsInt();
        int totalBookDifficulty = Arrays.stream(books).sum();
        // 从最大的单本书难度开始
        for (int i = maxBookDifficulty; i <= totalBookDifficulty; i++) {
            if (canAllocate(books, m, i)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] books = {1, 2, 3, 4, 5};
        int m = 2;
        int min= minDifficulty(books, m);
        System.out.println("每个学生分配到的书的难度总和的最大值最小为: " + min);
    }

}

在canAllocate方法中首先初始化studentCount为1，表示至少有一个学生，currentSum为0，用于累加当前正在分配给某个学生的书籍难度总和，然后遍历书籍数组  books  中的每一本书的难度  bookDifficulty，
如果当前累加的难度总和currentSum加上当前这本书的难度超过了给定的最大难度maxDifficulty ，那就意味着需要给下一个学生分配书了，所以studentCount加1，并且将currentSum更新为当前这本书的难度，如果没有超过给定的最大难度，就把当前这本书的难度累加到  currentSum  中，最后，返回  studentCount <= m  的结果。

题目3

柠檬水一杯卖5美元，顾客排队依次买一杯，付5美元、10美元或20美元。开始没零钱，给你整数数组bills，若能给每位顾客正确找零，返回true，否则返回false。

例如：bills = [5,5,5,10,20] 输出：true

解题思路

我们要根据顾客付款的顺序模拟找零过程，看是否能在整个交易过程中给每一位顾客都正确找零，最终确定是否能满足每位顾客净支付5美元的条件，因为20美元找零需要消耗10美元和5美元，10美元找零需要消耗5美元，所以统计5美元和10美元的数量即可。

public class Main {
    public static void main(String[] args) {
        int[] bills = {5,5,5,10,20,20};
        int sumFive = 0;
        int sumTen = 0;
        for (int bill : bills) {
            if (bill == 5) {
                sumFive ++;
            }else if (bill == 10) {
                sumTen ++;
                sumFive--;
            }else{
                sumTen--;
                sumFive--;
            }
        }
        if (sumFive<0 || sumTen<0) {
            System.out.println(false);
        }else {
            System.out.println(true);
        }
    }
}

收到三张5元钞票， sumFive变为3。
收到一张10元钞票，需要找零一张5元，sumFive变为2，sumTen变为1。
收到一张20元钞票，需要找零一张10元和一张5元， sumTen变为0，sumFive变为1。
再收到一张20元钞票，尝试找零一张10元和一张5元，但此时没有10元钞票，因此sumTen变为-1，sumFive变为0。
（取自leedcode860)

贪心算法是一个强有力的解决问题的工具，它简单高效，但并不总是能得到最优解，在设计贪心算法时，证明问题具有贪心选择性质和最优子结构是至关重要的。如果这两个性质中的一个不成立，贪心算法可能不会给出正确答案。因此，在应用贪心算法之前，理解问题的性质是非常重要的。