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

算法竞赛之离散化技巧 python

news 来源：原创 2025/5/25 17:53:22

离散化

不改变数据相对大小的情况下，对数据进行相应的下标映射，即离散化。

例如：【100,200,300,400,500】，离散化后为【1,2,3,4,5】

什么时候可以离散化：当数据只与它们之间的相对大小有关，而与具体是多少无关

实战演练

LCP74.最强祝福力场 https://leetcode.cn/problems/xepqZ5/

在这里插入图片描述

提示：

数据范围1e9，该离散化技巧出山了

题解code：

class Solution:def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:x_set = set()y_set = set()for i, j, s in forceField:x_set.add(2 * i - s)y_set.add(2 * j - s)x_set.add(2 * i + s)y_set.add(2 * j + s)  # 通过*2来避免出现0.5这样的小数x_set_list = sorted(x_set)y_set_list = sorted(y_set)  # 集合转为列表m = len(x_set_list)n = len(y_set_list)# 初始化二位差分数组diff = [[0] * (n + 2) for _ in range(m + 2)]# 离散化：通过下标来映射for i, j, s in forceField:x1 = bisect_left(x_set_list, 2 * i - s) + 1y1 = bisect_left(y_set_list, 2 * j - s) + 1x2 = bisect_left(x_set_list, 2 * i + s) + 1y2 = bisect_left(y_set_list, 2 * j + s) + 1  # 通过二分查找得到下标# 二维差分diff[x1][y1] += 1diff[x2 + 1][y1] -= 1diff[x1][y2 + 1] -= 1diff[x2 + 1][y2 + 1] += 1ans = 0# 把二维差分数组还原为原数组for i in range(1, m + 2):for j in range(1, n + 2):diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]ans = max(ans, diff[i][j])return ans

涉及的二维差分可点此进入详细讲解
涉及的二分查找可点此进入详细讲解

总结

离散化的本质是一种哈希：将离散的数字（浮点数），转换成1-n
所有仅关注偏序关系的题目，均可以先离散化处理

如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注谢谢

算法竞赛之离散化技巧 python

目录离散化实战演练总结离散化不改变数据相对大小的情况下，对数据进行相应的下标映射，即离散化。例如：【100,200,300,400,500】，离散化后为【1,2,3,4,5】什么时候可以离散化：当数据只与它们之间的相对大小有关&a…...

编程日记 2025/5/25 17:53:22

1.CSS的三大特性

css有三个非常重要的三个特性：层叠性、继承性、优先级 1.1 层叠性想通选择器给设置想听的样式，此时一个样式就会覆盖（层叠）另一个冲突的样式。层叠性主要是解决样式冲突的问题。 <!DOCTYPE html> <html lang"en&…...

编程日记 2025/5/25 1:49:24

由于请求的竞态问题，前端仔喜提了一个bug

在平常的开发过程中，你可能会遇到这样一个bug。测试：我在测一个输入框搜索的功能时，告诉你通过输入框输入的内容，和最终通过输入内容搜索出来的结果对不上。前端：我是通过调用后端接口拿到的数据，这明显…...

编程日记 2025/5/26 3:53:28

HTML `＜head＞` 元素详解

在 HTML 文档中，<head> 元素是一个非常重要的部分，它包含了文档的元数据（metadata）和其他与文档相关的信息。虽然 <head> 中的内容不会直接显示在网页上，但它对网页的行为、样式和搜索引擎优化&#xff08…...

编程日记 2025/5/26 3:56:26

基于RAG构建Text2SQL的实战教程

大家好，我是herosunly。985院校硕士毕业，现担任算法研究员一职，热衷于大模型算法的研究与应用。曾担任百度千帆大模型比赛、BPAA算法大赛评委，编写微软OpenAI考试认证指导手册。曾获得阿里云天池比赛第一名，CCF比赛第二名，科大讯飞比赛第三名。授权多项发明专利。对机器学…...

编程日记 2025/5/25 6:40:40

GPT-4对话模型在客服中的应用与前景：开启智能客服新时代

GPT-4对话模型在客服中的应用与前景：开启智能客服新时代随着人工智能技术的迅猛发展，基于深度学习的对话模型在各个领域中得到了广泛应用。其中，GPT-4对话模型在客服系统中的应用尤为引人注目。本文将探讨GPT-4在客服中的应用与未来发展前景，并结合具体代码示例进行说明。…...

