算法修炼之筑基篇——筑基二层后期(初步理解解决贪心算法)

这篇具有很好参考价值的文章主要介绍了算法修炼之筑基篇——筑基二层后期(初步理解解决贪心算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

博主:命运之光

🦄专栏:算法修炼之练气篇

🍓专栏:算法修炼之筑基篇

博主的其他文章:点击进入博主的主页

前言:学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期难度可谓是天差地别,懂得都懂,题目难度相比起练气期的题目难度提升很多,所以要是各位蒟蒻小伙伴们看不懂筑基期的题目可以在练气期多积累积累,练气期的题目也会不断更新,大家一定要把基础打牢固了再来看筑基期的题目哈,这样子也可以提高大家的学习效率,一举两得,加油(●'◡'●)🎉🎉

算法修炼之筑基篇——筑基二层后期(初步理解解决贪心算法)

 

目录

✨贪心算法到底是什么?怎么使用它?它适合于怎么样的问题?

🍓使用贪心算法时,通常遵循以下步骤:

🍓常见适合使用贪心算法的问题包括:

✨例题:删除字符

🍓题目分析

🍓先让你们看看本✨光写的💩代码

🍓对比一下在网上找到的题解

✨两个代码之间的区别。

✨贪心选择性质和最优子结构性质

✨结语


✨贪心算法到底是什么?怎么使用它?它适合于怎么样的问题?

贪心算法(Greedy Algorithm)是一种常用的算法思想,用于在每个步骤中选择局部最优解,以期望达到全局最优解。它的核心思想是通过贪心选择来构建问题的解,并希望每次选择都是最优的,以达到整体的最优解。

🍓使用贪心算法时,通常遵循以下步骤:

  1. 确定问题的最优子结构:贪心算法的关键在于问题具有最优子结构性质,即一个问题的最优解包含了其子问题的最优解。
  2. 构建贪心选择:对于每个步骤,通过某种策略选择局部最优解,这个选择通常是基于当前可用的信息,并且不考虑子问题的解决方案。
  3. 证明贪心选择性质:需要证明每次贪心选择都是最优的,即通过选择局部最优解最终可以得到全局最优解。
  4. 迭代执行贪心选择:重复执行贪心选择的步骤,直到得到全局最优解或者达到终止条件。

贪心算法适用于一些具有贪心选择性质的问题,这些问题的最优解可以通过一系列局部最优解来达到。通常情况下,贪心算法的效率较高,因为它不需要进行全局搜索,而是通过局部选择来逐步构建解决方案。

注意:并不是所有问题都适合使用贪心算法。贪心算法的局限性在于它没有回溯的能力,无法保证得到全局最优解。对于一些问题,贪心选择可能会导致局部最优解,并不能得到整体的最优解。在使用贪心算法时,需要仔细分析问题的特性,确定问题是否具有贪心选择性质,并且要能够证明贪心选择能够导致最优解。

🍓常见适合使用贪心算法的问题包括:

  • 需要在给定约束条件下寻找最优解的问题,例如零钱找零、背包问题等。
  • 可以通过选择某个局部最优解来构建整体最优解的问题,例如活动选择、区间调度等。
  • 某些问题可以转化为贪心选择的子问题,并且贪心选择是全局最优解的一部分,例如最小生成树问题中的Prim算法和Kruskal算法。

注意:贪心算法并非适用于所有问题的通用解法,对于某些问题,可能需要使用动态规划、回溯、分治等其他算法来求解。因此,在使用贪心算法时,需要充分理解问题的特点和限制,并进行合理的算法选择和设计。

✨例题:删除字符

算法修炼之筑基篇——筑基二层后期(初步理解解决贪心算法)

🍓题目分析

先解释一下题目描述避免一些小伙伴们不理解

给定一个单词,请问在单词中删除 tt 个字母后,能得到的字典序最小的单词是什么?

给定一个单词,题目要求删除其中的 t 个字母后,得到的字典序(按照字母顺序)最小的单词是什么。

具体来说,题目要求在原始单词中删除 t 个字母,使得得到的新单词在字典序上尽可能靠前,也就是说新单词应该是按照字母顺序最小的。

例如,假设给定的单词是 "example",如果要删除 2 个字母,我们可以得到以下可能的新单词:

  • "eample":删除了第一个 "x" 和 "p"。
  • "exmple":删除了第二个 "a" 和 "p"。
  • "exaple":删除了 "m" 和 "p"。
  • "exale":删除了第一个 "m" 和第二个 "p"。

在这些可能的新单词中,"eample" 在字典序上最小,因为 "a" 在字母表中比 "m" 和 "x" 都靠前。因此,答案就是 "eample"。

题目的意思是找到在给定单词中删除 t 个字母后,得到字典序最小的新单词。具体删除哪些字母没有指定,可以自由选择,只需确保得到的新单词在字典序上最小。

🍓先让你们看看本✨光写的💩代码

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    char s[105],s2[105];
    int t;

    cin.getline(s, 105);  // 从标准输入读取一行字符串,并存储到s中
    cin >> t;
    
    int num=0,n=0,m=0;
    int len=strlen(s);
    int len2=strlen(s);
	while(t--)
	{
		if(s[num]<s[n+1])
		{
			s2[0]=s[num];
			n++;
			len--;
		}
		else
		{
			s2[0]=s[n+1];
			num=n+1;
			n++;
			len--;
		}
	}
	int temp=len;
	for(int i=1;i<=len;i++)
	{
		
		s2[temp--]=s[len2--];
	}
	for(int i=0;i<len;i++)
	{
		cout<<s2[i];
	}
    return 0;
}

