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数据库二进制日志导致磁盘满了处理过程
数据库的二进制日志是数据库管理系统(DBMS)用来记录所有对数据库进行修改的操作的记录。这种日志对于数据库的备份、恢复、复制和审计等操作至关重要。 以MySQL数据库为例,二进制日志(Binary Log)记录了所有更改数据的…...
前端面试题日常练-day07 【面试题】
题目 希望这些选择题能够帮助您进行前端面试的准备,答案在文末。 1. 在 JavaScript 中,以下哪个方法可以用于从数组的末尾添加一个或多个元素? A) push() B) pop() C) shift() D) unshift()2. 下列哪个 HTML 标签用于定义表格的表头&#…...
Uniapp H5开发常见问题解析
引言 在移动应用开发领域,Uniapp已经成为一个备受瞩目的技术框架,其跨平台能力和高效开发特性使得开发者能够更加便捷地构建出功能丰富、性能优越的应用程序。特别是在H5开发中,Uniapp的应用场景日益广泛,然而,随之而…...
QT状态机4-使用并行状态来避免组合爆炸
#include "MainWindow.h" #include "ui_MainWindow.h"MainWindow::MainWindow(QWidget *parent):...
MemoryModule - 应用编程细节
文章目录 MemoryModule - 应用编程细节概述笔记实验环境升级MemoryModule,在上下文中加入DLL在内存载入前的信息MemoryModule.hMemoryModule.cpp实现接口MemoryGetPayload() 整理 - 在内存载入的DLL中,取得资源表中的信息,取得载入前的DLL内容…...
Java程序CPU持续高,如何排查?
首先找到进程ID jps然后找到该进程用占用cpu高的线程 top -Hp 进程ID将线程ID转化为十六进制 printf “0x%x” 线程ID使用jstack 工具跟踪堆栈定位问题 jstack 进程ID | grep 十六进制线程ID -A 5说明,最后-A 5是打印出来后5行。...
(Java)心得:LeetCode——15.三数之和
一、原题 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。…...
Rust中忽略JSON反序列化时的不必要字段
在Rust中处理JSON数据时,经常会遇到JSON数据中包含一些在目标数据结构中不存在的字段的情况。如果你使用的是serde和serde_json这两个流行的库来处理JSON,那么有一些简单的方法可以忽略这些不必要的字段。 默认行为:忽略未知字段 在Rust中&…...
UDP多对多组播通信
广播和多播仅应用于UDP。TCP是一个面向连接的协议,TCP一定是点对点的,一点是两个主机来建立连接的,TCP肯定是单播。只有UDP才会使用广播和组播。 如下示例实现一个UDP多对多的组播通信,进程中有收、发两个线程,分别表…...
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 调用堆栈可以很好的帮助我们定位问题,特别是报错的Error日志 Debug.Log("Hello World");Debug.Log("This is a log m…...
二叉树的常见操作
建立树 复制二叉树 计算深度 计算总结点数 计算叶子结点数...
CSS 根据子元素选择父元素,并设置父元素的样式
场景举例:当子元素有增加了一个class时,需要影响其父元素的样式 可以使用":has"伪类来实现选择父元素的效果 <style>.parent:has(.child){background-color: #eee;}p{width:100px;border:1px solid #000;} </style> <body>…...
onnx转trt时,关于动态shape自动配置默认值的脚本
onnx转trt时,关于动态shape自动配置默认值,一般需要指定3个shape,分别是最小最优与最大。但是我们在测试时不想写那么多的代码,能否自动实现3个shape的配置,这里实现了一版。 import osimport tensorrt as trt import…...
实验室无法培养的菌,原来可以这么研究!
厌氧氨氧化(anammox)细菌在全球氮循环和废水氮去除中发挥着至关重要的作用,由于anammox细菌生长缓慢、难以培养等特点,对其生态学和生物学特性知之甚少。近日,凌恩生物合作客户重庆大学陈猷鹏教授团队在《Science of t…...
Xed编辑器开发第一期:使用Rust从0到1写一个文本编辑器
这是一个使用Rust实现的轻量化文本编辑器。学过Rust的都知道,Rust 从入门到实践中间还隔着好几个Go语言的难度,因此,如果你也正在学习Rust,那么恭喜你,这个项目被你捡到了。本项目内容较多,大概会分三期左右陆续发布&a…...
农业自动气象监测站:赋能智慧农业的新动力
在信息化、智能化快速发展的今天,农业领域也迎来了前所未有的变革。其中,农业自动气象监测站作为智慧农业的重要组成部分,正在发挥着越来越重要的作用。它们如同农业生产的“眼睛”和“耳朵”,实时感知和记录着大气的微妙变化&…...
2-6 任务 猜数小游戏(单次版)
本任务要求编写一个猜数小游戏(单次版),游戏规则是计算机产生一个0到100之间的随机整数,用户通过输入猜测的数字进行猜测,根据猜测情况给出提示,直到猜对为止。编程思路是利用while循环和多分支结构实现永真…...
springboot 定时任务解决方案
Scheduled (springboot 自带的 注解) 基于注解Scheduled默认为单线程,开启多个任务时,任务的执行时机会受上一个任务执行时间的影响。 EnableScheduling注解: 在配置类上使用,开启计划任务的支持(类上)。…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
