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将请求分发…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
