【算法思维】-- 贪心算法

这篇具有很好参考价值的文章主要介绍了【算法思维】-- 贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

OJ须知:

  • 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间(中值5*10e8)。在竞赛中,一般认为计算机1秒能执行 5*10e8 次计算
时间复杂度 取值范围
o(log2n) 大的离谱
O(n) 10e8
O(nlog(n)) 10e6
O(nsqrt(n))) 10e5
O(n^2) 5000
O(n^3) 300
O(2^n) 25
O(3^n) 15
O(n!)

11

时间复杂度排序:o(1) < o(log2n) < o(n) < o(nlog2n) < o(n^2) < o(n^3) < o(2^n) < o(2^n) < o(3^n) < o(n!)


目录

算法思想

算法局限性

过程

案例

平衡分割字符串⭐

方法一:贪心

复杂度分析

买股票的最佳时机2⭐⭐

方法一:贪心 

复杂度分析

跳跃游戏⭐⭐

方法一:贪心(nums[i] == 0为核心)

复杂度分析

方法二:贪心(nums[i]为核心)


算法思想

        贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

融汇贯通的理解:

        贪心算法是不会考虑全局的,其每一步都会确定当前其所看到的场景下的最优的一个解  —— 整个贪心问题的解:每一步的最优解叠加之后的结果。

        有一个概念,就叫做最优子结构:每一个子问题,其的最优解最终叠加之后,能够作为最终问题的解,那就是最优子结构

融汇贯通的理解:

        所以,如果想用贪心算法,首先就要去确定一下,这个问题是不是最优子结构(将问题进行一定的缩小,查看缩小版是否符合最优子结构

算法局限性

        用贪心算法的时候,其如果不是一个最优子结构,那我们得到的这一个解,其不一定是全局的一个最优解,有可能是一个局部的最优解。

  • 不能保证求得的最后解是最佳的
  • 不能用来求最大值最小值的问题
  • 只能求满足某些约束条件可行解的范围比

过程

  1. 建立数学模型来描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每一子问题求解,得到子问题的局部最优解
  4. 把子问题的局部最优解合成原来解问题的一个解

        说白了就是:假设一个问题比较复杂,暂时找不到全局最优解,那么我们可以考虑把原问题拆成几个小问题(分而治之的思想),分别求每个小问题的最优解,再把这些 “局部最优解” 叠起来,就 “当作” 整个问题的最优解了。

案例

        在我们排序所学知识中,选择排序就很好的诠释了贪心算法的使用。

【算法思维】-- 贪心算法

        其每一次的排序都是选择未排序的区间内的最小值。 所以这个地方每一个子问题,其的最优解最终叠加之后,能够作为最终问题的解,所以是一个最优子结构

//直接插入排序
// 对比 插入排序,谁更小。
void SelectSort(int* a, int n)
{
	assert(a);
	int begin_i = 0, end_i = n - 1;
	while (begin_i < end_i)
	{
        // 贪心算法: 每次从未排序数组中找到最小值
		int min_i = begin_i;
		for (int i = begin_i + 1; i <= end_i; ++i)
		{
			if (a[i] < a[min_i])
				min_i = i;
		}

		Swap(&a[begin_i], &a[min_i]);
		++begin_i;
	}
}

        贪心算法:每次找当前情况的最优解,不用考虑上一步是什么 / 下一步是什么。

平衡分割字符串⭐

1221. 分割平衡字符串 - 力扣(LeetCode)


平衡字符串 中,'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s,请你将它分割成尽可能多的子字符串,并满足:

        每个子字符串都是平衡字符串。
返回可以通过分割得到的平衡字符串的 最大数量 。

提示:

  • 2 <= s.length <= 1000
  • s[i] = 'L' 或 'R'
  • s 是一个 平衡 字符串

方法一:贪心

抽象题中线索:

  • 整体策略:不能让平衡字符串嵌套
  • 当前情况决策:当前情况下的字符串,是否符合平衡分割字符串
class Solution {
public:
    int balancedStringSplit(string s) {
        int ret = 0;
        int balance = 0;
        for(auto ch : s)
        {
            // 当前情况决策: 当前情况下的字符串,是否符合平衡分割字符串
            ch == 'L' ? balance++ : balance--;
            if(balance == 0) ret++;
        }
        return ret;
    }
};

复杂度分析

  • 时间复杂度:O(n)。
  • 空间复杂度:O(1)。

买股票的最佳时机2⭐⭐

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


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

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

也可以先购买,然后在 同一天 出售。

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

提示:

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

方法一:贪心 

抽象题中线索:

  • 整体策略:不能股票的购买售出嵌套
  • 当前情况决策:当前情况下的股票以最低价买入,然后以高价售出

【算法思维】-- 贪心算法

就是判断趋势:

  • 连续上涨:上涨的最低点买入,上涨的最高点卖出 —— 上涨区间中买卖绝对利润相同。
  • 连续下跌:不进行买卖。
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int buy = prices[0];
        int sell = 0;
        for(int i = 1; i < prices.size(); i++)
        {
            // 判断趋势
            if(prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        }
        return profit;
    }
};

复杂度分析

  • 时间复杂度:O(n)。
  • 空间复杂度:O(1)。

跳跃游戏⭐⭐

55. 跳跃游戏 - 力扣(LeetCode)


给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

提示:

  • 1 <= nums.length <= 3 * 10e4
  • 0 <= nums[i] <= 105

方法一:贪心(nums[i] == 0为核心)

抽象题中线索:

  • 整体策略:不要嵌套nums[i] == 0。
  • 当前情况决策:当前情况下有nums[i] == 0,其前面的最大值是否跨的过

需要注意:最后一个数据为0,不用提出,已经到最后了。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max = 0;
        for(int i = 0; i < nums.size() - 1; i++)
        {
            // 当前情况决策: 当前情况下有nums[i] == 0,其前面的最大值是否跨的过
            if(nums[i] + i > max) max = nums[i] + i;
            if(nums[i] == 0)
                if(max > i) 
                    continue;
                else 
                    return false;
        }
        return true;
    }
};

        max_i 位置很有可能已经完全足够到达最后,所以我们可以增加以一次判断。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_i = 0;
        for(int i = 0; i < nums.size() - 1; i++)
        {
            // 当前情况决策: 当前情况下有nums[i] == 0,其前面的最大值是否跨的过
            if(nums[i] + i > max_i)
                if((max_i = nums[i] + i) >= nums.size() - 1) return true;
            if(nums[i] == 0)
                if(max_i > i) 
                    continue;
                else 
                    return false;
        }
        return true;
    }
};

复杂度分析

  • 时间复杂度:O(n)。
  • 空间复杂度:O(1)。

方法二:贪心(nums[i]为核心)

抽象题中线索:文章来源地址https://www.toymoban.com/news/detail-471461.html

  • 整体策略:不要嵌套nums[i + 1]。
  • 当前情况决策:当前位置 i 前述最大值是否可以到达。
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_i = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            // 当前情况决策: 当前位置 i 前述最大值是否可以到达。
            if(max_i >= i)
            {
                max_i = max(max_i, nums[i] + i);
                // max_i 位置已经完全足够到达最后
                if(max_i >= nums.size() - 1) return true;
            }
            else return false;
        }
        return true;
    }
};

到了这里,关于【算法思维】-- 贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法思维】-- KMP算法

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间(中值5*10e8)。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1)

    2024年02月06日
    浏览(44)
  • 算法思维/优化

    目录 搜索 深度优先搜索 题目来源:小木棍 广度优先搜索 题目来源:棋盘 题目来源:引水入城 双向搜索/折半搜索 题目来源:世界冰球锦标赛 题目来源:Balanced Cow Subsets G A*/迭代加深搜索/IDA* 题目来源:八数码难题 逆序对 题目来源:逆序对[模板] 题目来源:火柴排队 倍增

    2024年02月19日
    浏览(43)
  • 【算法思维】-- 动态规划(C++)

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月02日
    浏览(45)
  • 【算法思维】-- 动态规划

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月05日
    浏览(34)
  • 贪心算法part04 算法

    ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球 https://leetcode.cn/problems/lemonade-change/description/ https://leetcode.cn/problems/queue-reconstruction-by-height/description/ https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

    2024年01月17日
    浏览(38)
  • 算法 - 动态规划 / 贪心算法

    🥂 🌸 121. 买卖股票的最佳时机 [数组] [股票] (动态规划) 🥂 🌸 122. 买卖股票的最佳时机Ⅱ [数组] [股票] (动态规划) 🥂 🌸 123. 买卖股票的最佳时机Ⅲ [数组] [股票] (动态规划) 🥂 🌸 188. 买卖股票的最佳时机Ⅳ [数组] [股票] (动态规划) 🥂 🌸 309. 买卖股票的最佳时机含冷冻

    2024年01月17日
    浏览(37)
  • 【算法】—贪心算法详解

    ①贪心算法的概念 : 贪心算法就是不断选择 在当前看来最好的选择,也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择 虽然贪心算法不能对所有问题都得到整体最优解,但在一些情况下,即使贪心算法 不一定能得到整体最优解 ,其

    2024年02月04日
    浏览(44)
  • 算法-贪心算法

    题目:给定一个字符串str,只由‘X’和‘.’两种字符构成。‘X’表示墙,不能放灯,也不需要点亮‘.’表示居民点,可以放灯,需要点亮如果灯放在i位置,可以让i-1,i和i+1三个位置被点亮返回如果点亮str中所有需要点亮的位置,至少需要几盏灯 思路:递归方式,每个位置

    2024年02月21日
    浏览(36)
  • 贪心算法part03算法

    ● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果 https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ https://leetcode.cn/problems/gas-station/description/ https://leetcode.cn/problems/candy/description/

    2024年01月18日
    浏览(44)
  • 【算法】贪心算法练习一

    个人主页 : zxctscl 如有转载请先通知 一、贪心策略:解决问题的策略,局部最优-全局最优 把解决问题的过程分为若干步; 解决每一步的时候,都选择当前看起来“最优的”解法; 希望得到全局最优。 二、贪心策略的正确性 因为有可能“贪心策略”是一个错误的方法 正确

    2024年04月25日
    浏览(70)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包