[C++] : 贪心算法专题(第一部分)
2023-12-30 14:48:03
1.柠檬水找零:
1.思路一:
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int file=0;
int ten =0;
for(auto num:bills)
{
if(num == 5) file++;
else if(num == 10)
{
if(file > 0)
file--,ten++;
else
return false;
}
else
{
if(ten>=1 && file>=1)
ten--,file--;
else if(file>=3)
file-=3;
else
return false;
}
}
return true;
}
};
GIF题目解析
2. 将数组和减半的最小操作数:
1.思路一:
class Solution {
public:
int halveArray(vector<int>& nums) {
//1.求和:
long long sum = 0;
for (auto num : nums)
{
sum += num;
}
//2.计算一半的值:
long double half = ((long double)sum) / 2;
//3.记录操作数:
int count = 0;
priority_queue<double> qu(nums.begin(), nums.end());
while (half>0)//等于或者小于都不满足循环条件
{
double tmp = qu.top();//获取堆顶数据
qu.pop();//pop堆顶数据
tmp /= 2;
half -= tmp;
count++;
qu.push(tmp);
}
return count;
}
};
GIF题目解析
3.最大数:
1.思路一:
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> strs;
for(int num:nums)
{
strs.push_back(to_string(num));
}
sort(strs.begin(),strs.end(),
[](const string s1 , const string s2)
{
return s1+s2 > s2+s1;
}
);
string ret;
for(auto str:strs)
{
ret+=str;
}
//下标访问字符串返回的是char&可读可写类型的数据!
if(ret[0]=='0') return "0";
return ret;
}
};
GIF题目解析
4.摆动序列:
1.思路一:
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int ret = 0;
int left = 0;
int right = 0;
for(int i = 0 ; i < nums.size() - 1 ; i++)
{
right = nums[i+1] - nums[i];
if(right == 0) continue;
if(left*right <= 0) ret++;
left = right;
}
//第一个点是没有加入进来的!
return ret+1;
}
};
GIF题目解析
5.最长递增子序列
1.思路一:dp方法
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n,1);
//1.开始遍历:
int ret = 0;
for(int i=1 ; i<n;i++)
{
//1.计算从0到i-1的递增子序列
for(int j=0;j<i;j++)
{
if(nums[j] < nums[i])
{
//1.注意:
dp[i] = max(dp[j]+1 , dp[i]);
}
}
ret = max(dp[i] , ret);
}
return ret;
}
};
GIF题目解析
2.思路二:在dp基础上进行的贪心优化:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//1.创建dp数组保存当前遍历到的位置的递增字序列元素
vector<int> dp;
//1-1:第一个数一定开始就在dp里面了!
dp.push_back(nums[0]);
int n = nums.size();
//2.遍历顺序表:
for(int cur=1 ; cur<n ; cur++)
{
//1.比最后一个数都大直接push_back()
if(nums[cur] > dp.back())
{
dp.push_back(nums[cur]);
}
//2.二分寻找!
else
{
int left = 0 , right = dp.size()-1;
while(left < right)
{
int mid = left + (right - left)/2;
if(dp[mid] < nums[cur]) left = mid + 1;
else right = mid;
}
//3.找到数据更新!
dp[left] = nums[cur];
}
}
return dp.size();
}
};
GIF题目解析
6.递增的三元子序列
1.思路一:
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int one = nums[0];
int two = INT_MAX;
for(int cur = 1 ; cur < nums.size() ; cur++)
{
if(nums[cur] > two) return true;
else if(nums[cur] < two)
{
if(nums[cur] <= one) one = nums[cur];
else two = nums[cur];
}
}
return false;
}
};
GIF题目解析
7.最长连续递增序列
1.思路一:
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int i=0;
int ret = 0;
while(i < nums.size())
{
int j = 0;
for(j = i;j<nums.size()-1;j++)
{
if(nums[j] >= nums[j+1]) break;
}
ret = max(ret , j-i+1);
//贪心思路j的位置在连续递增子序列的最后一个位置!
i = j+1;
}
return ret;
}
};
GIF题目解析:
文章来源:https://blog.csdn.net/2201_75943325/article/details/135093359
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!