贪心算法

2023-12-10数据结构与算法9 分钟170 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

简介

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择,就能得到问题的答案。贪心算法需要充分挖掘题目中条件,没有固定的模式,解决有贪心算法需要一定的直觉和经验。

贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

力扣相关算法题:https://leetcode.cn/tag/greedy/problemset/

应用场景

  1. 单源最短路经问题
  2. 最小生成树问题
  3. 可任意分割的背包问题。如果不可以任意分割,就需要用动态规划求解
  4. 某些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似
  5. 活动安排

例题

盛最多水的容器

题目:11.盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明: 你不能倾斜容器。

示例 1:
盛最多水的容器

输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入: height = [1,1]
输出: 1

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

解法:这里我主要用双子针进行收缩,每次选取最小高度的一边计算,获取当前最优的面积区域。

java 复制代码
/**
 * 盛最多水的容器
 * https://leetcode.cn/problems/container-with-most-water/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class M_11 {
    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
    }

    public static int maxArea(int[] height) {
        int left = 0, right = height.length - 1, v = 0;
        // 判断当前左右指针是否相遇
        while (left < right) {
            // 判断当前哪个下标高度小
            if (height[left] < height[right]) {
                // 这里左边的高度小,则取左边的高度进行计算,并尝试让指针右移,看看是否有其它下标的高更大且让面积更大
                v = Math.max(v, getArea(right - left, height[left++]));
            } else {
                // 这里右边的高度小,则取右边的高度进行计算,并尝试让指针左移,看看是否有其它让面积更大的情况
                v = Math.max(v, getArea(right - left, height[right--]));
            }
        }
        return v;
    }

    public static int getArea(int x, int y) {
        return x * y;
    }
}

买卖股票的最佳时机 II

题目:122. 买卖股票的最佳时机 II

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润。

示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。

提示:

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

解法:这里本题只要保证今天比明天的股票价格低,就能获利,所以我们只要把获利的部分累加起来即可。

java 复制代码
/**
 * 122. 买卖股票的最佳时机 II
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class M_122 {

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
    }

    public static int maxProfit(int[] prices) {
        int sum = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                sum += prices[i + 1] - prices[i];
            }
        }
        return sum;
    }
}

最大数

题目:179. 最大数

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:

输入: nums = [10,2]
输出: "210"

示例 2:

输入: nums = [3,30,34,5,9]
输出: "9534330"

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 109

解法:我们可以把这个组合起来的最大数,拆分成两个数之间组成的最大数的子问题,最后排序完后得到的数组,进行拼接,即得出最大数。这里我利用字符串比较是从第一个字符开始逐一比较它们的 ASCII 值的特性,来进行排序:

  • 若x + y > y + x,则 x 排在 y 左边
  • 若y + x > x + y,则 y 排在 x 左边

例如:
x=3,y=30,"330">"303",故 30 应该排在 3 的右边。

java 复制代码
import java.util.Arrays;

/**
 * 最大数
 * https://leetcode.cn/problems/largest-number/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class M_179 {
    public static void main(String[] args) {
        System.out.println(largestNumber(new int[]{3, 30, 34, 5, 9}));
    }

    public static String largestNumber(int[] nums) {
        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = Integer.toString(nums[i]);
        }
        // 让字符串之间拼接比较,比如 3 与 30拼接
        // 判断当前 330大还是 303大,将大的结果排在前边
        Arrays.sort(arr, (x, y) -> {
            // 字符串之间比较默认是从第一个字符开始逐一比较 ASCII 码的值
            return (y + x).compareTo(x + y);
        });
        if ("0".equals(arr[0])) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for (String s : arr) {
            sb.append(s);
        }
        return sb.toString();
    }
}

最长回文串

题目:409. 最长回文串

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

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

示例 1:

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

示例 2:

输入: s = "a"
输出: 1

示例 3:

输入: s = "aaaaaccc"
输出: 7

提示:

  • 1 <= s.length <= 2000
  • s 只由小写 和/或 大写英文字母组成

解法:本题只需要求出回文串的最大长度,而回文串中最多出现一个奇数数量的字符,其它字符均为偶数个。故我们可以先统计字符出现的个数,然后判断累加字符数量,每次遍历的时候先累加偶数个字符数量,并判断如果当前累计的字符数量是偶数个,且当前字符的个数是奇数个,则把累加数加一(保证长度最长),如果累加后的字符数量为奇数个,则之后只需要累加偶数个字符数量即可。

java 复制代码
/**
 * 409. 最长回文串
 * https://leetcode.cn/problems/longest-palindrome/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class S_409 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccccdd"));
    }

    public static int longestPalindrome(String s) {
        int length = s.length();
        if (length == 1) {
            return 1;
        }
        // 统计每个字符出现的次数
        int[] counts = new int[128];
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            counts[c]++;
        }
        // 统计数量
        int sum = 0;
        for (Integer count : counts) {
            // 保证每次先累加当前偶数个字符
            sum += count / 2 * 2;
            // 如果当前字符个数 sum 为偶数,且当前的 count 为奇数,则需要加上去保证对称
            // 如果 sum 为奇数个,则之后只需要添加偶数个字符即可,才能保证对称¬
            if (count % 2 == 1 && sum % 2 == 0) {
                sum += 1;
            }
        }
        return sum;
    }

简写下算法

java 复制代码
/**
 * 409. 最长回文串
 * https://leetcode.cn/problems/longest-palindrome/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class S_409 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccccdd"));
    }

    public static int longestPalindrome(String s) {
        int length = s.length();
        if (length == 1) {
            return 1;
        }
        // 统计每个字符出现的次数
        int[] counts = new int[128];
        // 统计数量
        int sum = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            counts[c]++;
            // 如果当前字符出现过两次,我们就可以把它累加
            // 相当于它在回文串的左右,保证对称
            if (counts[c] == 2) {
                sum += 2;
                // 置零,重新计算后边的出现次数
                // 直到有偶数个出现时,则重新累加
                counts[c] = 0;
            }
        }
        return sum < length ? ++sum : sum;
    }
}

分割数组

题目:915. 分割数组

给定一个数组 nums ,将其划分为两个连续子数组 left 和 right, 使得:

  • left 中的每个元素都小于或等于 right 中的每个元素。
  • left 和 right 都是非空的。
  • left 的长度要尽可能小。
    在完成这样的分组后返回 left 的 长度 。

用例可以保证存在这样的划分方法。

示例 1:

输入:nums = [5,0,3,8,6]
输出:3
解释:left = [5,0,3],right = [8,6]

示例 2:

输入:nums = [1,1,1,0,6,12]
输出:4
解释:left = [1,1,1,0],right = [6,12]

提示:

  • 2 <= nums.length <= 105
  • 0 <= nums[i] <= 106
  • 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

解法:我们可以通过预先计算每个位置右侧的最小值,可以在从左到右的遍历过程中直接比较左侧最大值和右侧最小值,从而找到分割点。

java 复制代码
/**
 * 915. 分割数组
 * https://leetcode.cn/problems/partition-array-into-disjoint-intervals
 *
 * @author Salmon
 * @since 2024-02-28
 */
