当前位置: 首页 > news >正文

c++算法贪心系列

本篇文章,同大家一起学习贪心算法!!!

 第一题

题目链接

2208. 将数组和减半的最少操作次数 - 力扣(LeetCode)

题目解析

本题重点:最终的数组和要小于原数组和的一半,且求这一操作的最少操作数

代码原理

代码编写

class Solution {

public:

    int halveArray(vector<int>& nums) {

        double sum = 0.0;

        priority_queue<double> heap;//将数据存放进大根堆中的优势:最大的数会在堆顶

        for(auto cur: nums)

        {

            heap.push(cur);

            sum += cur;

        }

        sum /= 2.0;

        int count = 0;

        while(sum > 0)

        {

            double t = heap.top() / 2.0;

            heap.pop();

            sum -= t;

            count++;

            heap.push(t);

        }

        return count;

    }

};

贪心策略

选择数组中最大的元素

第二题

题目链接

179. 最大数 - 力扣(LeetCode)

题目解析

代码原理

代码编写

class Solution {

public:

    string largestNumber(vector<int>& nums) {

        vector<string> str;

        for(auto cur: nums)

        {

            str.push_back(to_string(cur));

        }

        sort(str.begin(), str.end(), [](const string& a, const string& b)

        {

            return a + b > b + a;

        });

        string ret;

        for(auto& s: str)

        {

            ret += s;

        }

        if(ret[0] == '0') return "0";

        return ret;

    }

};

贪心策略

先看数字的最高位,与其他数字的最高位进行比较,大的在前小的在后

注意:一切都以每个数的最高位为比较对象

第三题

题目链接

376. 摆动序列 - 力扣(LeetCode)

题目解析

相信大家对这道题已经不再陌生,因为我们上一次做这题的时候是用动态规划的方法去做的题,当然这次博主依旧为给大家简单解析一下这题

注意:这里的加号表示递增,减号表示递减!!!大体可以参考高中时学过的单调性

代码原理

将一个波分成两段分析,因此就有了left和right,left的状态(是上升还是下降)由后面的i+1的元素决定,right的状态则需要i + 1元素和i元素决定。

由于起点无法判断它的状态因此要长度减1,也因此最后的子序列长度要加1

代码编写

class Solution {

public:

    int wiggleMaxLength(vector<int>& nums) {

        int n = nums.size();

        if(n < 2) return n;

        int ret = 0, left = 0;

        for(int i = 0; i < n - 1; i++)

        {

             int right = nums[i + 1] - nums[i];

             if(right == 0) continue;

             if(right * left <= 0) ret++;

             left = right;

        }

        return ret + 1;

    }

};

贪心策略

画图 + 状态走向

那么本篇文章的内容就先到这里,我们下期文章再见!!!!

记得一键三联哦!!!

http://www.lryc.cn/news/525197.html

相关文章:

  • 【Maui】注销用户,采用“手势”点击label弹窗选择
  • 智慧脚下生根,智能井盖监测终端引领城市安全新革命
  • Word2Vec如何优化从中间层到输出层的计算?
  • 第七篇:vue3 计算属性:computed
  • 搭建k8s集群
  • Android SystemUI——最近任务应用列表(十七)
  • java 根据前端传回的png图片数组,后端加水印加密码生成pdf,返回给前端
  • 《探秘鸿蒙Next:如何保障AI模型轻量化后多设备协同功能一致》
  • C语言二级
  • 隐私保护+性能优化,RyTuneX 让你的电脑更快更安全
  • rust学习-宏的定义与使用
  • 【学习总结|DAY032】后端Web实战:登录认证
  • leetcode 123. 买卖股票的最佳时机 III
  • Apache Tika 详解
  • ChatGPT被曝存在爬虫漏洞,OpenAI未公开承认
  • Qt——界面优化
  • python学opencv|读取图像(四十一 )使用cv2.add()函数实现各个像素点BGR叠加
  • Spring MVC和Spring WebFlux的区别
  • Linux探秘坊-------4.进度条小程序
  • Llama 3:开源大模型的里程碑式突破
  • 计算机网络 (56)交互式音频/视频
  • STM32 GPIO工作模式
  • 自动化实现的思路变化
  • MongoDB的索引与聚合
  • Java菜鸟养成计划(java基础)--java运算符
  • 除了基本的事件绑定,鸿蒙的ArkUI
  • 0164__【GNU】gcc -O编译选项 -Og -O0 -O1 -O2 -O3 -Os
  • vue3组件传值具体使用
  • Web 音视频(二)在浏览器中解析视频
  • 江天科技主要产品销售单价下滑,应收账款、存货周转率大幅下降