leetcode贪心算法题总结(一)

此系列分三章来记录leetcode的有关贪心算法题解,题目我都会给出具体实现代码,如果看不懂的可以后台私信我。

本章目录

  • 1.柠檬水找零
  • 2.将数组和减半的最少操作次数
  • 3.最大数
  • 4.摆动序列
  • 5.最长递增子序列
  • 6.递增的三元子序列
  • 7.最长连续递增序列
  • 8.买卖股票的最佳时机
  • 9.买卖股票的最佳时机II
  • 10.K次取反后最大化的数组和
  • 11.按身高排序
  • 12.优势洗牌

1.柠檬水找零

柠檬水找零
在这里插入图片描述

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0,ten = 0;
        for(auto x:bills)
        {
            if(x==5) five++;
            else if(x==10)
            {
                if(five == 0) return false;
                five--;ten++;
            }
            else
            {
                if(ten&&five) //贪心
                {
                    ten--;five--;
                }
                else if(five>=3)
                {
                    five -= 3;
                }
                else return false;
            }
        }
        return true;
    }
};

2.将数组和减半的最少操作次数

将数组和减半的最少操作次数
在这里插入图片描述

class Solution {
public:
    int halveArray(vector<int>& nums) {
        //贪心+大根堆
        priority_queue<double> heap;
        double sum = 0.0;
        for(auto x:nums)
        {
            sum += x;
            heap.push(x);
        }

        sum /= 2.0;
        int count =0;
        while(sum>0)
        {
            auto t = heap.top()/2.0;
            heap.pop();
            sum -= t;
            count++;
            heap.push(t);
        }
        return count;
    }
};

3.最大数

最大数
在这里插入图片描述

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        //优化:将整型都转成字符串,通过比较字符串的字典序来比大小
        vector<string> strs;
        for(auto x:nums) strs.push_back(to_string(x));
        sort(strs.begin(),strs.end(),[&](const string& s1,const string& s2)
        {
            return s1+s2>s2+s1;
        });

        string ret;
        for(auto& s: strs) ret+=s;
        //处理前导零
        if(ret[0]=='0') return "0";
        return ret;
    }
};

4.摆动序列

摆动序列
在这里插入图片描述

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        //贪心:找极值点,建议大家将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(left*right<=0) ret++; //两边异号
            left = right;
        }
        return ret+1;//最后一个点必要
    }
};

5.最长递增子序列

最长递增子序列
在这里插入图片描述

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //自己设计一个数组,此数组的每个元素表示存储长度为x的子序列的最后一个元素的最小值
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for(int i=1;i<n;i++)
        {
            if(nums[i]>ret.back())
            {
                ret.push_back(nums[i]);
            }
            else
            {
                int left = 0,right = ret.size()-1;
                while(left<right)
                {
                    int mid = (left+right)>>1;
                    if(ret[mid]<nums[i]) left = mid+1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }
        return ret.size();
    }
};

6.递增的三元子序列

递增的三元子序列
在这里插入图片描述

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int a = nums[0],b = INT_MAX;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]>b) return true;
            if(nums[i]>a) b = nums[i];
            else a = nums[i];
        }
        return false;
    }
};

7.最长连续递增序列

最长连续递增序列
在这里插入图片描述

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        //贪心+双指针
        int ret = 0,n = nums.size();
        for(int i=0;i<n;)
        {
            int j = i+1;
            while(j<n&& nums[j]>nums[j-1]) j++;
            ret = max(ret,j-i);
            i = j;//直接在循环中更新下一个起点的位置,体现了贪心
        }
        return ret;
    }
};

8.买卖股票的最佳时机

买卖股票的最佳时机
在这里插入图片描述

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0,minElem = INT_MAX;
        int n = prices.size();
        for(int i=0;i<n;i++)
        {
            ret = max(ret,prices[i]-minElem);//先更新结果
            minElem = min(minElem,prices[i]);//再更新最小值
        }
        return ret;
    }
};


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

买卖股票的最佳时机II述
在这里插入图片描述

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //法一:双指针
        int ret = 0,n = prices.size();
        for(int i=0;i<n;i++)
        {
            int j = i;
            while(j+1<n && prices[j+1]>prices[j]) j++;
            ret += prices[j]-prices[i];
            i = j;
        }
        return ret;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //法二:一天一天进行计算
        int ret = 0,n = prices.size();
        for(int i=1;i<n;i++)
        {
            if(prices[i]-prices[i-1]>0) ret += (prices[i]-prices[i-1]);
        }
        return ret;
    }
};

10.K次取反后最大化的数组和

K次取反后最大化的数组和
在这里插入图片描述

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int m = 0,minElem = INT_MAX,n = nums.size();
        for(auto x:nums)
        {
            if(x<0) m++;
            minElem = min(minElem,abs(x));
        }
        int ret = 0;
        if(m>k)
        {
            sort(nums.begin(),nums.end());
            for(int i=0;i<k;i++)
            {
                ret += -nums[i];
            }
            for(int i=k;i<n;i++)
            {
                ret += nums[i];
            }
        }
        else
        {
            for(auto x:nums)
            {
                ret += abs(x);
            }
            if((k-m)%2!=0)
            {
                ret -= minElem*2;
            }
        }
        return ret;
    }
};

