C++ day36 贪心算法 无重叠区间 划分字母区间 合并区间

题目1:435 无重叠区间

题目链接:无重叠区间

对题目的理解

移除数组中的元素,使得区间互不重叠,保证移除的元素数量最少,数组中至少包含一个元素

贪心算法

局部最优,使得重叠区间的个数最大,全局最优,移除最少的元素

本题和昨天引爆气球的题目相似,还是对数组进行排序(按照左边界排序和右边界排序均可),这里还是选择的左边界排序

代码的精华所在

伪代码

完整代码

class Solution {
public:
    static bool cmp(const vector<int>& a, vector<int>& b){
        return a[0]<b[0];//将左边界从小到大排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;
        //首先对数组的起始坐标进行从小到大排序
        sort(intervals.begin(),intervals.end(),cmp);
        int count=0;
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]<intervals[i-1][1]){
                count++;
                //更新当前重叠区间的最小右边界
                intervals[i][1] = min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return count;

    }
};
  • 时间复杂度:O(nlog n) ,有一个快排
  • 空间复杂度:O(n),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间

题目2:763 划分字母区间

题目链接:划分字母区间

对题目的理解

由小写字母构成的字符串划分为尽可能多的片段,每个字母最多再一个片段中出现,比如,字母a在第一个片段中出现了,那么a就不能在之后的片段中出现了,注意划分的结果顺序拼接仍为原字符串,最终返回每个片段的长度

一旦包含了某个字母,就不得不向后遍历,使得该字母只出现在这个区间里,寻找所有的该字母,最终将该片段分割,就是寻找该区间里所有字母的最远边界,这个边界就是分割点。

可以分为如下两步:

  • 统计每一个字符最远出现的位置
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点

伪代码

完整代码

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27]= {0};
        for(int i=0;i<s.size();i++){
            hash[s[i]-'a'] = i;//求解字符串中每个字母出现的最远下标
        }
        int left=0,right = 0;//定义片段的左下标,右下标,计算片段的长度
        vector<int> result;
        for(int i=0;i<s.size();i++){
            right = max(right,hash[s[i]-'a']);//右边界
            if(i==right){
                result.push_back(right-left+1);
                left = i+1;
            }  
        }
        return result;

    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1),使用的hash数组是固定大小

题目3:56 合并区间

题目链接:合并区间

对题目的理解

合并数组中的重叠区间,返回一个不重叠的区间数组,这个数组覆盖输入的所有区间

注意[1,4]和[4,5]也可以合并,合并成[1,5]

本题的本质其实还是判断重叠区间问题

还是先排序,让所有的相邻区间尽可能的重叠在一起,按左边界,或者右边界排序都可以,我还是按照左边界进行排序,然后考虑重叠的区间,更新右边界的最大值,对于不重叠的区间,直接存放到result数组中

伪代码

代码

