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

学python的第二天---差分

  • 一、改变数组元素(差分)
    • 方法一:差分数组
      • map(int,input().split())
      • for b in arr[:n]:
      • print(1 if b else 0,end=' ')
    • 方法二:区间合并
      • interval.sort(key=lambda x:x[0])
  • 二、差分
      • a = [0] + list(map(int, input().split())) + a[n + 1:]
  • 三、差分矩阵
    • 写法一:
    • 写法二:
      • print(" ".join(map(str,dt[i][1:m+1])))
  • 四、增减序列
      • print(f"{max(pos, neg)}\n{abs(pos - neg) + 1}")

一、改变数组元素(差分)

在这里插入图片描述

方法一:差分数组

map(int,input().split())

这个返回的是一个对象,而不是一个整数

for b in arr[:n]:

arr[:n] 是 Python 中的一个切片操作,表示从列表 arr 的开头(索引0)到第 n-1 个元素的子列表。

print(1 if b else 0,end=’ ')

这段代码的作用是将布尔值 b 转换成整数并打印出来。如果 b 为 True,则打印 1,否则打印 0。代码中的 end=’ ’ 表示在打印结果后不换行,而是以空格结尾。

#只用关心某个数字位置是否被覆盖过,不关心覆盖过几次
for i in range(int(input())):#读入输入数组的次数n,a=int(input()),list(map(int,input().split()))#前面是传入一个数,后面传的一个数组arr=[0]*(n+5)#数组的大小for j in range(n):arr[max(0,j-a[j]+1)]+=1arr[j+1]-=1for j in range(1,n):arr[j]+=arr[j-1]#差分数组for b in arr[:n]:print(1 if b else 0,end=' ')#这个用法好绝,对于初学者来说print()#换行

方法二:区间合并

这段代码是一个处理区间问题的算法,主要实现以下步骤:

1.读入一个整数 n 和长度为 n 的整数列表 a。

2.对于列表 a 中的每个元素 a[j],如果它不为零,则将区间 [max(0, j-a[j]+1), j] 添加到 interval 列表中。

3.对 interval 列表按照区间的左端点进行排序。

4.对于排好序的 interval 列表中的每个区间,将该区间内的所有元素在 arr 列表中标记为 1。

5.输出标记好的 arr 列表。

可以看到,该算法的时间复杂度为 O(nlogn),其中最耗时的操作是对区间列表进行排序。

interval.sort(key=lambda x:x[0])

这段代码是按照左端点进行排序,如果要按照右端点进行排序

interval.sort(key=lambda x: x[1])

for i in range(int(input())):#input()返回为str,转换为intn,a=int(input()),list(map(int,input().split()))#输入数组大小及数组元素arr,interval=[0]*n,[]for j in range(n):if a[j]:interval.append([max(0,j-a[j]+1),j])#记录区间interval.sort(key=lambda x:x[0])#按照区间端点进行排序if interval:#检查interval是否为空,若为空则直接输出长度为n的全0数组,# 如果不为空,则按照一定的规则将1填充到arr数组中p=1#编号为0的区间for j in range(1,len(interval)):if interval[j][0]>interval[p-1][1]+1:#如果区间左端点大于编号为p-1的一个区间右端点+1,则说明这是两个区间interval[p]=interval[j]p+=1else:#如果在内部,则可以这两个区间interval[p-1][1]=max(interval[p-1][1],interval[j][1])for j in range(p):#枚举每个区间,将每个区间内所包含的置1for k in range(interval[j][0],interval[j][1]+1):arr[k]=1for a in arr:print(a,end=' ')print()

注意缩进!!!

二、差分

在这里插入图片描述

a = [0] + list(map(int, input().split())) + a[n + 1:]

这行代码的作用是将列表a中从下标1到n(包括1和n)的元素替换为输入的元素,并在列表的开头和结尾添加了一个0,保证了后面的操作不会出现索引错误。具体地:

a[:n+1]表示从下标0到n的元素,其中a[0]为列表的第一个元素,a[n]为列表的最后一个元素,a[n+1:]表示从下标n+1到列表结尾的所有元素。

因此,a = [0] + list(map(int, input().split())) + a[n +1:]的作用就是先将0添加到列表的开头,然后将输入的元素添加到原来的位置上,最后再将原来的n+1到结尾的所有元素添加到列表的尾部,从而得到了一个长度为n+2的新列表a。

n,q=map(int,input().split())
a=[0]*(n+10)
b=[0]*(n+10)#a的0位是0,第1位到第n位是输入的数,第n+1位起往后都是0
a=[0]+list(map(int,input().split()))+a[n+1:]
for i in range(1,n+1):b[i]=a[i]-a[i-1]#初始化b数组while q:l,r,c=map(int,input().split())b[l]+=cb[r+1]-=cq-=1#a数组没有用了,将a更新一遍
for i in range(1,n+1):a[i]=a[i-1]+b[i]print(a[i],end=' ')

三、差分矩阵

在这里插入图片描述

写法一:

def insert(matrix,x1,y1,x2,y2,c):#差分数组matrix[x1][y1]+=cmatrix[x2+1][y1]-=cmatrix[x1][y2+1]-=cmatrix[x2+1][y2+1]+=cdef main():n, m, q = map(int, input().split())matrix=[[0 for i in range(m+10)] for j in range(n+10)]#定义二维数组for i in range(1,n+1):row =list(map(int, input().split()))for j in range(m):insert(matrix,i,j+1,i,j+1,row[j])for i in range(q):x1,y1,x2,y2,c=map(int,input.split())insert(matrix,x1,y1,x2,y2,c)for i in range(1,n+1):for j in range(1,m+1):matrix[i][j]+=matrix[i-1][j]+matrix[i][j-1]-matrix[i-1][j-1]print(matrix[i][j],end=" ")print()if __name__=="__main__":main()

写法二:

print(" ".join(map(str,dt[i][1:m+1])))

这行代码将列表dt[i][1:m+1]中的元素转换成字符串,然后用空格连接起来,并打印输出。其中:

  1. map(str, dt[i][1:m+1]) 表示将列表 dt[i][1:m+1] 中的每个元素都转换成字符串类型;
  2. " ".join(…) 表示将字符串列表中的元素用空格连接起来,形成一个新的字符串;
  3. print(…) 表示将拼接好的字符串打印输出。
def insert(b,x1,y1,x2,y2,c):b[x1][y1] += cb[x2+1][y1] -= cb[x1][y2+1] -= cb[x2+1][y2+1] += cn,m,q = map(int,input().split())
ls = []
dt = [[0 for _ in range(1010)] for _ in range(1010)]
for i in range(n):ls.append(list(map(int,input().split())))
for i in range(1,n+1):for j in range(1,m+1):insert(dt,i,j,i,j,ls[i-1][j-1])
while q >0:q -= 1x1,y1,x2,y2,c = map(int,input().split())insert(dt,x1,y1,x2,y2,c)
for i in range(1,n+1):for j in range(1,m+1):dt[i][j] +=dt[i-1][j]+dt[i][j-1] - dt[i-1][j-1]
for i in range(1,n+1):print(" ".join(map(str,dt[i][1:m+1])))

四、增减序列

差分解决一段区域同时增加或减少的问题
给区间【L,R】上都加上一个常数c,则b[L] += c , b[R + 1] -=c

求出a的差分序列b,其中b1 = a1,b(i) = a(i) - a(i - 1) (2 <= i <= n)。令b(n + 1) = 0,题目对序列a的操作,相当于每次可以选出b1,b2…b(n + 1)中的任意两个数,一个加1,另外一个减一。目标是把b2,b3,…bn变为全0。最终得到的数列a就是由 n 个 b1 构成的

任选两个数的方法可分为四类
1、2 <= i , j <=n(优先)
2、i = 1, 2 <=j <=n
3、2 <= i <= n , j = n + 1
4、i = 1, j = n + 1(没有意义)

设b2,b3…bn中正数总和为p,负数总和的绝对值为q。首先以正负数匹配的方式尽量执行1类操作,可执行min(p,q)次。剩余|p - q|个为匹对,每个可以选与b1或b(n + 1)匹配,即执行2 或 3 类操作,共需|p - q|次

综上所诉,最少操作次数为min(p,q) + |p - q|。根据|p - q|次第2、3类操作的选择情况,能产生|p - q| + 1中不同的b1的值,即最终得到的序列a可能有|p - q| + 1 种

在这里插入图片描述

print(f"{max(pos, neg)}\n{abs(pos - neg) + 1}")

这是一种 f-string 的写法,用于格式化字符串。其中,大括号内的部分会被替换为相应的变量或表达式的值。具体来说:

f"xxx":表示这是一个 f-string,其中 xxx 是字符串内容,可以包含普通文本和大括号表达式。
{max(pos, neg)}:表示一个大括号表达式,会被替换为 pos 和 neg 中的最大值。
\n:表示换行符。
{abs(pos - neg) + 1}:表示一个大括号表达式,会被替换为 pos 和 neg 的差值的绝对值加上 1。

n = int(input())
a = [0] * (n + 2)
for i in range(1,n+1):x = int(input())a[i] += xa[i+1] -= xpos, neg = 0, 0
for i in range(2, n+1):if a[i] > 0:pos += a[i]else:neg -= a[i]print(f"{max(pos, neg)}\n{abs(pos - neg) + 1}")

相关文章:

学python的第二天---差分

一、改变数组元素&#xff08;差分&#xff09;方法一&#xff1a;差分数组map(int,input().split())for b in arr[:n]:print(1 if b else 0,end )方法二&#xff1a;区间合并interval.sort(keylambda x:x[0])二、差分a [0] list(map(int, input().split())) a[n 1:]三、差…...

数据结构入门5-2(数和二叉树)

目录 注&#xff1a; 树的存储结构 1. 双亲表示法 2. 孩子表示法 3. 重要&#xff1a;孩子兄弟法&#xff08;二叉树表示法&#xff09; 森林与二叉树的转换 树和森林的遍历 1. 树的遍历 2. 森林的遍历 哈夫曼树及其应用 基本概念 哈夫曼树的构造算法 1. 构造过程 …...

把Redis当作队列来用,到底合适吗?

文章目录 前言从最简单的开始:List 队列发布/订阅模型:Pub/Sub趋于成熟的队列:Stream1) Stream 是否支持「阻塞式」拉取消息?2) Stream 是否支持发布 / 订阅模式?3) 消息处理时异常,Stream 能否保证消息不丢失,重新消费?4) Stream 数据会写入到 RDB 和 AOF 做持久化吗?…...

