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

LeetCode 第397场周赛个人题解

目录

100296. 两个字符串的排列差

原题链接

思路分析

AC代码

100274. 从魔法师身上吸取的最大能量

原题链接

思路分析

AC代码

100281. 矩阵中的最大得分

原题链接

思路分析

AC代码

100312. 找出分数最低的排列

原题链接

思路分析

AC代码


100296. 两个字符串的排列差

原题链接

两个字符串的排列差 - 力扣 (LeetCode) 竞赛

思路分析

签到题,两次遍历搞定

AC代码

class Solution:def findPermutationDifference(self, s: str, t: str) -> int:mp = dict()res = 0for i, x in enumerate(s):mp[x] = ifor i, x in enumerate(t):res += abs(i - mp[x])return res

100274. 从魔法师身上吸取的最大能量

原题链接

从魔法师身上吸取的最大能量 - 力扣 (LeetCode) 竞赛

思路分析

记忆化搜索

dfs(0)代表从0出发的最大能量,记忆化剪枝保证每个结点只走一次

时间复杂度O(n)

AC代码

class Solution:def maximumEnergy(self, energy: List[int], k: int) -> int:n = len(energy)@cache def dfs(x: int) -> int:if x >= n:return 0return energy[x] + dfs(x + k)return max(dfs(i) for i in range(n))

100281. 矩阵中的最大得分

原题链接

矩阵中的最大得分 - 力扣 (LeetCode) 竞赛

思路分析

典中典网格上递推,为了拼手速还是用的记忆化搜索

不过注意起点特判,可以在递归函数里面多加个bool参数

时间复杂度O(n^2)

AC代码

class Solution:def maxScore(self, g: List[List[int]]) -> int:m, n = len(g), len(g[0])@cachedef dfs(x: int, y: int, lim: bool):if x >= m or y >= n:return 0ret = -inf if lim else 0if x + 1 < m:ret = max(ret, g[x + 1][y] - g[x][y] + dfs(x + 1, y, False))if y + 1 < n:ret = max(ret, g[x][y + 1] - g[x][y] + dfs(x, y + 1, False))return retreturn max(dfs(i, j, True) for j in range(n) for i in range(m))

100312. 找出分数最低的排列

原题链接

找出分数最低的排列 - 力扣 (LeetCode) 竞赛

思路分析

看得出数据很弱啊,全排列+最优性剪枝就过了

就是全排列的暴搜,然后如果当前已经比最优解更差了就剪枝

时间复杂度:阶乘级别带剪枝的就不分析了


2024.5.1214:30

回看这道题发现就是状压dp求哈密顿回路板子题,而且起点一定是0,任何解可以轮转到0为起点

那么时间复杂度就是O(2^n * n)

AC代码

暴力

class Solution:def findPermutation(self, nums: list[int]) -> list[int]:n = len(nums)mi = n * nret = []path = []st = set()def dfs(res: int, s: int) -> None:nonlocal mi, path, ret, st# print(path, s, mi, res)if s >= mi:returnif (not res) and s + abs(path[-1] - nums[path[0]]) < mi:mi = s + abs(path[-1] - nums[path[0]])ret = path.copy()# print(ret, s)returnfor i in range(n):if not (i in st):path.append(i)st.add(i)t = 0 if res == n else abs(nums[path[-1]] - path[-2])dfs(res - 1, s + t)path.pop()st.remove(i)dfs(n, 0)return ret

状压dp

class Solution:def findPermutation(self, nums: List[int]) -> List[int]:n = len(nums)g = [[0] * n for _ in range(n)]for i in range(n):for j in range(n):g[i][j] = abs(i - nums[j])f = [[inf] * n for _ in range(1 << n)]ans = [["" + chr(ord('a') + n) * n] * n for _ in range(1 << n)]f[1][0] = 0ans[1][0] = "a"for i in range(1, 1 << n):if i & 1:for j in range(n):if i >> j & 1:for k in range(n):if i >> k & 1:t = f[i ^ (1 << j)][k] + g[k][j]s = ans[i ^ (1 << j)][k] + chr(ord('a') + j)if t < f[i][j]:f[i][j] = tans[i][j] = selif t == f[i][j] and s < ans[i][j]:ans[i][j] = smi = infret = str(n) * nfor i in range(1, n):t = f[(1 << n) - 1][i] + g[i][0]if t < mi:mi = f[(1 << n) - 1][i] + g[i][0]ret = ans[(1 << n) - 1][i]elif t == mi and ans[(1 << n) - 1][i] < ret:ret = ans[(1 << n) - 1][i]return [ord(x) - ord('a') for x in ret]

相关文章:

LeetCode 第397场周赛个人题解

目录 100296. 两个字符串的排列差 原题链接 思路分析 AC代码 100274. 从魔法师身上吸取的最大能量 原题链接 思路分析 AC代码 100281. 矩阵中的最大得分 原题链接 思路分析 AC代码 100312. 找出分数最低的排列 原题链接 思路分析 AC代码 100296. 两个字符串的排…...

Mysql数据库二进制日志导致磁盘满了处理过程

数据库的二进制日志是数据库管理系统&#xff08;DBMS&#xff09;用来记录所有对数据库进行修改的操作的记录。这种日志对于数据库的备份、恢复、复制和审计等操作至关重要。 以MySQL数据库为例&#xff0c;二进制日志&#xff08;Binary Log&#xff09;记录了所有更改数据的…...

前端面试题日常练-day07 【面试题】

题目 希望这些选择题能够帮助您进行前端面试的准备&#xff0c;答案在文末。 1. 在 JavaScript 中&#xff0c;以下哪个方法可以用于从数组的末尾添加一个或多个元素&#xff1f; A) push() B) pop() C) shift() D) unshift()2. 下列哪个 HTML 标签用于定义表格的表头&#…...

Uniapp H5开发常见问题解析

引言 在移动应用开发领域&#xff0c;Uniapp已经成为一个备受瞩目的技术框架&#xff0c;其跨平台能力和高效开发特性使得开发者能够更加便捷地构建出功能丰富、性能优越的应用程序。特别是在H5开发中&#xff0c;Uniapp的应用场景日益广泛&#xff0c;然而&#xff0c;随之而…...

QT状态机4-使用并行状态来避免组合爆炸

#include "MainWindow.h" #include "ui_MainWindow.h"MainWindow::MainWindow(QWidget *parent):...

MemoryModule - 应用编程细节

文章目录 MemoryModule - 应用编程细节概述笔记实验环境升级MemoryModule&#xff0c;在上下文中加入DLL在内存载入前的信息MemoryModule.hMemoryModule.cpp实现接口MemoryGetPayload() 整理 - 在内存载入的DLL中&#xff0c;取得资源表中的信息&#xff0c;取得载入前的DLL内容…...

Java程序CPU持续高,如何排查?

首先找到进程ID jps然后找到该进程用占用cpu高的线程 top -Hp 进程ID将线程ID转化为十六进制 printf “0x%x” 线程ID使用jstack 工具跟踪堆栈定位问题 jstack 进程ID | grep 十六进制线程ID -A 5说明&#xff0c;最后-A 5是打印出来后5行。...

(Java)心得:LeetCode——15.三数之和

一、原题 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的三元组。…...

Rust中忽略JSON反序列化时的不必要字段

在Rust中处理JSON数据时&#xff0c;经常会遇到JSON数据中包含一些在目标数据结构中不存在的字段的情况。如果你使用的是serde和serde_json这两个流行的库来处理JSON&#xff0c;那么有一些简单的方法可以忽略这些不必要的字段。 默认行为&#xff1a;忽略未知字段 在Rust中&…...

UDP多对多组播通信

广播和多播仅应用于UDP。TCP是一个面向连接的协议&#xff0c;TCP一定是点对点的&#xff0c;一点是两个主机来建立连接的&#xff0c;TCP肯定是单播。只有UDP才会使用广播和组播。 如下示例实现一个UDP多对多的组播通信&#xff0c;进程中有收、发两个线程&#xff0c;分别表…...

Linux技术---部署PXE服务器实现批量安装操作系统

部署PXE服务器实现批量安装操作系统 部署PXE服务器实现批量安装操作系统 部署PXE服务器实现批量安装操作系统1.安装相关服务组件1.1 安装tftp和xinetd1.2 安装DHCP服务1.3 准备 Linux 内核、初始化镜像文件、 PXE 引导程序、安装FTP服务并准备安装源1.4 配置启动菜单文件1.5 验…...

日志:打印技巧

一、概览 Unity日志打印技巧 常规日志打印彩色日志日志存储与上传日志开关日志双击溯源 二、常规日志打印 1、打印Hello World 调用堆栈可以很好的帮助我们定位问题&#xff0c;特别是报错的Error日志 Debug.Log("Hello World");Debug.Log("This is a log m…...

二叉树的常见操作

建立树 复制二叉树 计算深度 计算总结点数 计算叶子结点数...

CSS 根据子元素选择父元素,并设置父元素的样式

场景举例&#xff1a;当子元素有增加了一个class时&#xff0c;需要影响其父元素的样式 可以使用":has"伪类来实现选择父元素的效果 <style>.parent:has(.child){background-color: #eee;}p{width:100px;border:1px solid #000;} </style> <body>…...

onnx转trt时,关于动态shape自动配置默认值的脚本

onnx转trt时&#xff0c;关于动态shape自动配置默认值&#xff0c;一般需要指定3个shape&#xff0c;分别是最小最优与最大。但是我们在测试时不想写那么多的代码&#xff0c;能否自动实现3个shape的配置&#xff0c;这里实现了一版。 import osimport tensorrt as trt import…...

实验室无法培养的菌,原来可以这么研究!

厌氧氨氧化&#xff08;anammox&#xff09;细菌在全球氮循环和废水氮去除中发挥着至关重要的作用&#xff0c;由于anammox细菌生长缓慢、难以培养等特点&#xff0c;对其生态学和生物学特性知之甚少。近日&#xff0c;凌恩生物合作客户重庆大学陈猷鹏教授团队在《Science of t…...

Xed编辑器开发第一期:使用Rust从0到1写一个文本编辑器

这是一个使用Rust实现的轻量化文本编辑器。学过Rust的都知道&#xff0c;Rust 从入门到实践中间还隔着好几个Go语言的难度&#xff0c;因此&#xff0c;如果你也正在学习Rust,那么恭喜你&#xff0c;这个项目被你捡到了。本项目内容较多&#xff0c;大概会分三期左右陆续发布&a…...

农业自动气象监测站:赋能智慧农业的新动力

在信息化、智能化快速发展的今天&#xff0c;农业领域也迎来了前所未有的变革。其中&#xff0c;农业自动气象监测站作为智慧农业的重要组成部分&#xff0c;正在发挥着越来越重要的作用。它们如同农业生产的“眼睛”和“耳朵”&#xff0c;实时感知和记录着大气的微妙变化&…...

2-6 任务 猜数小游戏(单次版)

本任务要求编写一个猜数小游戏&#xff08;单次版&#xff09;&#xff0c;游戏规则是计算机产生一个0到100之间的随机整数&#xff0c;用户通过输入猜测的数字进行猜测&#xff0c;根据猜测情况给出提示&#xff0c;直到猜对为止。编程思路是利用while循环和多分支结构实现永真…...

springboot 定时任务解决方案

Scheduled (springboot 自带的 注解) 基于注解Scheduled默认为单线程&#xff0c;开启多个任务时&#xff0c;任务的执行时机会受上一个任务执行时间的影响。 EnableScheduling注解&#xff1a; 在配置类上使用&#xff0c;开启计划任务的支持&#xff08;类上&#xff09;。…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...