首页 > 编程语言 >代码随想录算法训练营第34天 | 贪心算法 5:56.合并区间、738.单调递增的数字

代码随想录算法训练营第34天 | 贪心算法 5:56.合并区间、738.单调递增的数字

时间:2024-07-21 15:55:59浏览次数:17  
标签:int res 56 随想录 算法 intervals https 题解

56.合并区间
https://leetcode.cn/problems/merge-intervals/description/
代码随想录
https://programmercarl.com/0056.合并区间.html
738.单调递增的数字
https://leetcode.cn/problems/monotone-increasing-digits/description/
代码随想录
https://programmercarl.com/0738.单调递增的数字.html

56.合并区间

题解思路

  • 和res最后一个比较是否重合;
  • 如果不重合,就增加一个;
  • 如果重合,将前面的范围扩散到最大;

题解代码

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals)==0:
            return []
        intervals.sort(key = lambda x:x[0])
        res = [intervals[0]]
        for i in range(1,len(intervals)):
            if intervals[i][0]>res[-1][1]:##不重合
                res.append(intervals[i])
            else:
                res[-1][1] = max(intervals[i][1],res[-1][1])
        return res

738.单调递增的数字

题解思路

  • 从后向前找不符合要求的数字
  • 找到后标记 将前一个向下减一 后面全部变为9

题解代码

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        if n<10:
            return n

        strnum = str(n)
        flag = len(strnum) ###设定flag是完全不需要改变的

        for i in range(len(strnum)-1,0,-1):##从后往前遍历
            if int(strnum[i])<int(strnum[i-1]):
                flag = i
                strnum = strnum[:i-1]+str(int(strnum[i-1])-1)+strnum[i:]
        strnum_i = strnum[:flag]+"9" * (len(strnum)-flag)
        return int(strnum_i)

标签:int,res,56,随想录,算法,intervals,https,题解
From: https://www.cnblogs.com/P201821440041/p/18314567

相关文章

  • 一文搞懂银行家算法
    在学操作系统的时候,了解到死锁问题,今天在学习并发编程时,也遇到了死锁,在了解了死锁的原因后,遇到一个经典的算法——银行家算法,这是一种避免死锁的算法。在学习完后,我决定总结一下银行家算法的核心思想。什么是死锁?死锁是指在计算机系统中,多个进程或线程因竞争资源或互相等待而......
  • 代码随想录算法训练营第35天 | 动态规划1:509.斐波那契数、70.爬楼梯、746.使用最小花
    代码随想录算法训练营第35天|动态规划理论基础https://programmercarl.com/动态规划理论基础.html#算法公开课509.斐波那契数https://leetcode.cn/problems/fibonacci-number/submissions/548309803/代码随想录https://programmercarl.com/0509.斐波那契数.html#算法公开......
  • 常见的排序算法——堆排序(四)
    本文记述了针对堆排序同时实施减少数据交换和Floyd方法的一份参考实现代码,并在说明了算法的性能后用随机数据进行了验证。◆思想减少数据交换的操作,请参考堆排序(二);Floyd方法,请参考堆排序(三)(此处略去详细说明)。◆实现排序代码采用《算法(第4版)》的“排序算法类模板”实现。(......
  • B3956 [GESP202403 三级] 字母求和 题解
    B3956[GESP202403三级]字母求和题解当时在考试,3分钟A了,结果第二题T了。#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+2;constintN1=1e3+2;typedeflonglongll;typedefunsignedlonglongull;#definefo(i,n,m)for(inti=n;i<=m;i++)......
  • 【软考】数据结构与算法基础 - 数组和链表
    一、数组和链表的区别(很简单,但是很常考,记得要回答全面)什么是数组:C++语言中,可以用数组,处理一组数据类型相同的数据,不可以动态定义数组的大小(使用前,必须指定大小。)在实际应用中,用户使用数组之前,无法确定数组的大小只能够将数组定义成足够大小,多余出来空间可能不被使用,......
  • 常见的排序算法——堆排序(三)
    本文记述了针对堆排序实施Floyd方法的基本思想和一份参考实现代码,并在说明了算法的性能后用随机数据进行了验证。◆思想“大多数在下沉排序期间重新插入堆的元素会被直接加入到堆底。Floyd在1964年观察发现,我们正好可以通过免去检查元素是否到达正确位置来节省时间。”(引......
  • RK3562 NPU开发环境搭建
    如何在Ubuntu系统(PC)上搭建RK3562 Buildroot Linux的NPU开发环境?即电脑端运行Ubuntu系统,而RK3562板卡运行Buildroot Linux系统的情况下,搭建RK3562 NPU开发环境。下面是相应的步骤(对应的命令):1、下载RKNN相关仓库在Ubuntu电脑端执行如下命令:mkdir-p~/bigger_disk/rknpu......
  • 【故障诊断】基于斑马优化算法ZOA优化长短记忆网络LSTM实现故障诊断附matlab代码
    %导入数据集load(‘fault_diagnosis_data.mat’);%假设故障诊断数据保存在fault_diagnosis_data.mat文件中%数据预处理%这里省略了数据预处理的步骤,包括数据归一化、特征提取等%划分训练集和测试集train_ratio=0.8;%训练集占总数据的比例train_size=round......
  • 【独家首发】Matlab实现淘金优化算法GRO优化Transformer-LSTM实现负荷数据回归预测
    %导入数据集load(‘load_data.mat’);%假设负荷数据保存在load_data.mat文件中%数据预处理%这里省略了数据预处理的步骤,包括数据归一化、特征提取等%构建Transformer-LSTM模型model=create_transformer_lstm_model();%自定义创建Transformer-LSTM模型的函数......
  • 【独家首发】Matlab实现狮群优化算法LSO优化Transformer-LSTM实现负荷数据回归预测
    %导入数据集load(‘load_data.mat’);%假设负荷数据保存在load_data.mat文件中%数据预处理%这里省略了数据预处理的步骤,包括数据归一化、特征提取等%构建Transformer-LSTM模型model=create_transformer_lstm_model();%自定义创建Transformer-LSTM模型的函数......