Python学习-----项目设计1.0(设计思维和ATM环境搭建)

目录 前言&#xff1a; 项目开发流程 MVC设计模式 什么是MVC设计模式&#xff1f; ATM项目要求 ATM项目的环境搭建 前言&#xff1a; 我个人学习Python大概也有一个月了&#xff0c;在这一个月中我发布了许多关于Python的文章&#xff0c;建立了一个Python学习起步的专栏…...

(九)python网络爬虫(理论+实战)——爬虫实战:指定关键词的百度新闻爬取

系列文章目录 (1)python网络爬虫—快速入门(理论+实战)(一) (2)python网络爬虫—快速入门(理论+实战)(二) (3) python网络爬虫—快速入门(理论+实战)(三) (4)python网络爬虫—快速入门(理论+实战)(四) (5)...

数据分析面试、笔试题汇总+解析(六)

&#xff08;接上篇&#xff09; 面试题&#xff08;MySQL篇&#xff09; 3. 如何提高MySQL的查询速度&#xff1f; 考点解析&#xff1a; 考察面试者对MySQL查询优化的理解 参考答案&#xff1a; &#xff08;因为这个问题如果回答的详细一点可以写上一整篇&#xff0c;…...

vue3+rust个人博客建站日记3-编写主页

内容 绘制了主页的基本布局设置了封装了header栏组件并设置了全局黑夜模式. 选择一个组件库-Naive UI 如果没有设计能力&#xff0c;又想开发出风格统一的前端页面。就一定要选择一个漂亮的组件库。 本次项目选择使用Naive UI&#xff0c;NaivUI库曾被Vue框架作者尤雨溪推荐…...