编程日记 2025/5/20 8:16:31

我想通过python语言，学习数据结构和算法该如何入手？

学习数据结构和算法是编程中的重要基础，Python 是一个非常适合入门的语言。以下是学习数据结构和算法的步骤和建议： 1. 掌握 Python 基础确保你对 Python 的基本语法、数据类型、控制结构（如循环、条件语句）、函数等有扎实的理…...

编程日记 2025/5/23 17:09:07

Java多线程的面试面试题及答案解析

什么是进程？什么是线程？有什么区别？ 进程是系统资源分配的基本单位，拥有独立的地址空间。线程是 CPU 调度和分派的基本单位，是比进程更小的独立执行的单位，共享所在进程的内存空间等资源。一个进程可以包含…...

编程日记 2025/5/22 22:07:50

python flask中使用or查询和and查询，还有同时使用or、and的情况

在 Flask 中处理数据库查询时，通常会结合使用 ORM 工具，例如 SQLAlchemy。以下是 or 查询、and 查询以及两者同时使用的示例。文章目录基础准备1. 使用 or_ 查询2. 使用 and_ 查询3. 同时使用 or_ 和 and_4. 更加复杂的嵌套查询基础准备假设有一个…...

编程日记 2025/5/22 22:07:08

C# 解析视频流播放全解析

在多媒体技术日益发达的今天，视频流播放已经成为众多应用中不可或缺的功能。对于开发者而言，掌握如何使用编程语言来解析和播放视频流是一项重要的技能。本文将深入探讨如何使用 C# 来实现视频流的解析与播放。一、视频流播放原理简介视频流是将视频…...

编程日记 2025/5/25 14:30:06

关于为什么java中nextInt()和nextLine()不能混用 | nextInt()和nextInt()之类的可以一起用

键盘录入的区别： 第一套体系：遇到空格、制表符、回车都结束，并且都不接收 nextInt()、nextDouble()、next() 遇到空格、制表符、回车就结束，只接收其之前的数据，空格以及空格之后的数据都在缓冲区内，如果…...

编程日记 2025/5/22 13:16:57

计算机图形学：实验一 OpenGL基本绘制

1.OpenGL的环境配置： 集成开发环境Visual Studio Community 2019的安装： 在Windows一栏选择使用C的桌面开发；再转到“单个组件”界面，在“编译器、生成工具和运行时”一栏选择用于“Windows的C CMake工具”；然后转到…...

编程日记 2025/5/21 17:56:34

Node.js 到底是什么

Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境，它允许开发者使用 JavaScript 编写服务器端代码。一、主要特点 1. 事件驱动和非阻塞 I/O 模型 Node.js 采用事件驱动架构，通过回调函数处理 I/O 操作，这使得它在处理大量并发请…...

编程日记 2025/5/26 3:08:06

2022年全国职业院校技能大赛网络系统管理赛项模块A：网络构建（样题5）

目录任务描述任务清单（一）基础配置（二）有线网络配置（三）无线网络配置（四）出口网络配置附录1：拓扑图附录2：地址规划表任务描述随着业务的发展，现在要对海琼银行进行全网改造，为其它区域的网络提供高效的保障服务。同时，海琼银行还针对各个分支行、网点的…...

编程日记 2025/5/1 2:39:27

智慧脚下生根，智能井盖监测终端引领城市安全新革命

在繁忙的都市生活中，我们往往只关注地面的繁华与喧嚣，却忽略了隐藏在地面之下的基础设施——井盖。这些看似不起眼的井盖，实则承担着排水、通讯、电力等重要功能，是城市安全运转的重要一环。然而，传统的井盖管理面临着…...

编程日记 2025/5/23 19:15:58

ES6 简单练习笔记--变量申明

一、ES5 变量定义 1.在全局作用域中 this 其实就是window对象 <script>console.log(window this) </script>输出结果: true 2.在全局作用域中用var定义一个变量其实就相当于在window上定义了一个属性例如: var name "孙悟空" 其实就相当于执行了 win…...

编程日记 2025/5/22 21:36:07

MsfVenom木马制作及使用