之前有个错误是在i<len这块,应该是i<len当时写错了写成了i<=len

for(int i=0;i<len;i++)
{
    cout<<s2[i];
}

🍓对比一下在网上找到的题解


#include<iostream>
#include<list>
using namespace std;
int main(){
    int n;
    string str;
    cin>>str>>n;
    
    while(n--){
        for(int i=0;i<str.size();++i){
            if(str[i]>str[i+1]){
                str.erase(i,1);
                break;
            }
        }
    }
    cout<<str<<endl;
    return 0;    
}

🍓其中对str.erase(i,1);的应用很好(这里解释一下)
str.erase(i, 1) 是C++中string类的成员函数,用于从字符串中删除指定位置的字符。它的用法是:

str.erase(pos, count);
  • pos:表示要删除的起始位置,即从字符串的第pos个字符开始删除。
  • count:表示要删除的字符个数。

这样,str.erase(i, 1) 的意思就是从字符串 str 中删除位置为 i 的字符,删除的字符个数为 1。

例如,如果有一个字符串 str = "abcdef",执行 str.erase(2, 1),就会删除字符串中位置为 2 的字符,结果为 "abdef"

需要注意的是,删除字符会导致字符串长度减少,后面的字符会向前移动填补被删除的位置。

在贪心算法中,str.erase(i, 1) 可以用于删除字符串中的某些字符,以满足贪心选择的条件。通常,这是根据特定问题的需求来决定的,你可以根据具体问题的要求在适当的位置使用 str.erase(i, 1) 进行字符删除操作。

✨两个代码之间的区别。

代码一和代码二的主要区别在于字符串的处理方式和字符数组的使用。

代码一使用了 std::string 类型来存储字符串,并利用 std::string 提供的成员函数进行字符串操作,如 erase()size()

代码二使用了字符数组 char s[105] 来存储字符串,并利用字符数组的索引进行字符操作和字符串处理。还使用了 strlen() 函数来获取字符串的长度。

具体区别如下:

代码一:

  • 使用 std::string 类型存储字符串,可以方便地进行字符串操作。
  • 使用 std::string 提供的成员函数 erase()size() 对字符串进行删除和长度获取操作。

代码二:

  • 使用字符数组 char s[105] 存储字符串,需要手动处理字符操作和字符串处理。
  • 使用字符数组时,需要使用 strlen() 函数获取字符串的长度,没有直接的成员函数可用。

在第二段代码中,存在一些问题可能导致运行不正常:

  • len2 在赋值时与 len 的值相同,导致在后续循环中 s[len2--] 会超出数组范围。
  • s2 数组在赋值时只赋值了第一个元素 s2[0],而后续循环中没有正确赋值其他元素。
  • 输出循环中,应该使用 < len,而不是 <= len,否则会输出多余的字符。

🎉🎉做完这道题大家一定对贪心算法有了深刻的想法。就是找到局部最优解,理解题意,然后写出算法,没什么特别的地方。

有一些问题需要注意:

  1. 贪心算法的局部最优解不一定能够导致全局最优解。在某些情况下,贪心策略可能会导致次优解或无法得到正确答案。因此,在应用贪心算法时,需要确保所选取的局部最优解确实能够推导出全局最优解。
  2. 贪心算法的适用性有限。贪心算法通常适用于满足贪心选择性质和最优子结构性质的问题。贪心选择性质是指通过选择局部最优解可以得到全局最优解,最优子结构性质是指问题的最优解包含子问题的最优解。对于一些问题,贪心算法可能不适用或者需要进一步优化。

✨✨综上所述,贪心算法是一种简单而强大的解决问题的策略,但在应用时需要确保问题满足贪心选择性质和最优子结构性质,并且需要仔细分析问题的特点,选择合适的贪心策略。

✨贪心选择性质和最优子结构性质

当应用贪心算法解决问题时,有两个重要的概念需要考虑:贪心选择性质和最优子结构性质。

  1. 贪心选择性质(Greedy Choice Property): 贪心选择性质是指在每一步选择中,选择当前看起来最优的解决方案。也就是说,贪心算法做出的每个局部决策都应该是当前状态下最好的选择,而不考虑未来步骤的影响。这样,通过一系列局部最优解,希望能够得到全局最优解。
  2. 最优子结构性质(Optimal Substructure Property): 最优子结构性质是指问题的最优解包含子问题的最优解。也就是说,问题的整体最优解可以通过子问题的最优解推导得出。这种性质允许我们通过解决子问题来构建问题的最优解,从而简化问题的求解过程。

对于一个问题适用贪心算法,需要满足以下两个条件:

  1. 贪心选择性质:每一步选择都是局部最优的选择,可以得到全局最优解。
  2. 最优子结构性质:问题的最优解包含子问题的最优解,可以通过解决子问题来构建问题的最优解。

在应用贪心算法时,需要仔细分析问题的特点和约束条件,并选择合适的贪心策略。这意味着需要理解问题的本质,识别出问题中哪些部分具有贪心选择性质和最优子结构性质,以便设计相应的贪心策略。

选择合适的贪心策略可能需要考虑问题的特征、约束条件、目标函数以及可能的局部最优解如何导致全局最优解。有时候可能需要尝试不同的贪心策略或结合其他算法技巧来解决问题。

✨结语

总结来说,贪心算法要求问题具有贪心选择性质和最优子结构性质,并需要仔细分析问题的特点和约束条件,选择合适的贪心策略。这样才能确保贪心算法能够正确解决问题并得到全局最优解。文章来源地址https://www.toymoban.com/news/detail-514039.html