前端常考react面试题(持续更新中)

react diff 算法 我们知道React会维护两个虚拟DOM&#xff0c;那么是如何来比较&#xff0c;如何来判断&#xff0c;做出最优的解呢&#xff1f;这就用到了diff算法 diff算法的作用 计算出Virtual DOM中真正变化的部分&#xff0c;并只针对该部分进行原生DOM操作&#xff0c;而…...

C++11多线程编程 二:多线程通信,同步,锁

C11多线程编程 一&#xff1a;多线程概述 C11多线程编程 二&#xff1a;多线程通信&#xff0c;同步&#xff0c;锁 C11多线程编程 三&#xff1a;锁资源管理和条件变量 2.1 多线程的状态及其切换流程分析 线程状态说明&#xff1a; 初始化&#xff08;Init&#xff09;&am…...

js——原型和原型链

最近看了很多面试题&#xff0c;看到这个js原型是常考点&#xff0c;于是&#xff0c;我总结了一些该方面的知识点分享给大家&#xff0c;其实原型就是那么一回事&#xff0c;搞明白了就没啥了。结果如下图所示&#xff1a;原型原型又可分为显式原型和隐式原型1.1显式原型显式原…...

[计算机网络(第八版)]第三章 数据链路层(学习笔记)

物理层解决了相邻节点透明传输比特的问题 3.1 数据链路层的几个共同问题 3.1.1 数据链路和帧 链路&#xff1a; 从一个节点到相邻节点的一段物理线路&#xff0c;中间没有任何其他的交换节点 数据链路&#xff1a; 节点间的逻辑通道是把实现控制数据传输的协议的硬件和软件加…...

