Leetcode 2967. Minimum Cost to Make Array Equalindromic
- Leetcode 2967. Minimum Cost to Make Array Equalindromic
- 1. 解题思路
- 2. 代码实现
- 题目链接:2967. Minimum Cost to Make Array Equalindromic
1. 解题思路
这一题其实我的思路有点笨,多少有点暴力求解的意思。
显然,如果我们给出全部的对称数并将其有序排列,那么对于其中每一个对称数作为目标值时的cost就是一个包含一个最小值的先减后增有序数列,而我们要做的就是求这个最小值。
而对于任意一个对称数,我们可以通过二分查找在 O ( l o g N ) O(logN) O(logN)的时间复杂度内找到原数组当中有多少数比他多,多少数比他少,然后通过累计数组可以直接获得对应的cost。
这些其实都还好,只是原则上感觉对于第一部分,对于这么有规律的东西应该有更好的算法可以更快找到最小值的,不过这里我暂时没想到,就直接遍历寻找了,所以感觉多少有点蠢了……
2. 代码实现
给出python代码实现如下:
@lru_cache(None)
def get_palindromes():ans = [0]for i in range(1, 10**6):s = str(i)a = int(s + s[::-1])if a <= 10**9:ans.append(a)b = int(s + s[:-1][::-1])if b <= 10**9:ans.append(b)return sorted(ans)class Solution:def minimumCost(self, nums: List[int]) -> int:n = len(nums)nums = sorted(nums)sums = [0] + list(accumulate(nums))palindromes = get_palindromes()ans = sums[-1]for x in palindromes:idx = bisect.bisect_right(nums, x)s = x * idx - (sums[idx] - sums[0]) + (sums[-1] - sums[idx]) - x * (n-idx)if ans >= s:ans = selse:breakreturn ans
提交代码评测得到:耗时2414ms,占用内存35.7MB。
相关文章:
Leetcode 2967. Minimum Cost to Make Array Equalindromic
Leetcode 2967. Minimum Cost to Make Array Equalindromic 1. 解题思路2. 代码实现 题目链接:2967. Minimum Cost to Make Array Equalindromic 1. 解题思路 这一题其实我的思路有点笨,多少有点暴力求解的意思。 显然,如果我们给出全部的…...
【数据结构】什么是堆?
🦄个人主页:修修修也 🎏所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 堆的概念及结构 堆的定义如下: n个元素的序列{k1,k2,...,kn}当且仅当满足以下关系时,称之为堆. 或 把这个序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个…...
生产环境_Spark处理轨迹中跨越本初子午线的经度列
使用spark处理数据集,解决gis轨迹点在地图上跨本初子午线的问题,这个问题很复杂,先补充一版我写的 import org.apache.spark.{SparkConf, SparkContext} import org.apache.spark.sql.{Row, SparkSession} import org.apache.spark.sql.func…...
Vue前端与后端放在一起的搭建方式
1.首先把后端项目搭建好 去到项目的存放位置 2.然后cmd黑窗口输入命令创建vue项目 3.创建成功后回到后端项目进行合并 3.1在File处选择Project Structure 3.2选择模块 3.3找到自己的vue项目 3.4疯狂next最后create 3.5选择Apply并确定OK,恭喜您创建成功了 二、启动…...
SI24R03国产自主可控RISC-V架构MCU低功耗2.4GHz收发芯片SoC
目录 RISC-V架构的优势SI24R03/04特性射频收发器模块特征MCU 模块特征 其他特征 RISC-V架构的优势 相对于目前主流的英特尔X86架构及ARM等架构来说,RISC-V架构具有指令精简、模块化、可扩展、开源、免费等优点。RISC-V的基础指令集只有40多条,加上其他基…...
基于FPGA的温度控制系统设计(论文+源码)
1.系统设计 本次基于FPGA的智能温度控制系统,以FPGA为控制核心,采用自顶向下的设计方法,按照模块化设计的思路分别实现各个模块,再加以整合实现整个系统,从而达到了温度控制的目的。系统以水箱为被控对象,…...
C语言训练:三个字符串比较大小,实现两个整数数的交换统计二进制中1的个数
目录 一、编写程序,输入三个字符串,比较它们的大小,并将它们按由小到大的顺序输出。要求用函数、指针实现。要求:要采用函数调用,并用指向函数的指针作为函数的参数。 1.不使用函数指针作为参数,并自己模拟strcmp。 …...
module ‘tensorflow‘ has no attribute XXX 报错解决
问题描述: 粘了别人的tensorflow项目,运行总是报错module ‘tensorflow’ has no attribute什么什么 问题解决: 导入tensorflow的代码如下 import tensorflow as tf此时,某个某块报错,比如下面这个 那么就直接把tf.…...
MySQL数据库 DDL
目录 一、DDL 二、操作数据库 三、操作表 四、数据类型 五、表操作案例 六、修改表 七、删除表 一、DDL Data Definition Language,数据定义语言,用来定义数据库对象(数据库,表,字段) 。 二、操作数据库 (1&am…...
力扣二叉树--总结篇(2)
前言 总体回顾:11.18-12.14,中间有一个星期左右因为考试没有写题。37道题。 内容 这是第二阶段刷的题 从路径到构造二叉树,合并二叉树,再到二叉搜索树,公共祖先问题 看到二叉树,看到递归 都会想&#…...
小米移动端页面练习---重点:导航栏点击下箭头内容的切换以及样式,高亮显示的实现
效果图 1.html <div><header><div class"header-ad"><img src"./images/ad.png" alt"" srcset""></div><div class"header-two-section"><div class"logo"><div c…...
从零开始创建一个项目,springBoot+mybatisPlus+mysql+swagger+maven
一,前提 从零开始创建一个项目,绑定了数据库 用到的技术栈:springBootmybatisPlusmysqlswaggermaven 二,创建项目步骤 1,创建项目 创建出来的项目结构如图所示 2,修改配置文件 因为我比较习惯yml语言&…...
【视点合成】代码解读:生成demo视频
变换工具 def render_3dphoto(src_imgs, # 输入的源图像,维度为 [batch_size, 3, height, width]mpi_all_src, # 输入的所有源图像的MPI,维度为 [batch_size, num_planes, 4, height, width]disparity_all_src, # 所有源图像的视差信息&…...
Process On在线绘制流程图
目录 一.ProcessOn 1.1.介绍 1.2.直接网上使用 二.绘制门诊流程图 三.绘制住院流程图 四.绘制药库采购入库流程图 五.绘制OA会议流程图 今天就到这里了哦!!!希望能帮到你哦!!! 一.ProcessOn 1.1.介绍 ProcessOn(流程&#…...
【Hadoop-OBS-Hive】利用华为云存储对象 OBS 作为两个集群的中间栈 load 文件到 Hive
【Hadoop-OBS-Hive】利用华为云存储对象 OBS 作为两个集群的中间栈 load 文件到 Hive 1)压缩文件2)上传文件到 OBS 存储对象3)crontab 定时压缩上传4)从 obs 上拉取下来文件后解压缩5)判断对应文件是否存在6࿰…...
直线检测算子
hough_lines_dir 接口 hough_lines_dir(ImageDir : HoughImage, Lines : DirectionUncertainty, AngleResolution, Smoothing, FilterSize, Threshold, AngleGap, DistGap, GenLines : Angle, Dist) 参数 in: ImageDir :由边缘检测算子sobel_dir、edge_image获取的…...
如何在本地Docker中部署MinIO服务并实现远程访问管理界面
文章目录 前言1. Docker 部署MinIO2. 本地访问MinIO3. Linux安装Cpolar4. 配置MinIO公网地址5. 远程访问MinIO管理界面6. 固定MinIO公网地址 前言 MinIO是一个开源的对象存储服务器,可以在各种环境中运行,例如本地、Docker容器、Kubernetes集群等。它兼…...
逛商场。。。
题目名字 逛商场 题意 见到想买的物品,只要能买得起,就一定会买下来之后才会继续往前走;如果买不起就直接跳过 思路 接着,它读取数组 aa 的值,并存储在数组中。然后,程序读取一个整数 m。初始化计数器 cn…...
RTrPPG
研究背景 心率 (HR) 和脉搏率变异性 (PRV) 是允许分析心脏行为的两个生理参数。心率监测可以通过接触式和非接触式的两种方法进行。通常用于测量 HR 和 PRV 的两种接触式技术是心电图 (ECG) 和光电容积脉搏波 (PPG)。 ECG 测量由心脏活动引起的电场。另一方面,PPG …...
web应用开发技术的一些概念
一、Servlet 1.Servlet的工作过程: Servelt的工作流程示意图 (1)客户端发起一个Http请求到服务器,请求特定的资源或者是要执行特定的操作 (2)服务器在接收到请求后,根据请求相应的URL将请求分发…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决
问题: pgsql数据库通过备份数据库文件进行还原时,如果表中有自增序列,还原后可能会出现重复的序列,此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”,…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