public class M_915 {
    public static void main(String[] args) {
        System.out.println(partitionDisjoint(new int[]{5, 0, 3, 8, 6}));
        System.out.println(partitionDisjoint(new int[]{1, 1, 1, 0, 6, 12}));
        System.out.println(partitionDisjoint(new int[]{90, 47, 69, 10, 43, 92, 31, 73, 61, 97}));
    }


    public static int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] minRight = new int[n];
        minRight[n - 1] = nums[n - 1]; // 数组最后一个元素肯定在右边

        for (int i = n - 2; i >= 0; i--) {
            // 从右到左,记录当前右数组中,从右到左最小的数,之后从左到右遍历,只要与其比较即可
            minRight[i] = Math.min(nums[i], minRight[i + 1]);
        }
        int maxLeft = 0; // 左数组最大的值
        for (int i = 0; i < n - 1; i++) {
            maxLeft = Math.max(maxLeft, nums[i]);
            // 与之后所有元素中最小的数比较
            // 当前左数组最大值小于等于右数组中最小的值,则当前最大值+1即为左数组的长度
            if (maxLeft <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return n - 1;
    }
}

可拆分背包问题之贪心的自助餐

题目如下:

小BB同学呢,想去吃自助餐,但是他是那种比较节俭的的人,既不想浪费食物,又想尽可能吃的贵一点,他于是私下里做了调查。