msfvenom基本用法 1、功能介绍 msfvenom的功能：常用于生成木马，在目标机器执行，在本地机器kali中上线，与反弹shell类似。MsfVenom可以生成两种类型的攻击载荷： （1）Payload：Payloa…...

编程日记 2025/5/25 13:35:47

ChromeOS 132 版本更新

ChromeOS 132 版本更新 1. 企业定制化 Chrome Web Store 管理员现在可以使用新设置定制 Chrome Web Store 以适应他们管理的用户，包括以下功能： 添加公司标志添加首页横幅和自定义公告策划扩展集合实施基于类别的控制这些设置可以通过管理员控制台进…...

编程日记 2025/5/25 2:50:11

MySQL(表空间)

开始前先打开此图配合食用 MySQL表空间| ProcessOn免费在线作图,在线流程图,在线思维导图 InnoDB 空间文件中的页面管理后面也会持续更新，学到新东西会在其中补充。建议按顺序食用，欢迎批评或者交流！ 缺什么东西欢迎评论！我都…...

编程日记 2025/5/23 19:15:23

智能化加速标准和协议的更新并推动验证IP（VIP）在芯片设计中的更广泛应用

作者：Karthik Gopal, SmartDV Technologies亚洲区总经理智权半导体科技（厦门）有限公司总经理随着AI技术向边缘和端侧设备广泛渗透，芯片设计师不仅需要考虑在其设计中引入加速器，也在考虑采用速度更快和带宽更高的总…...

编程日记 2025/5/25 0:20:47

Chrome远程桌面无法连接怎么解决？

Chrome远程桌面连接已停止工作 Chrome远程桌面是一款极为便捷的浏览器插件，能够帮助用户将自己的计算机连接到其他设备，无论是手机、平板电脑还是其他电脑。然而，在实际使用中，许多用户可能会面临各种各样的问题，比如…...

编程日记 2025/5/23 8:08:39

springcloud alibaba 五大组件

Spring Cloud Alibaba是Spring Cloud的一个子项目，致力于为构建分布式应用提供一站式解决方案。它基于阿里巴巴的底层Java开源框架，主要包含以下五大核心组件： 1. Nacos（服务注册与配置中心） 功能：Nacos提…...

编程日记 2025/5/25 12:47:59

es 3期第25节-运用Rollup减少数据存储

#### 1.Elasticsearch是数据库，不是普通的Java应用程序，传统数据库需要的硬件资源同样需要，提升性能最有效的就是升级硬件。 #### 2.Elasticsearch是文档型数据库，不是关系型数据库，不具备严格的ACID事务特性&#xff…...

编程日记 2025/5/23 19:03:57

理解深度学习pytorch框架中的线性层

文章目录 1. 数学角度： y W x b \displaystyle y W\,x b yWxb示例 2. 编程实现角度： y x W T b \displaystyle y x\,W^T b yxWTb3. 常见错误与易混点解析4. 小结参考链接在神经网络或机器学习的线性层（Linear Layer / Fully Connect…...

编程日记 2025/5/22 11:37:38

“上门按摩” 小程序开发项目：基于 SOP 的全流程管理

在竞争激烈的生活服务市场，“上门按摩” 服务需求日益增长。为满足这一需求，我们启动了 O2O 模式的 “上门按摩” 小程序开发项目，该项目涵盖客户端、系统管理端、技师端。以下将通过各类 SOP 对项目进行全面管理，确保项目顺利推进。一、项目启动 SOP：5W2H 分析法 What（…...

编程日记 2025/5/24 10:02:30

【xcode 16.2】升级xcode后mac端flutter版的sentry报错

sentry_flutter 7.11.0 报错 3 errors in SentryCrashMonitor_CPPException with the errors No type named terminate_handler in namespace std (line 60) and No member named set_terminate in namespace std 替换sentry_flutter版本为： 8.3.0 从而保证oc的…...

编程日记 2025/5/24 15:47:50

Unity自学之旅05

Unity自学之旅05 Unity学习之旅⑤📝 AI基础与敌人行为🥊 AI导航理论知识（基础）开始实践 🎃 敌人游戏机制追踪玩家攻击玩家子弹碰撞完善游戏失败条件 🤗 总结归纳 Unity学习之旅⑤ 📝 AI基础与敌…...