到了这里,关于算法修炼之筑基篇——筑基二层后期(初步理解解决贪心算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【蓝桥杯-筑基篇】动态规划

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 1.最大连续子段和 2.LCS 最大公共子序列 3.LIS 最长上升子序列 4.数塔 5.最大子矩阵和 6.背包问题 ①01背包问题 ②完全背包 这段代码是一个求最大子数组和的算法,使用的是动态规划的思想。下面是代码的解释: 首先定义了一个

    2023年04月24日
    浏览(73)
  • 【蓝桥杯-筑基篇】贪心

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 1.找零问题 ①暴力枚举 ②贪心 2.人性总是贪婪的 3.堆果子 4.图书推荐 有币种 1 、 2 、 4 、 5 、 10 若干张,找零 n 元,输出找零方案。 ①暴力枚举 这是一个找零问题,我们需要找到一种方案,使得用给定的硬币找零时,所需的

    2024年01月18日
    浏览(40)
  • 【蓝桥杯-筑基篇】搜索

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 递归树 1.递归构建二进制串  2.全排列的 DFS 解法 3.全排列的 BFS 解法 4.数的划分法 5.图书推荐 递归树 递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化,从而更好地理解算法的时间复杂度

    2024年01月16日
    浏览(78)
  • MySQL筑基篇之增删改查

    ✅作者简介:C/C++领域新星创作者,为C++和java奋斗中 ✨个人社区:微凉秋意社区 🔥系列专栏:MySql一点通 📃推荐一款模拟面试、刷题神器👉注册免费刷题 🔥前言 本文将承接前两篇MySQL专栏的博文,讲解数据库的 增删改查 操作,这里的查询确切的说应该是初级的查询,不

    2024年02月12日
    浏览(57)
  • 百日筑基篇——python爬虫学习(一)

    百日筑基篇——python爬虫学习(一) 随着学习的深入,有关从各种不同的数据库中以及互联网上的海量信息,如何有选择性的爬取我们所需的数据以方便我们的数据分析工作,爬虫的学习是必要的。 Python爬虫是指使用Python编程语言编写的程序,通过模拟浏览器行为从网页中

    2024年02月13日
    浏览(52)
  • C++修炼之筑基期第三层——拷贝构造函数

    🌸作者简介: 花想云 ,在读本科生一枚,致力于 C/C++、Linux 学习。 🌸 本文收录于 C++系列 ,本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等,专为大学生打造全套 C++ 学习教程,持续更新! 🌸 相关专栏推荐: C语言初阶系列 、 C语言进阶系列 、 数据结构与算法 本章主要

    2023年04月09日
    浏览(64)
  • C++修炼之筑基期第一层——认识类与对象

    🌸作者简介: 花想云 ,在读本科生一枚,致力于 C/C++、Linux 学习。 🌸 本文收录于 C++系列,本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等,专为大学生打造全套 C++ 学习教程,持续更新! 🌸 相关专栏推荐: C语言初阶系列 、 C语言进阶系列 、 数据结构与算法 本章内容

    2023年04月08日
    浏览(41)
  • C++修炼之筑基期第四层 ——透过日期类看运算符重载 | 赋值运算符重载 | 取地址操作符重载

    🌸作者简介: 花想云 ,在读本科生一枚,致力于 C/C++、Linux 学习。 🌸 本文收录于 C++系列 ,本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等,专为大学生打造全套 C++ 学习教程,持续更新! 🌸 相关专栏推荐: C语言初阶系列 、 C语言进阶系列 、 数据结构与算法 本章主要

    2023年04月09日
    浏览(82)
  • Exgcd(拓展欧几里得算法)的初步理解

    若a,b是整数,且 gcd(a,b)=d ,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。它的一个重要推论是:a,b互质的充分必要条件是存在整数x,y使ax+by=1. 针对于一次不定方程 ax+by=c 进行求解,利用以上的裴蜀定理可以进行求解,当然要满足 gcd(a,b)|

    2024年02月16日
    浏览(34)
  • 音频筑基:算法时延分析

    音频算法中,经常遇到时延分析的问题,刚开始接触大多都比较迷惑,这里将自己对时延的学习思考梳理总结于此。 音频领域中,时延(delay/latency)主要指声音从源端发出,经链路传输,再到对端接收到声音,所经过的总时间延迟。一般人耳无法感知的蓝牙段链路时延是25-30

    2024年01月17日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包