11.按身高排序

按身高排序
在这里插入图片描述

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        //1.创建一个下标数组
        int n = names.size();
        vector<int> index(n);
        for(int i=0;i<n;i++) index[i] = i;
        //2.对下标数组进行排序
        sort(index.begin(),index.end(),[&](int i,int j)
        {
            return heights[i]>heights[j];
        });
        //3.输出结果
        vector<string> ret;
        for(auto x:index)
        {
            ret.push_back(names[x]);
        }
        return ret;
    }
};

12.优势洗牌

优势洗牌
在这里插入图片描述

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        //此题可以学习对应的策略,积累经验
        int n = nums1.size();
        //1.排序
        sort(nums1.begin(),nums1.end());
        vector<int> index2(n);
        for(int i=0;i<n;i++) index2[i] = i;
        sort(index2.begin(),index2.end(),[&](int i,int j)
        {
            return nums2[i]<nums2[j];
        });
        //2.田忌赛马
        int left = 0,right = n-1;
        vector<int> ret(n);
        for(int i=0;i<n;i++)
        {
            if(nums1[i]>nums2[index2[left]]) ret[index2[left++]] = nums1[i];
            else ret[index2[right--]] = nums1[i];
        }
        return ret;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/274479.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

设计模式-过滤器模式

设计模式专栏 模式介绍模式特点应用场景Java中的过滤器介绍代码示例Java实现过滤器模式Python实现过滤器模式 过滤器模式在spring中的应用 模式介绍 过滤器模式是一种设计模式&#xff0c;它允许开发人员使用不同的标准来过滤一组对象。这种模式是通过运算逻辑以解耦的方式将它…

XIAO ESP32S3之物体检测加入视频流

一、前言 由于XIAO ESP32S3开发套件没有显示屏配件&#xff0c;因此加入http视频流功能&#xff0c;可通过浏览器请求ESP32S3上的视频流。 二、思路 1、XIAO ESP32S3启动后通过wifi连接到AP&#xff1b; 2、启动http服务器&#xff0c;注册get_mjpeg处理函数&#xff1b; 3…

2023年中职“网络安全”——B-5:网络安全事件响应(Server2216)

B-5&#xff1a;网络安全事件响应 任务环境说明&#xff1a; 服务器场景&#xff1a;Server2216&#xff08;开放链接&#xff09; 用户名:root密码&#xff1a;123456 1、黑客通过网络攻入本地服务器&#xff0c;通过特殊手段在系统中建立了多个异常进程&#xff0c;找出启…

【Pytorch】学习记录分享8——PyTorch自然语言处理基础-词向量模型Word2Vec

【Pytorch】学习记录分享7——PyTorch自然语言处理基础-词向量模型Word2Vec 1. 词向量模型Word2Vec)1. 如何度量这个单词的&#xff1f;2.词向量是什么样子&#xff1f;3.词向量对应的热力图&#xff1a;4.词向量模型的输入与输出![在这里插入图片描述](https://img-blog.csdni…

Java面试题及答案汇总来啦!快来领取

Java面试题及答案汇总来啦&#xff01;快来领取 还有不到两个月就要过年了&#xff0c;过完年紧接着“金三银四”招聘热季就要到了&#xff0c;在过年期间只想着吃吃喝喝玩玩&#xff0c;这习是学不了一点。那就趁着过年前这段时间开始恶补Java面试题&#xff0c;实现弯道超车吧…

ArkTS基本概念装饰器

目录 ArkTS基本概念 装饰器汇总 ArkTS基本概念 ArkTS是HarmonyOS的主力应用开发语言。 它在TypeScript&#xff08;简称TS&#xff09;的基础上&#xff0c;匹配ArkUI框架&#xff0c;扩展了声明式UI、状态管理等相应的能力&#xff0c;让开发者以更简洁、更自然的方式开发跨…

FTP简介FTP服务器的搭建【虚拟机版】以及计算机端口的介绍

目录 一. FTP简介 二. FTP服务器的搭建【虚拟机Windows2012版】 1. 启用防火墙 2. 打开服务器管理器➡工具➡计算机管理 3. 选择本地用户与组➡新建组 4. 给组命名&#xff0c;输入描述&#xff0c;点击创建 5. 新建用户&#xff0c;设置用户名称&#xff0c;添加描述&a…

立体匹配算法(Stereo correspondence)SGM

SGM(Semi-Global Matching)原理&#xff1a; SGM的原理在wiki百科和matlab官网上有比较详细的解释&#xff1a; wiki matlab 如果想完全了解原理还是建议看原论文 paper&#xff08;我就不看了&#xff0c;懒癌犯了。&#xff09; 优质论文解读和代码实现 一位大神自己用c实现…

