算法-贪心思想
2021/8/2 9:05:51
本文主要是介绍算法-贪心思想,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法-贪心思想
庭前看玉树,肠断忆连枝
一、剪绳子
1、题目描述
把一根绳子剪成多段,并且使得每段的长度乘积最大。
n = 2 return 1 (2 = 1 + 1) n = 10 return 36 (10 = 3 + 3 + 4)
2、解题思路
贪心
尽可能得多剪长度为 3 的绳子,并且不允许有长度为 1 的绳子出现。如果出现了,就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合,把它们切成两段长度为 2 的绳子。以下为证明过程。
将绳子拆成 1 和 n-1,则 1(n-1)-n=-1<0,即拆开后的乘积一定更小,所以不能出现长度为 1 的绳子。
将绳子拆成 2 和 n-2,则 2(n-2)-n = n-4,在 n>=4 时这样拆开能得到的乘积会比不拆更大。
将绳子拆成 3 和 n-3,则 3(n-3)-n = 2n-9,在 n>=5 时效果更好。
将绳子拆成 4 和 n-4,因为 4=2*2,因此效果和拆成 2 一样。
将绳子拆成 5 和 n-5,因为 5=2+3,而 5<2*3,所以不能出现 5 的绳子,而是尽可能拆成 2 和 3。
将绳子拆成 6 和 n-6,因为 6=3+3,而 6<3*3,所以不能出现 6 的绳子,而是拆成 3 和 3。这里 6 同样可以拆成 6=2+2+2,但是 3(n - 3) - 2(n - 2) = n - 5 >= 0,在 n>=5 的情况下将绳子拆成 3 比拆成 2 效果更好。
继续拆成更大的绳子可以发现都比拆成 2 和 3 的效果更差,因此我们只考虑将绳子拆成 2 和 3,并且优先拆成 3,当拆到绳子长度 n 等于 4 时,也就是出现 3+1,此时只能拆成 2+2。
1 public class Solution { 2 public int cutRope(int target) { 3 if(target < 2){ 4 return 0; 5 } 6 if(target == 2){ 7 return 1; 8 } 9 if(target == 3){ 10 return 2; 11 } 12 /* 13 * 8/3 = 2, 9/3 =3, 10/3 =3 14 */ 15 int timeOf3 = target /3; // 3的倍数 16 if(target - timeOf3 * 3 == 1){ 17 timeOf3--; 18 } 19 int timeOf2 = (target - timeOf3 * 3) / 2; // 2的倍数 20 return (int)(Math.pow(3, timeOf3)) * (int)(Math.pow(2, timeOf2)); 21 22 } 23 }View Code
二、股票的最大利润
1、题目描述
可以有一次买入和一次卖出,买入必须在前。求最大收益。
输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
2、解题思路
使用贪心策略,假设第 i 轮进行卖出操作,买入操作价格应该在 i 之前并且价格最低。因此在遍历数组时记录当前最低的买入价格,并且尝试将每个位置都作为卖出价格,取收益最大的即可。
1 class Solution { 2 public int maxProfit(int[] prices) { 3 if(prices == null || prices.length == 0){ 4 return 0; 5 } 6 int soFarMin = prices[0]; 7 int maxProfit = 0; 8 for(int i = 1; i < prices.length; i++){ 9 soFarMin = Math.min(soFarMin, prices[i]); 10 // 返回参数中的最大值 Math.max() 11 maxProfit = Math.max(maxProfit, prices[i] - soFarMin); 12 } 13 return maxProfit; 14 } 15 }
庭前看玉树
肠断忆连枝
这篇关于算法-贪心思想的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding