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

Leetcode 3149. Find the Minimum Cost Array Permutation

  • Leetcode 3149. Find the Minimum Cost Array Permutation
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3149. Find the Minimum Cost Array Permutation

1. 解题思路

这一题的话就是一个动态规划的问题,不过他这个错位着实是把题目变得复杂了不少,唉……

思路上的话实在是没啥可多说的,整体来说就是动态规划加剪枝,唯一的问题就是细节实现上容易踩坑,这里就不一一赘述了,仅把代码放在下面,有兴趣的读者可以自行研究一下。

2. 代码实现

给出python代码实现如下:

class Solution:def findPermutation(self, nums: List[int]) -> List[int]:n = len(nums)status = 0best_score = math.inf@lru_cache(None)def dp(idx, status, first, pre, pre_score):nonlocal best_scoreif pre_score >= best_score:return math.inf, []if idx >= n:best_score = min(best_score, abs(pre - nums[first]) + pre_score)return abs(pre - nums[first]) + pre_score, []score, ans = math.inf, []for i in range(n):if status & (1 << i) == 0:if idx == 0:s, nxt = dp(idx+1, status | (1 << i), i, i, 0)else:s, nxt = dp(idx+1, status | (1 << i), first, i, pre_score + abs(pre-nums[i]))if s < score:ans = [i] + nxtscore = sreturn score, ansscore, ans = dp(0, 0, 0, 0, 0)return ans

提交代码评测得到:耗时7140ms,占用内存237.1MB。

相关文章:

Leetcode 3149. Find the Minimum Cost Array Permutation

Leetcode 3149. Find the Minimum Cost Array Permutation 1. 解题思路2. 代码实现 题目链接&#xff1a;3149. Find the Minimum Cost Array Permutation 1. 解题思路 这一题的话就是一个动态规划的问题&#xff0c;不过他这个错位着实是把题目变得复杂了不少&#xff0c;唉…...

Python | 为列表中的元素分配唯一值

我们可以给列表中的所有数字分配一个唯一的值&#xff0c;重复时它会保留给它的值。这是一个非常常见的问题&#xff0c;在Web开发中&#xff0c;处理物品id时会遇到。让我们讨论一下解决这个问题的一些方法。 1. 使用enumerate() 列表解析 # initializing list test_list …...

HTML炫酷的相册

目录 写在前面 HTML简介 完整代码 代码分析 系列推荐 写在最后 写在前面 本期小编给大家带来一个炫酷的旋转相册&#xff0c;快来解锁属于你的独家记忆吧&#xff01; HTML简介 HTML&#xff08;全称为超文本标记语言&#xff09;是一种用于创建网页结构和内容的标记语…...

C++笔试强训day20

目录 1.经此一役小红所向无敌 2.连续子数组最大和 3.非对称之美 1.经此一役小红所向无敌 链接 简单模拟即可。 需要注意的是&#xff1a; 除完之后有无余数&#xff0c;若有&#xff0c;则还可以再挨一次打。 #include <iostream> using namespace std; #define in…...

【PHP【实战项目】系统性教学】——使用最精简的代码完成用户的登录与退出

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…...

Linux下的常用基本指令

基本指令 前言一、ls 指令语法功能常用选项举例注意要点关于拼接关于 -a关于文件ls与/的联用ls与根目录ls与任意文件夹ls与常用选项与路径 ls -d与ls -ldls与ll 二、pwd命令语法功能常用选项注意要点window与Linux文件路径的区别家目录 三、cd 指令语法功能举例注意要点cd路径.…...

phpstorm环境配置与应用

在 PhpStorm 中配置 PHP 开发环境及进行一些常用的应用设置涉及以下几个主要步骤&#xff1a; ### 1. 安装和激活 PhpStorm - **下载安装**: 访问 JetBrains 官网下载最新版本的 PhpStorm 安装包&#xff0c;然后按照提示进行安装。 - **激活**: 启动 PhpStorm&#xff0c;你可…...

【Qt 学习笔记】Qt常用控件 | 布局管理器 | 水平布局Horizontal Layout

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt常用控件 | 布局管理器 | 水平布局Horizontal Layout 文章编号&…...

Hive Aggregation 聚合函数

Hive Aggregation 聚合函数 基础聚合 增强聚合...

Unity 性能优化之GPU Instancing(五)

提示&#xff1a;仅供参考&#xff0c;有误之处&#xff0c;麻烦大佬指出&#xff0c;不胜感激&#xff01; 文章目录 前言一、GPU Instancing使用方法二、使用GPU Instancing的条件三、GPU Instancing弊端四、注意五、检查是否成功总结 前言 GPU Instancing也是一种Draw call…...

LeetCode 138. 随机链表的复制

目录 1.原题链接&#xff1a; 2.结点拆分&#xff1a; 代码实现&#xff1a; 3.提交结果&#xff1a; 4.读书分享&#xff1a; 1.原题链接&#xff1a; 138. 随机链表的复制 2.结点拆分&#xff1a; ①.拷贝各个结点&#xff0c;连接在原结点后面&#xff1b; ②.处…...

【PC微信小程序点不动处理方法】

描述 在使用电脑小程序抓包的时候发现原来能点的小程序今天不能点了。就是原来有个输入车牌号的输入框点击会出现车牌号键盘&#xff0c;现在不行了&#xff0c;经过卸载安装发现不是微信的问题&#xff0c;是WeChatAppEx.exe 的bug。早期使用的是不带ex的都没有问题升级以后&…...

量化交易:日内网格交易策略.md

哈喽&#xff0c;大家好&#xff0c;我是木头左&#xff01; 本文将详细介绍日内网格交易策略的原理&#xff0c;并结合Python代码示例&#xff0c;展示如何在掘金平台上实现这一策略。 策略原理 日内网格交易策略的核心思想是在一天的交易时间内&#xff0c;通过设置多个买卖…...

Ubuntu 20.04在Anaconda虚拟环境中配置PyQt4

一、创建一个虚拟环境 1 创建一个python2.7的虚拟环境&#xff1a; conda create -n pyqt4 numpy matplotlib python2.72 在环境中安装几个需要的包&#xff1a; pip install Theano pip install python-opencv3.4.0.14 pip install qdarkstyle pip install dominate二、在主…...

charts3D地球--添加航线

要在地球视角下画出海运路线图 方案 添加 globl 地球创建geo地理坐标系创建canvas对象用于承载地图世界地图this.worldChart //初始化canvas节点let cav document.createElement("canvas");this.$echarts.registerMap("world", geoJson);this.worldCha…...

变色龙还是树懒:揭示大型语言模型在知识冲突中的行为

你是知识变色龙还是树懒?我今天在ICLR学到一个很有趣的术语,叫做证据顺序(order of evidence)。 大模型RAG处理知识冲突的探讨: 在检索增强生成(Retrieval-Augmented Generation, RAG)的过程中,技术团队会将检索到的前几名文档作为证据,并提示(prompt)给大型语言模型(Large La…...

Android OpenMAX(四)OMX Core

假设我们已经写好了所有的OMX组件,有vdec、venc、adec、aenc,接下来问题来了,我们应该如何管理这些组件呢(创建、销毁)?这一篇文章我们向上一层学习OMX Core提供的标准API。 OMX Core代码位于 OMX_Core.h OMX Core在OpenMAX IL架构中的位置位于IL Client与实际的OMX组件之…...

【Linux】轻量级应用服务器如何开放端口 -- 详解

一、测试端口是否开放 1、测试程序 TCP demo 程序&#xff08;可参考&#xff1a;【Linux 网络】网络编程套接字 -- 详解-CSDN博客&#xff09; 2、测试工具 Windows - cmd 窗口 输入命令&#xff1a;telnet [云服务器的公网ip] [port] 二、腾讯云安全组开放端口 1、安全组设…...

git如何查看密码

git查看用户名、邮箱 git config user.name git config user.email 也可以在系统&#xff0c;用户文件夹下面 gitconfig查看 通常无法查看git密码&#xff0c;运行以下命令 git config credential.helper 查看储存的方式&#xff0c;如果是manage 或manage-store则说明是…...

redis脑裂问题

1. 前言 脑裂就是指在主从集群中&#xff0c;同时有两个主节点&#xff0c;它们都能接收写请求。而脑裂最直接的影响&#xff0c;就是客户端不知道应该往哪个主节点写入数据&#xff0c;结果就是不同的客户端会往不同的主节点上写入数据。而且&#xff0c;严重的话&#xff0c;…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...