IntelliJ IDEA [插件 MybatisX] mapper和xml间跳转

文章目录 1. 安装插件2. 如何使用3. 主要功能总结 MybatisX 是一款为 IntelliJ IDEA 提供支持的 MyBatis 开发插件 它通过提供丰富的功能集&#xff0c;大大简化了 MyBatis XML 文件的编写、映射关系的可视化查看以及 SQL 语句的调试等操作。本文将介绍如何安装、配置和使用 In…

redis 三主六从高可用docker(不固定ip)

redis集群(cluster)笔记 redis 三主三从高可用集群docker swarm redis 三主六从高可用docker(不固定ip) 此博客解决&#xff0c;redis加入集群后&#xff0c;是用于停掉后重启&#xff0c;将nodes.conf中的旧的Ip替换为新的IP&#xff0c;从而达到不会因为IP变化导致集群无法…

StackOverflowError的JVM处理方式

背景&#xff1a; 事情来源于生产的一个异常日志 Caused by: java.lang.StackOverflowError: null at java.util.stream.Collectors.lambda$groupingBy$45(Collectors.java:908) at java.util.stream.ReduceOps$3ReducingSink.accept(ReduceOps.java:169) at java.util.ArrayL…

阿里云 ACK 云上大规模 Kubernetes 集群高可靠性保障实战

作者&#xff1a;贤维 马建波 古九 五花 刘佳旭 引言 2023 年 7 月&#xff0c;阿里云容器服务 ACK 成为首批通过中国信通院“云服务稳定运行能力-容器集群稳定性”评估的产品&#xff0c; 并荣获“先进级”认证。随着 ACK 在生产环境中的采用率越来越高&#xff0c;稳定性保…

【ES6】Class继承-super关键字

目录 一、前言二、ES6与ES5继承机制区别三、super作为函数1、构造函数this1&#xff09;、首先要明确this指向①、普通函数②、箭头函数③、注意事项 2&#xff09;、其次要明确new操作符做了哪些事情 2、super()的用法及注意点1&#xff09;、用法2&#xff09;、注意点 四、s…

Unity引擎有哪些优点

Unity引擎是一款跨平台的游戏引擎&#xff0c;拥有很多的优点&#xff0c;如跨平台支持、强大的工具和编辑器、灵活的脚本支持、丰富的资源库和强大的社区生态系统等&#xff0c;让他成为众多开发者选择的游戏开发引擎。下面我简单的介绍一下Unity引擎的优点。 跨平台支持 跨…

用Xshell连接虚拟机的Ubuntu20.04系统记录。虚拟机Ubuntu无法上网。本机能ping通虚拟机,反之不能。互ping不通

先别急着操作&#xff0c;看完再试。 如果是&#xff1a;本机能ping通虚拟机&#xff0c;反之不能。慢慢看到第8条。 如果是&#xff1a;虚拟机不能上网&#xff08;互ping不通&#xff09;&#xff0c;往下一直看。 系统是刚装的&#xff0c;安装步骤&#xff1a;VMware虚拟机…

TCP 滑动窗口

滑动窗口&#xff08;Sliding window&#xff09;是一种流量控制技术。早期的网络通信中&#xff0c;通信双方不会考虑网络的拥挤情况直接发送数据。由于大家不知道网络拥塞状况&#xff0c;同时发送数据&#xff0c;导致中间节点阻塞掉包&#xff0c;谁也发不了数据&#xff0…

数据分析工具 Top 8

你能想象一个没有工具箱的水管工吗? 没有,对吧? 数据从业者也是如此。如果没有他们的数据分析工具&#xff0c;数据从业者就无法分析数据、可视化数据、从数据中提取价值&#xff0c;也无法做数据从业者在日常工作中做的许多很酷的事情。 根据你最感兴趣的数据科学职业——数…

VR与数字孪生:共同构筑未来的虚拟世界

随着科技的不断发展&#xff0c;数字孪生和VR已经成为当今热门的科技话题。作为山海鲸可视化软件的开发者&#xff0c;我们对这两者都有深入的了解。在此&#xff0c;我们将详细探讨数字孪生与VR的区别和联系。 首先&#xff0c;数字孪生&#xff08;Digital Twin&#xff09;…

深度学习 | DRNN、BRNN、LSTM、GRU

1、深度循环神经网络 1.1、基本思想 能捕捉数据中更复杂模式并更好地处理长期依赖关系。 深度分层模型比浅层模型更有效率。 Deep RNN比传统RNN表征能力更强。 那么该如何引入深层结构呢&#xff1f; 传统的RNN在每个时间步的迭代都可以分为三个部分&#xff1a; 1.2、三种深层…

pymol--常用指令

1. 导入蛋白质 1&#xff09;Pymol> load name.pdb, name # 载入pdb文件&#xff0c;并命名&#xff0c;我还没试过 Pymol> fetch proteinID # 直接就加载了 我用的这个 右边选框&#xff0c;有A S H L C指令 2. 保存图片 2.1 直接输出PNG&#xff0c;在pymol后输…