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

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. 代码实现 题目链接&#xff1a;2967. Minimum Cost to Make Array Equalindromic 1. 解题思路 这一题其实我的思路有点笨&#xff0c;多少有点暴力求解的意思。 显然&#xff0c;如果我们给出全部的…...

【数据结构】什么是堆?

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 堆的概念及结构 堆的定义如下: n个元素的序列{k1,k2,...,kn}当且仅当满足以下关系时,称之为堆. 或 把这个序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个…...

生产环境_Spark处理轨迹中跨越本初子午线的经度列

使用spark处理数据集&#xff0c;解决gis轨迹点在地图上跨本初子午线的问题&#xff0c;这个问题很复杂&#xff0c;先补充一版我写的 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&#xff0c;恭喜您创建成功了 二、启动…...

SI24R03国产自主可控RISC-V架构MCU低功耗2.4GHz收发芯片SoC

目录 RISC-V架构的优势SI24R03/04特性射频收发器模块特征MCU 模块特征 其他特征 RISC-V架构的优势 相对于目前主流的英特尔X86架构及ARM等架构来说&#xff0c;RISC-V架构具有指令精简、模块化、可扩展、开源、免费等优点。RISC-V的基础指令集只有40多条&#xff0c;加上其他基…...

基于FPGA的温度控制系统设计(论文+源码)

1.系统设计 本次基于FPGA的智能温度控制系统&#xff0c;以FPGA为控制核心&#xff0c;采用自顶向下的设计方法&#xff0c;按照模块化设计的思路分别实现各个模块&#xff0c;再加以整合实现整个系统&#xff0c;从而达到了温度控制的目的。系统以水箱为被控对象&#xff0c;…...

C语言训练:三个字符串比较大小,实现两个整数数的交换统计二进制中1的个数

目录 一、编写程序&#xff0c;输入三个字符串&#xff0c;比较它们的大小&#xff0c;并将它们按由小到大的顺序输出。要求用函数、指针实现。要求:要采用函数调用&#xff0c;并用指向函数的指针作为函数的参数。 1.不使用函数指针作为参数&#xff0c;并自己模拟strcmp。 …...

module ‘tensorflow‘ has no attribute XXX 报错解决

问题描述&#xff1a; 粘了别人的tensorflow项目&#xff0c;运行总是报错module ‘tensorflow’ has no attribute什么什么 问题解决&#xff1a; 导入tensorflow的代码如下 import tensorflow as tf此时&#xff0c;某个某块报错&#xff0c;比如下面这个 那么就直接把tf.…...

MySQL数据库 DDL

目录 一、DDL 二、操作数据库 三、操作表 四、数据类型 五、表操作案例 六、修改表 七、删除表 一、DDL Data Definition Language&#xff0c;数据定义语言&#xff0c;用来定义数据库对象(数据库&#xff0c;表&#xff0c;字段) 。 二、操作数据库 &#xff08;1&am…...

力扣二叉树--总结篇(2)

前言 总体回顾&#xff1a;11.18-12.14&#xff0c;中间有一个星期左右因为考试没有写题。37道题。 内容 这是第二阶段刷的题 从路径到构造二叉树&#xff0c;合并二叉树&#xff0c;再到二叉搜索树&#xff0c;公共祖先问题 看到二叉树&#xff0c;看到递归 都会想&#…...

小米移动端页面练习---重点:导航栏点击下箭头内容的切换以及样式,高亮显示的实现

效果图 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

一&#xff0c;前提 从零开始创建一个项目&#xff0c;绑定了数据库 用到的技术栈&#xff1a;springBootmybatisPlusmysqlswaggermaven 二&#xff0c;创建项目步骤 1&#xff0c;创建项目 创建出来的项目结构如图所示 2&#xff0c;修改配置文件 因为我比较习惯yml语言&…...

【视点合成】代码解读:生成demo视频

变换工具 def render_3dphoto(src_imgs, # 输入的源图像&#xff0c;维度为 [batch_size, 3, height, width]mpi_all_src, # 输入的所有源图像的MPI&#xff0c;维度为 [batch_size, num_planes, 4, height, width]disparity_all_src, # 所有源图像的视差信息&…...

Process On在线绘制流程图

目录 一.ProcessOn 1.1.介绍 1.2.直接网上使用 二.绘制门诊流程图 三.绘制住院流程图 四.绘制药库采购入库流程图 五.绘制OA会议流程图 今天就到这里了哦!!!希望能帮到你哦&#xff01;&#xff01;&#xff01; 一.ProcessOn 1.1.介绍 ProcessOn&#xff08;流程&#…...

【Hadoop-OBS-Hive】利用华为云存储对象 OBS 作为两个集群的中间栈 load 文件到 Hive

【Hadoop-OBS-Hive】利用华为云存储对象 OBS 作为两个集群的中间栈 load 文件到 Hive 1&#xff09;压缩文件2&#xff09;上传文件到 OBS 存储对象3&#xff09;crontab 定时压缩上传4&#xff09;从 obs 上拉取下来文件后解压缩5&#xff09;判断对应文件是否存在6&#xff0…...

直线检测算子

hough_lines_dir 接口 hough_lines_dir(ImageDir : HoughImage, Lines : DirectionUncertainty, AngleResolution, Smoothing, FilterSize, Threshold, AngleGap, DistGap, GenLines : Angle, Dist) 参数 in&#xff1a; ImageDir :由边缘检测算子sobel_dir、edge_image获取的…...

如何在本地Docker中部署MinIO服务并实现远程访问管理界面

文章目录 前言1. Docker 部署MinIO2. 本地访问MinIO3. Linux安装Cpolar4. 配置MinIO公网地址5. 远程访问MinIO管理界面6. 固定MinIO公网地址 前言 MinIO是一个开源的对象存储服务器&#xff0c;可以在各种环境中运行&#xff0c;例如本地、Docker容器、Kubernetes集群等。它兼…...

逛商场。。。

题目名字 逛商场 题意 见到想买的物品&#xff0c;只要能买得起&#xff0c;就一定会买下来之后才会继续往前走&#xff1b;如果买不起就直接跳过 思路 接着&#xff0c;它读取数组 aa 的值&#xff0c;并存储在数组中。然后&#xff0c;程序读取一个整数 m。初始化计数器 cn…...

RTrPPG

研究背景 心率 (HR) 和脉搏率变异性 (PRV) 是允许分析心脏行为的两个生理参数。心率监测可以通过接触式和非接触式的两种方法进行。通常用于测量 HR 和 PRV 的两种接触式技术是心电图 (ECG) 和光电容积脉搏波 (PPG)。 ECG 测量由心脏活动引起的电场。另一方面&#xff0c;PPG …...

web应用开发技术的一些概念

一、Servlet 1.Servlet的工作过程&#xff1a; Servelt的工作流程示意图 &#xff08;1&#xff09;客户端发起一个Http请求到服务器&#xff0c;请求特定的资源或者是要执行特定的操作 &#xff08;2&#xff09;服务器在接收到请求后&#xff0c;根据请求相应的URL将请求分发…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...