class Solution {
public:
    static bool cmp(const vector<int>& a, vector<int>& b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> result ;
        result.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]<=result.back()[1]){//重叠
                //左边界不用更新,因为左边界是按照从小到大排的
                //只更新右边界
                result.back()[1] = max(intervals[i][1],result.back()[1]);
                }
            else{//没有重叠
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(logn),排序需要的空间开销

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

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

相关文章

MyBatis Generator使用总结

MyBatis Generator使用总结 介绍具体使用数据准备插件引入配置条件构建讲解demo地址 介绍 MyBatis Generator &#xff08;MBG&#xff09; 是 MyBatis 的代码生成器。它能够根据数据库表&#xff0c;自动生成 java 实体类、dao 层接口&#xff08;mapper 接口&#xff09;及m…

【STM32单片机】自动售货机控制系统设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用STM32F103C8T6单片机控制器&#xff0c;使用OLED显示模块、矩阵按键模块、LED和蜂鸣器、继电器模块等。 主要功能&#xff1a; 系统运行后&#xff0c;OLED显示系统初始界面&#xff0c;可通过…

Java王者荣耀

第一步是创建项目 项目名自拟 第二部创建个包名 来规范class 然后是创建类 GameFrame 运行类 package com.sxt;import java.awt.Graphics; import java.awt.Image; import java.awt.Toolkit; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; im…

网络和Linux网络_5(应用层)HTTP协议(方法+报头+状态码)

目录 1. HTTP协议介绍 1.1 URL介绍 1.2 urlencode和urldecode 1.3 HTTP协议格式 1.4 HTTP的方法和报头和状态码 2. 代码验证HTTP协议格式 HttpServer.hpp 2.2 html正式测试 Util.hpp index.html 2.3 再看HTTP方法和报头和状态码 2.3.1 方法_GET和POST等 2.3.2 报头…

springboot函数式web

1.通常是路由(请求路径)业务 2.函数式web&#xff1a;路由和业务分离 一个configure类 配置bean 路由等 实现业务逻辑 这样实现了业务和路由的分离

代码常见问题

1. 前端页面出现404了&#xff1a; 1&#xff09;那说明你该页面里面有某个接口地址&#xff08;url&#xff09;写错了&#xff0c;后台没有这个接口 2&#xff09;你后台写了这个接口&#xff0c;但是后台忘了重启服务了&#xff0c;这样的话前端也映射不上的 所以404的时…

歌曲《兄弟情深》:歌手荆涛歌曲中的真挚情感

在人生的道路上&#xff0c;有时我们会遇到迷茫、失落、困惑等种种情境。而在这些时刻&#xff0c;身边有一个真挚的兄弟&#xff0c;其意义是无法估量的。歌手荆涛演唱的《兄弟情深》即是对这种深厚情感的美妙歌颂。 一、迷茫时的指引 “当我迷茫时&#xff0c;有你帮目标重新…

箱型图 Box Plot 数据分析的法宝

文章目录 一、箱形图的介绍二、六大因数三、Box plot的应用四、箱形图的优劣势五、图形拓展 一、箱形图的介绍 箱形图又称为盒须图、盒式图、盒状图或箱线图&#xff0c;是一种用作显示一组数据分散情况资料的统计图。因型状如箱子而得名。在各种领域也经常被使用&#xff0c;…

Sqlserver 在数据库‘master’中拒绝了Create Database的权限

解决方案 打开SqlServer Manament Studio软件&#xff0c;然后登陆 选择安全性->登录名->找到您当前的用户 在您的登陆名上&#xff0c;点击右键-属性&#xff0c;配置相应的服务器角色权限&#xff08;这块需要勾选dbcreator的权限&#xff0c;这块如果不清楚还需要啥…

c语言:模拟实现各种字符串函数(2)

strncpy函数&#xff1a; 功能&#xff1a;拷贝指定长度的字符串a到字符串b中 代码模拟实现&#xff1a; //strncpy char* my_strncpy(char* dest, char* str,size_t num) {char* ret dest;assert(dest && str);//断言&#xff0c;如果其中有一个为空指针&#xff…

Linux篇:文件系统

一、共识原理&#xff1a; 文件文件内容文件属性 磁盘上存储文件存文件的内容&#xff08;数据块&#xff09;存文件的属性&#xff08;inode&#xff09; Linux的文件在磁盘中存储是将属性和内容分开存储的。 二、硬件简述&#xff1a; 1. 认识硬件 磁盘&#xff1a;唯一的一…

4.一维数组——用数组处理求Fibonacci数列前20项

文章目录 前言一、题目描述 二、题目分析 三、解题 程序运行代码 四、结果显示 前言 本系列为一维数组编程题&#xff0c;点滴成长&#xff0c;一起逆袭。 一、题目描述 用数组处理求Fibonacci数列前20项 二、题目分析 前两项&#xff1a;f[20]{1,1} 后18项&#xff1a;for(…

vue3+tsx的使用

<template><div><xiaoman on-click"getItem" name"似懂非懂"></xiaoman></div> </template><script setup langts>import xiaoman from "./App"const getItem(item:any)>{console.log(item,it…

王者小游戏作业

一、创建好文件、包、类、插入图片文件夹 二、beast包 1、Bear类 package beast; import sxt.GameFrame; public class Bear extends Beast {public Bear(int x, int y, GameFrame gameFrame) {super(x, y, gameFrame);setImg("C:\\Users\\陆先生\\Desktop\\王者荣耀图片…

C++学习之路(四)C++ 实现简单的待办事项列表命令行应用 - 示例代码拆分讲解

本期示例介绍: 本期示例《待办事项列表应用》展示了一个简单的任务管理系统&#xff0c;用户可以通过命令行界面执行添加任务、删除任务和显示任务列表等操作。 功能描述&#xff1a; 添加任务功能&#xff1a; 用户可以输入任务描述&#xff0c;将新的任务添加到任务列表中。…

设计模式—依赖倒置原则(DIP)

1.概念 依赖倒置原则&#xff08;Dependence Inversion Principle&#xff09;是程序要依赖于抽象接口&#xff0c;不要依赖于具体实现。简单的说就是要求对抽象进行编程&#xff0c;不要对实现进行编程&#xff0c;这样就降低了客户与实现模块间的耦合。 通俗的讲&#xff1…

【教学类-06-13】20231126 (55格版)趣味题(一)1-9加法题(10倍)(整十相加)

作品展示 背景需求&#xff1a; 1、会做加法题的孩子5分钟内完成题目&#xff0c;太快了&#xff0c;所以为了拉平差异&#xff0c;需要给这些会做另外的题目&#xff0c;比如提供一些他们没有做过的“趣味题形”。 2、好多次&#xff0c;听见大班孩子在互相“考试”——“老…

04_MySQL备份与恢复

任务背景 一、真实案例 某天&#xff0c;公司领导安排刚入职不久的小冯同学将生产环境中的数据(MySQL数据库)全部导入到测试环境给测试人员使用。当小冯去拿备份数据时发现&#xff0c;备份数据是1个礼拜之前的。原因是之前运维同事通过脚本每天对数据库进行备份&#xff0c;…

2023年程序设计迎新赛(第二届个人程序设计大赛)

7-1 找规律 请从所给的四个选项中&#xff0c;选择最合适的一个填入问号处&#xff0c;使之呈现一定的规律性。 输入格式: 无 输出格式: 大写字母 输入样例: 输出样例: #include<stdio.h> int main(){printf("D");return 0; }7-2 蜡烛燃烧时间 有粗细不同…

【MySQL】JDBC编程

&#x1f451;专栏内容&#xff1a;MySQL⛪个人主页&#xff1a;子夜的星的主页&#x1f495;座右铭&#xff1a;前路未远&#xff0c;步履不停 目录 一、JDBC工作原理二、JDBC 使用1、准备工作2、使用实例3、手动输入 一、JDBC工作原理 JDBC是Java语言中用于与数据库进行交互…