void在不同场景下的意义

指针一般有三种含义&#xff1a;一是指明数据的位置&#xff0c;体现在指针的值&#xff0c;表示一个地址。二是表示数据类型的大小&#xff0c;例如int指针表示四个字节为一组数据&#xff0c;体现在指针的加减法如何计算。三是表示数据如何被解释&#xff0c;例如float指针和…...

Flume简介

Flume是一个高可用&#xff0c;高可靠&#xff0c;分布式的海量日志采集、聚合和传输的系统&#xff0c;能够有效的收集、聚合、移动大量的日志数据。 优点&#xff1a; 使用Flume采集数据不需要写一行代码&#xff0c;注意是一行代码都不需要&#xff0c;只需要在配置文件中…...

java简单学习

Java 基础语法 一个 Java 程序可以认为是一系列对象的集合&#xff0c;而这些对象通过调用彼此的方法来协同工作。下面简要介绍下类、对象、方法和实例变量的概念。 对象&#xff1a;对象是类的一个实例&#xff0c;有状态和行为。例如&#xff0c;一条狗是一个对象&#xff…...

Vue2 组件基础使用、父子组件之间的传值

一、什么是组件如画红框的这些区域都是由vue里的各种组件组成、提高复用信通常一个应用会以一棵嵌套的组件树的形式来组织&#xff1a;例如&#xff0c;你可能会有页头、侧边栏、内容区等组件&#xff0c;每个组件又包含了其它的像导航链接、博文之类的组件。为了能在模板中使用…...

代码随想录算法训练营 || 贪心算法 122 55 45

Day28122.买卖股票的最佳时机II力扣题目链接给定一个数组&#xff0c;它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易&#xff08;多次买卖一支股票&#xff09;。注意&#xff1a;你不能同时参与多笔交易…...

数据结构基础之栈和队列

目录​​​​​​​ 前言 1、栈 2、队列 2.1、实现队列 2.2、循环队列 前言 上一篇中我们介绍了数据结构基础中的《动态数组》&#xff0c;本篇我们继续来学习两种基本的数据结构——栈和队列。 1、栈 特点&#xff1a;栈也是一种线性结构&#xff0c;相比数组&#xff…...

【Spark分布式内存计算框架——Spark Streaming】3.入门案例(上)官方案例运行

2.1 官方案例运行 运行官方提供案例&#xff0c;使用【$SPARK_HOME/bin/run-example】命令运行&#xff0c;效果如下&#xff1a; 具体步骤如下&#xff1a; 第一步、准备数据源启动端口&#xff0c;准备数据 nc -lk 9999 spark spark hive hadoop spark hive 第二步、运行…...

【博学谷学习记录】超强总结,用心分享 | 架构师 Tomcat源码学习总结

文章目录TomcatTomcat功能需求分析Tomcat两个非常重要的功能&#xff08;身份&#xff09;Tomcat的架构&#xff08;设计实现&#xff09;连接器的设计连接器架构分析核心功能ProtocolHandler 组件1.EndPoint组件EndPoint类结构图2.Processor组件Processor类结构图3.Adapter组件…...

泛型<E>

泛型 案例引出泛型 按要求写出代码&#xff1a; 在ArrayList中添加3个Dog对象&#xff0c;Dog对象有name和age两个属性&#xff0c;且输出name和age public class test1 {public static void main(String[] args) {ArrayList list new ArrayList();list.add(new Dog(10,&quo…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...