✨博主:命运之光 🦄专栏:算法修炼之练气篇 🍓专栏:算法修炼之筑基篇 ✨博主的其他文章:点击进入博主的主页 前言:学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期难度可谓是天差地别,懂得都懂,题目难度相比起练气期的题目难度提升很多,所以要是各位蒟蒻小伙伴们看不懂筑基期的题目可以在练气期多积累积累,练气期的题目也会不断更新,大家一定要把基础打牢固了再来看筑基期的题目哈,这样子也可以提高大家的学习效率,一举两得,加油(●'◡'●)🎉🎉
贪心算法(Greedy Algorithm)是一种常用的算法思想,用于在每个步骤中选择局部最优解,以期望达到全局最优解。它的核心思想是通过贪心选择来构建问题的解,并希望每次选择都是最优的,以达到整体的最优解。
贪心算法适用于一些具有贪心选择性质的问题,这些问题的最优解可以通过一系列局部最优解来达到。通常情况下,贪心算法的效率较高,因为它不需要进行全局搜索,而是通过局部选择来逐步构建解决方案。
注意:并不是所有问题都适合使用贪心算法。贪心算法的局限性在于它没有回溯的能力,无法保证得到全局最优解。对于一些问题,贪心选择可能会导致局部最优解,并不能得到整体的最优解。在使用贪心算法时,需要仔细分析问题的特性,确定问题是否具有贪心选择性质,并且要能够证明贪心选择能够导致最优解。
注意:贪心算法并非适用于所有问题的通用解法,对于某些问题,可能需要使用动态规划、回溯、分治等其他算法来求解。因此,在使用贪心算法时,需要充分理解问题的特点和限制,并进行合理的算法选择和设计。
先解释一下题目描述避免一些小伙伴们不理解
给定一个单词,请问在单词中删除 tt 个字母后,能得到的字典序最小的单词是什么?
给定一个单词,题目要求删除其中的 t 个字母后,得到的字典序(按照字母顺序)最小的单词是什么。
具体来说,题目要求在原始单词中删除 t 个字母,使得得到的新单词在字典序上尽可能靠前,也就是说新单词应该是按照字母顺序最小的。
例如,假设给定的单词是 "example",如果要删除 2 个字母,我们可以得到以下可能的新单词:
在这些可能的新单词中,"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);
这样,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
,否则会输出多余的字符。🎉🎉做完这道题大家一定对贪心算法有了深刻的想法。就是找到局部最优解,理解题意,然后写出算法,没什么特别的地方。
有一些问题需要注意:
✨✨综上所述,贪心算法是一种简单而强大的解决问题的策略,但在应用时需要确保问题满足贪心选择性质和最优子结构性质,并且需要仔细分析问题的特点,选择合适的贪心策略。
当应用贪心算法解决问题时,有两个重要的概念需要考虑:贪心选择性质和最优子结构性质。
对于一个问题适用贪心算法,需要满足以下两个条件:
在应用贪心算法时,需要仔细分析问题的特点和约束条件,并选择合适的贪心策略。这意味着需要理解问题的本质,识别出问题中哪些部分具有贪心选择性质和最优子结构性质,以便设计相应的贪心策略。
选择合适的贪心策略可能需要考虑问题的特征、约束条件、目标函数以及可能的局部最优解如何导致全局最优解。有时候可能需要尝试不同的贪心策略或结合其他算法技巧来解决问题。
总结来说,贪心算法要求问题具有贪心选择性质和最优子结构性质,并需要仔细分析问题的特点和约束条件,选择合适的贪心策略。这样才能确保贪心算法能够正确解决问题并得到全局最优解。