编程日记 2025/5/24 15:47:26

LINUX下设置分离状态（Detached State）和未设置分离状态的主要区别在于线程资源的管理方式和线程的生命周期。以下是两种状态的对比：

1. 设置分离状态（Detached State） 资源管理： 线程终止时，系统会自动释放与线程相关的所有资源（如线程栈、线程控制块）。不需要其他线程显式回收（pthread_join）。线程生命周期&…...

编程日记 2025/5/24 19:49:11

软考信安26~大数据安全需求分析与安全保护工程

1、大数据安全威胁与需求分析 1.1、大数据相关概念发展大数据是指非传统的数据处理工具的数据集，具有海量的数据规模、快速的数据流转、多样的数据类型和价值密度低等特征。大数据的种类和来源非常多，包括结构化、半结构化和非结构化数据。 1.2、大数据安全威胁分析（…...

编程日记 2025/5/23 2:02:47

Alibaba Spring Cloud 一核心组件、特性

Alibaba Spring Cloud 是 Alibaba 基于 Spring Cloud 的分布式微服务解决方案，提供了一套高性能、高可靠的微服务开发和运维工具。它扩展了 Spring Cloud 的功能，并优化了许多在生产环境中的实践场景，例如服务发现、配置管理、熔断限流等。 …...

编程日记 2025/5/22 11:34:54

通过脚本申请免费SSL证书（泛解析SSL证书）

参考来源 1.https://github.com/acmesh-official/acme.sh/wiki/%E8%AF%B4%E6%98%8E 2.https://github.com/acmesh-official/acme.sh/wiki/dns-manual-mode 3.https://github.com/acmesh-official/acme.sh/wiki/dnsapi 安装 acme.sh 配置账号配置默认CA 安装依赖 # Cento…...

编程日记 2025/5/22 10:34:29

基于相机内参推导的透视投影矩阵

基于相机内参推导透视投影矩阵（splatam）： M c a m [ 2 ⋅ f x w 0.0 ( w − 2 ⋅ c x ) w 0.0 0.0 2 ⋅ f y h ( h − 2 ⋅ c y ) h 0.0 0 0 f a r n e a r n e a r − f a r 2 f a r ⋅ n e a r n e a r − f a r 0.0 0.0 − 1.0 0.0 ] M_…...

编程日记 2025/5/25 2:19:16

代码随想录算法训练营day34

代码随想录算法训练营 —day34 文章目录代码随想录算法训练营前言一、62.不同路径动态规划动态规划空间优化二、63. 不同路径 II动态规划动态规划优化空间版三、343. 整数拆分动态规划贪心算法 96.不同的二叉搜索树总结前言今天是算法营的第34天，希望自己能够…...

编程日记 2025/5/24 5:00:01

Orgill EDI需求分析

Orgill 是一家位于美国的家族企业，主要为五金零售商、建材供应商及相关行业提供全面的分销服务和支持，覆盖范围遍及全球。 EDI需求分析 EDI全称Electronic Data Interchange，中文名称是电子数据交换，也被称为“无纸化贸易”。EDI…...

编程日记 2025/5/23 2:47:08

好用的js工具类

格式化相关 // 数字每三位增加一个逗号 function toThousands(num) {if (num) {return num.toString().replace(/\d/, function(n) {// 先提取整数部分return n.replace(/(\d)(?(\d{3})$)/g, function($1) {return $1 ,})})} else {return 0} }//输出10,000 toThousands(10…...

编程日记 2025/5/24 4:59:33

C++ —— 基于范围的 for 循环

