leetcode–差分数组

leetcode–差分数组0.差分数组的概念:常用于某个区间值都需加/减去a的问题。1.1094拼车classSolution:defcarPooling(self,trips:List[List[int]],capacity:int)->bool:max_val=0foriinrange(len(trips)):max_val=max(max_val,trips[i][2])diff=[0

大家好,又见面了,我是你们的朋友全栈君。

0. 差分数组的概念:

常用于某个区间值都需加/减去a的问题。

1. 1094拼车

在这里插入图片描述

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        max_val = 0
        for i in range(len(trips)):
            max_val = max(max_val, trips[i][2])
        diff = [0]*(max_val+2)
        for i in range(len(trips)):
            diff[trips[i][1]] += trips[i][0]
            diff[trips[i][2]] -= trips[i][0]
        sum_val = 0   
        flag = True 
        for i in range(len(diff)):
            sum_val +=diff[i]
            if sum_val > capacity:
                flag = False
                break 
        return flag

2. 1109航班预定统计

在这里插入图片描述

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0]*(n+2)
        res = [0]*n
        sum_val = 0 
        for i in range(len(bookings)):
            diff[bookings[i][0]] += bookings[i][2]
            diff[bookings[i][1]+1] -= bookings[i][2]
        for i in range(1,n+1):
            sum_val+= diff[i]
            res[i-1] = sum_val
        return res

1674. 使数组互补的最少操作数

在这里插入图片描述

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        diff = [0 for i in range(2*limit +2)]
        n = len(nums)
        for i in range(n//2):
            A = nums[i]
            B = nums[n-1-i]
            l = 2
            r = 2*limit
            diff [l] +=2
            diff[r+1] -=2
            l = 1 + min(A,B)
            r = limit + max(A,B)
            diff [l] -=1
            diff [r+1] +=1
            diff [A+B] -=1
            diff[A+B+1] +=1
        print(diff)    
        res = n    
        sum_val = 0
        for j in range(2,2+limit+1):
            sum_val += diff[j]
            res = min(res, sum_val)
        return res  

121. 买卖股票I

122. 买卖股票II

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133434.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • i386和i686的具体定义

    i386和i686的具体定义转自:http://hi.baidu.com/adongwang/blog/item/a4f89c3e5654ad0bbaa167b2.htmli386和i686    现在所有的intel32位体系(包括AMD等兼容CPU)都叫i386体系,包括P4。、i686仍然属于i386体系,不过对CPU(相对于386)的特性作了指令优化。GNU/Linux分为alpha、PowerP

  • Pytest(2)使用和调用方法

    Pytest(2)使用和调用方法Pytest执行用例规则Pytest在命令行中支持多种方式来运行和选择测试用例1.对某个目录下所有的用例pytest2.对模块中进行测试pytesttest_mod.py3.对文件夹进行

  • 数据库概念结构设计_数据库设计阶段分为

    数据库概念结构设计_数据库设计阶段分为概念结构设计:将需求分析得到的用户需求抽象为信息结构(即概念模型)的过程。一、概念模型在需求分析阶段所得到的应用需求应该首先抽象为信息世界的结构,然后才能更改、更准确地用某一数据库管理系统实现这些需求。概念模型的主要特点:1.能真实、充分地反映现实世界,包括事物和事物之间的联系,能满足用户对数据的处理要求,是现实世界的一个真是模型。2.易于理解,可以用它和不熟悉…

    2022年10月12日
  • gb50174-2017电子信息系统机房设计规范发布时间_机房建设标准规范

    gb50174-2017电子信息系统机房设计规范发布时间_机房建设标准规范机房分级3.1.1电子信息系统机房应划分为A、B、C三级。设计时应根据机房的使用性质、管理要求及其在经济和社会中的重要性确定所属级别。3.1.2符合下列情况之一的电子信息系统机房应为A级1电子信息系统运行中断将造成重大的经济损失;2电子信息系统运行中断将造成公共场所秩序严重混乱。3.1.3符合下列情况之一的电子信息系统机房应为B级。1电子信息系统运行中断将造成较大的经济损…

  • js数组排序的几种方法

    js数组排序的几种方法1、冒泡排序以从小到大排序为例,冒泡排序的原理就是通过两层循环把数组中两两相邻的元素进行比较,是的大的元素放到后边,元素交换位置,从而一步步的交换元素的位置,使得最大的元素放到数组的末尾,这样内部的循环就进行了一轮,再根据外部的循环依次再把次大一点的元素放到数组的末尾,从而实现数组的逐步排序。代码如下://冒泡排序vararr=[52,3,8,57,75,2,1];for(…

  • Python读取excel文件数据并插入数据库[通俗易懂]

    Python读取excel文件数据并插入数据库[通俗易懂]目的:将excel文件StudentInfo.xls的学生信息插入到test库中的student表中一、连接mysql数据库安装第三方库pymysql:pipinstallpymysql调用pymysql.connect()方法连接数据库,代码如下importpymysql#打开数据库连接conn=pymysql.connect(host=’localhost’,#MySQL服务器地址user=’root’,#MySQL服务器端口号p

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号