小蓝餐厅的自助餐有 nn 种食材,每种食材都有它的价格。

而且也能估计出每一份的重量,所以他列了一个表格。

sh 复制代码
红烧牛肉  30元    300g
油闷大虾  8元     5g
四喜丸子  4元     8g
三文鱼    5元     3g
排骨      18元    200g
麻辣兔头  20元    120g
高汤海参  40元    70g
扇贝粉丝  8元     32g
牛排      79元    240g
...

现在小 BB 想知道在他到底最多吃多少钱的菜品。

假设自助餐厅的菜品供应同样的菜品每个人只能取一份。

小BB的饭量假设为 CC,单位为 gg。

现在请你设计一个程序帮助小BB计算他的最多吃了多少钱。

输入:

输入解法

第一行输入 n,C(0≤n≤1000)(0≤C≤10000)n,C (0 \leq n \leq1000)(0 \leq C \leq10000)

其中 nn 为菜品数量,CC 为小BB的肚子容量。

第二行输入两个数 VV,WW

第一个数 V[i]V[i] 是第 ii 个菜品的价值 (0≤v[i]≤10000)(0\leq v[i]\leq 10000)

第二个数 V[i]V[i] 是第 ii 个菜品的质量 (0≤w[i]≤10000)(0\leq w[i]\leq 10000)

输入样例:

sh 复制代码
20 1000
1 22
2 43
123 214
12 2
123 432
21 223
22 16
77 49
34 78
34 9
43 677
21 34
23 23
12 56
332 56
21 99
123 545
389 33
12 999
23 88

输出:

输出一行数据,表示最大的价值,保留三位小数。

输出样例:

sh 复制代码
1204.114

运行限制:

sh 复制代码
最大运行时间:1s
最大运行内存:128M

解法:对于肚子的容量(背包),菜品(物品),是否能装满的问题,其实是一个经典的背包问题。我们应从中找出具有性价比的物品先放入背包,才能使价值最大化。而我们还需要考虑到两种情况:背包能否装满所有物品,能的话,那就直接装满,不行的话,那就按挑性价比从大到小排序对物品排序,每次放入性价比高的物品来装满,从而使利益最大化。

java 复制代码
import java.util.*;

// 可拆分背包问题之贪心的自助餐
public class Main {

	static class Food implements Comparable<Food> {
		double v; // 菜品价值
		double w; // 菜品质量
		double aver; // 价值商 价值/质量 得出 每克菜品的价值

		public Food(double v, double w) {
			this.v = v;
			this.w = w;
			this.aver = v / w;
		}

		@Override
		public int compareTo(Food o) {
			// 这里从大到小排序
			return this.aver > o.aver ? -1 : 1;
		}
	}

	// 存放菜品
	static Food[] foods = new Food[1010];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		double c = sc.nextInt();

		// 存放菜品,同时记录当前所有菜品的总质量
		double w_sum = 0; // 所有菜品的总质量
		double v_sum = 0;
		for (int i = 0; i < n; i++) {
			double v = sc.nextInt();
			double w = sc.nextInt();
			foods[i] = new Food(v, w);
			w_sum += w;
			v_sum += v;
		}
		// 先看看如果当前背包(肚子)能不能装下所有物品(菜品),那直接全部吃掉
		if (c >= w_sum) {
			System.out.printf("%.3f", v_sum);
			return;
		}

		// 走到这里,说明背包(肚子)不能装下所有物品(菜品),那我们从最有价值(性价比)的开始吃
		double sum = 0;
		// 按价值商(性价比)进行排序 大到小
		Arrays.sort(foods, 0, n);
		
		for (int i = 0; i < n; i++) {
			Food cur = foods[i];
			// 先看看当前吃不吃得下所有菜品
			if (c >= cur.w) {
				c -= cur.w;
				sum += cur.v;
				foods[i].w = 0; // 吃完这个菜品
			} else {
				// 当前吃不下这个菜品所有量,则吃剩余能吃的那份即可
				// 即直接将剩下的 c 用来吃这个即可
				double val = c * cur.aver;
				foods[i].w -= c;
				sum += val;
				c = 0;
			}
			// 装满了(吃饱了)
			if (c == 0) {
				break;
			}
		}
		System.out.printf("%.3f", sum);

	}
}
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句