C —— 基于范围的 for 循环语法push_back() 与 emplace_back() 的区别**emplace_back()** 示例代码如下：**push_back()** 示例代码如下： 容器中的元素是结构体和类语法 C11中引入了基于范围的for循环，语法如下： for (迭代的变…...

编程日记 2025/5/25 14:55:27

15-spring整合mybatis方式一

spring整合mybatis 方式一【重要】步骤: 1.导入相关jar包 junit mybatis mysql数据库 spring相关的 aop织入 mybatis-spring 【new】 junit junit 4.12 mysql mysql-connector-java 8.0.23 org.mybatis mybatis 3.5.2 org.springframework spring-webmvc 5…...

编程日记 2025/5/22 11:11:32

数据结构：二叉树—面试题（一）

目录 1、相同的树 2、另一棵树的子树 3、翻转二叉树 4、平衡二叉树 5、对称二叉树 6、二叉树遍历 7、二叉树的分层遍历 1、相同的树习题链接https://leetcode.cn/problems/same-tree/description/https://leetcode.cn/problems/same-tree/description/ 描述&#xff1a…...

编程日记 2025/5/23 18:49:22

GPU算力平台|在GPU算力平台部署可图大模型Kolors的应用实战教程

文章目录一、GPU算力服务平台GPU算力服务平台的概述二、平台账号注册流程可图大模型Kolors的应用实战教程可图大模型的介绍可图大模型的应用场景可图大模型Kolors的部署步骤一、GPU算力服务平台 GPU算力服务平台的概述蓝耘GPU算力平台专为高性能计算设计，广泛…...

编程日记 2025/5/24 4:52:33

Linux探秘坊-------4.进度条小程序

1.缓冲区 #include <stdio.h> int main() {printf("hello bite!");sleep(2);return 0; }执行此代码后，会先停顿两秒，再打印出hello bite，但是明明打印在sleep前面，为什么会后打印呢？ 因为&#xff…...

编程日记 2025/5/24 19:59:13

Ansys Motor-CAD：IPM 电机实验室 - 扭矩速度曲线

各位电动机迷们，大家好： 在本博客中，我讨论了如何使用 Ansys Motor-CAD 通过 LAB 模块获取扭矩速度曲线。使用每安培最大扭矩电机控制策略，并涵盖恒定扭矩区域和恒定功率、磁通减弱区域。分析了高转子速度如何影响功率输出。模型…...

编程日记 2025/5/21 22:15:19

关于事件捕获和事件冒泡的理解

我一直对事件捕获和事件冒泡是挺困惑的，好像理解了，但又感觉哪里不对。这篇文章打算深入探讨一些细节性的问题，更好的理解事件捕获和事件冒泡。当我们点击的时候，浏览器的默认行为是怎么样的？ 搞清楚这个非常的重要…...

编程日记 2025/5/22 21:25:43

如何使用HASH创建低交互式蜜罐系统

关于HASH HASH是一个用于创建和启动低交互蜜罐的框架，可以帮助广大研究人员轻松创建HTTP无关的低交互式软件蜜罐。 HASH 的主要理念是易于配置，能够灵活地模拟在 HTTP/HTTPs 上运行的任何软件。尽可能减少占用空间，避免被检测为蜜罐。功能…...

编程日记 2025/5/22 22:16:12

vue3+vite+ts安装wangeditor富文本编辑器

需求: 实现粘贴,上传图片时本地渲染但并不实现上传功能,工具栏移除不需要的工具安装方法看官网安装 | wangEditor 封装子组件 wangEditor.vue <template><div><div style"border: 1px solid #ccc; margin-top: 10px"><Toolbar:editor&qu…...

编程日记 2025/5/25 4:41:22

PostIn教程-安装配置

PostIn是一款国产开源免费的接口管理工具，包含项目管理、接口调试、接口文档设计、接口数据MOCK等模块，支持常见的HTTP协议、websocket协议等，支持免登陆本地接口调试，同时可以对项目进行灵活的成员权限、消息通知管理等。 1、服务…...

编程日记 2025/5/23 0:42:27

SpringBoot读取配置优先级顺序是什么？

Spring Boot外部化配置详解目录引言Spring Boot外部化配置概述配置加载优先级配置加载顺序详解实际案例总结引言 Spring Boot因其“开箱即用”的特性，极大地简化了Java应用的开发和部署过程。它通过外部化配置机制，允许开发者根据不同的环境&#x…...

编程日记 2025/5/25 1:14:37

群晖docker获取私有化镜像http: server gave HTTP response to HTTPS client].

群晖docker获取私有化镜像提示http: server gave HTTP response to HTTPS clien 问题描述层级时间用户事件Information2023/07/08 12:47:45cxlogeAdd image from xx.xx.31.240:1923/go-gitea/gitea:1.19.3Error2023/07/08 12:47:48cxlogeFailed to pull image [Get "http…...

编程日记 2025/5/25 1:14:16