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

第 397 场 LeetCode 周赛题解

A 两个字符串的排列差

在这里插入图片描述

模拟:遍历 s s s 记录各字符出现的位置,然后遍历 t t t 计算排列差

class Solution {public:int findPermutationDifference(string s, string t) {int n = s.size();vector<int> loc(26);for (int i = 0; i < n; i++)loc[s[i] - 'a'] = i;int res = 0;for (int i = 0; i < n; i++)res += abs(loc[t[i] - 'a'] - i);return res;}
};

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

在这里插入图片描述

模拟:设 p [ i ] p[i] p[i] 为从 i i i 出发能获得的最大能量,逆序遍历 e n e r g y energy energy p p p

class Solution {public:int maximumEnergy(vector<int>& energy, int k) {int n = energy.size();vector<int> p(n);for (int i = n - 1; i >= 0; i--)p[i] = i + k < n ? p[i + k] + energy[i] : energy[i];return *max_element(p.begin(), p.end());}
};

C 矩阵中的最大得分

在这里插入图片描述

前缀极值:可以发现一条移动路径的得分只和路径的终点和起点有关,所以当终点固定为 g r i d [ i ] [ j ] grid[i][j] grid[i][j] 时,起点值为 g r i d [ 0 , i ] [ 0 , j ] grid[0,i][0,j] grid[0,i][0,j] 中非 g r i d [ i ] [ j ] grid[i][j] grid[i][j] 的最小值时得分最大。所以枚举终点,用二维前缀维护子矩阵中非 g r i d [ i ] [ j ] grid[i][j] grid[i][j] 的最小值。

class Solution {public:int maxScore(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();int mn[m][n];int res = INT32_MIN;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (i == 0) {mn[i][j] = j == 0 ? grid[i][j] : min(mn[i][j - 1], grid[i][j]);if (j != 0)res = max(res, grid[i][j] - mn[i][j - 1]);} else {mn[i][j] = j == 0 ? min(mn[i - 1][j], grid[i][j]) : min({mn[i - 1][j], mn[i][j - 1], grid[i][j]});if (j != 0)res = max(res, grid[i][j] - min(mn[i - 1][j], mn[i][j - 1]));elseres = max(res, grid[i][j] - mn[i - 1][j]);}}return res;}
};

D 找出分数最低的排列

在这里插入图片描述

状态压缩:根据分数计算公式,有一个重要的结论是:把 p e r m perm perm 看成一个环,在环上选择不同位置作为数组起点可以得到不同的 p e r m perm perm 数组,但这些 p e r m perm perm 数组的分数是相同的,所以要想字典序最小, p e r m perm perm 首位为 0 0 0 。设 p [ c u r ] [ p i ] p[cur][pi] p[cur][pi] 为“当前各数的使用状态为 c u r cur cur (若 c u r > > i & 1 cur>>i\&1 cur>>i&1 i i i 已使用), p e r m perm perm 下一位为 p i pi pi ”的情况下,接下来能够获得的最大得分。通过记忆化搜索实现状态转移求 p [ 0 ] [ 0 ] p[0][0] p[0][0] , 同时用数组间接记录状态转移的路径。

class Solution {public:vector<int> findPermutation(vector<int>& nums) {int n = nums.size();int N = 1 << n;vector<vector<int>> p(N, vector<int>(n, -1));//-1:初始化标志vector<vector<int>> select(N, vector<int>(n, -1));//数组间接记录状态转移的路径function<int(int, int, int)> get = [&](int cur, int pi, int ind) {if (p[cur][pi] != -1)return p[cur][pi];if (ind == n - 1)//pi为perm的最后一个元素return p[cur][pi] = abs(pi - nums[0]);p[cur][pi] = INT32_MAX;for (int np = 0; np < n; np++)if ((cur >> np & 1) == 0 && np != pi)//枚举perm中pi的后一个元素npif (abs(pi - nums[np]) + get(cur | (1 << pi), np, ind + 1) < p[cur][pi]) {p[cur][pi] = abs(pi - nums[np]) + get(cur | (1 << pi), np, ind + 1);select[cur][pi] = np;//记录路径}return p[cur][pi];};get(0, 0, 0);vector<int> res;int new_mask, new_cur;for (int cur = 0, mask = 0; res.size() < n; mask = new_mask, cur = new_cur) {//重现路径res.push_back(cur);new_mask = mask | (1 << cur);new_cur = select[mask][cur];}return res;}
};

相关文章:

第 397 场 LeetCode 周赛题解

A 两个字符串的排列差 模拟&#xff1a;遍历 s s s 记录各字符出现的位置&#xff0c;然后遍历 t t t 计算排列差 class Solution {public:int findPermutationDifference(string s, string t) {int n s.size();vector<int> loc(26);for (int i 0; i < n; i)loc[s…...

文件存储解决方案-阿里云OSS

文章目录 1.菜单分级显示问题1.问题引出1.苹果灯&#xff0c;放到节能灯下面也就是id大于1272.查看菜单&#xff0c;并没有出现苹果灯3.放到灯具下面id42&#xff0c;就可以显示 2.问题分析和解决1.判断可能出现问题的位置2.找到递归返回树形菜单数据的位置3.这里出现问题的原因…...

基于Java的飞机大战游戏的设计与实现(论文 + 源码)

关于基于Java的飞机大战游戏.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89313362 基于Java的飞机大战游戏的设计与实现 摘 要 现如今&#xff0c;随着智能手机的兴起与普及&#xff0c;加上4G&#xff08;the 4th Generation mobile communication &#x…...

Vue路由开启步骤

1.在控制台输入命令 //控制台下载安装npm add vue-router3.6.5 2.在main.js下导入并注册组件 import Vue from vue import App from ./App.vue//控制台下载安装npm add vue-router3.6.5 //导入 import VueRouter from "vue-router";//注册 Vue.use(VueRouter) con…...

【碎片知识】2024_05_15

char int long float double运算的时候是从低转到高的&#xff0c;表达式的类型会自动提升或者转 换为参与表达式求值的最上级类型. 关于代码的说法正确的是&#xff08; &#xff09; #include <stdio.h> int main() {int x -1;unsigned int y 2;if (x > y){printf…...

彩虹聚合DNS管理系统

聚合DNS管理系统可以实现在一个网站内管理多个平台的域名解析&#xff0c;目前已支持的域名平台有&#xff1a;阿里云、腾讯云、华为云、西部数码、CloudFlare。本系统支持多用户&#xff0c;每个用户可分配不同的域名解析权限&#xff1b;支持API接口&#xff0c;支持获取域名…...

服务网格 SolarMesh v1.13 重磅发布

SolarMesh是行云创新推出的流量治理平台&#xff0c;它基于Istio&#xff0c;为部署在K8s集群上的应用提供全面的流量治理能力。 在之前的版本中&#xff0c;SolarMesh提供的能力有&#xff1a;流量视图&#xff0c;流量控制策略批量配置&#xff0c;API级别的流量数据采集和展…...

三大平台直播视频下载保存方法

终于解决了视频号下载的问题&#xff0c;2024年5月15日亲测可用。 而且免费。 教程第二部分&#xff0c;有本地电脑无法下载的解决方案。 第一部分&#xff1a;使用教程&#xff08;正常&#xff09; 第1步&#xff1a;下载安装包 下载迅雷网盘搜索&#xff1a;大海福利合集…...

OpenAI GPT-4o - 介绍

本文翻译整理自&#xff1a; Hello GPT-4o https://openai.com/index/hello-gpt-4o/ 文章目录 一、关于 GPT-4o二、模型能力三、能力探索四、模型评估1、文本评价2、音频 ASR 性能3、音频翻译性能4、M3Exam 零样本结果5、视觉理解评估6、语言 tokenization 六、模型安全性和局限…...

QTreeView学习 branch 虚线设置

1、方法一&#xff1a; #include <QStyleFactory> ui.treeView->setStyle(QStyleFactory::create("windows")); 2、方法二&#xff1a; QString strtyle2 R"( QTreeView::branch:has-siblings:!adjoins-item { border-image: url(:/TreeViewDe…...

C++ 日志库 log4cpp 编译、压测及其范例代码 [全流程手工实践]

文章目录 一、 log4cpp官网二、下载三、编译1.目录结构如下2.configure 编译3.cmake 编译 四、测试五、压测源码及结果1.运行环境信息2.压测源码3.压测结果 文章内容&#xff1a;包含了对其linux上的完整使用流程&#xff0c;下载、编译、安装、测试用例尝试、以及一份自己写好…...

python数据处理与分析入门-pandas使用(4)

往期文章&#xff1a; pandas使用1pandas使用2pandas使用3 pandas使用技巧 创建一个DF对象 # 首先创建一个时间序列 dates pd.date_range(20180101, periods6) print(dates)# 创建DataFrame对象&#xff0c;指定index和columns标签 df pd.DataFrame(np.random.randn(6,4), …...

操作系统-单片机进程状态问题(三态模型问题)

例题&#xff1a;在单处理机计算机系统中有1台打印机、1台扫描仪&#xff0c;系统采用先来先服务调度算法。假设系统中有进程P1、P2、P3、P4&#xff0c;其中P1为运行状态&#xff0c;P2为就绪状态&#xff0c;P3等待打印机&#xff0c;P4等待扫描仪。此时&#xff0c;若P1释放…...

Linux文件:重定向底层实现原理(输入重定向、输出重定向、追加重定向)

Linux文件&#xff1a;重定向底层实现原理&#xff08;输入重定向、输出重定向、追加重定向&#xff09; 前言一、文件描述符fd的分配规则二、输出重定向&#xff08;>&#xff09;三、输出重定向底层实现原理四、追加重定向&#xff08;>>&#xff09;五、输入重定向…...

波搜索算法(WSA)-2024年SCI新算法-公式原理详解与性能测评 Matlab代码免费获取

​ 声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 原理简介 一、初始化阶段 二、全…...

洛谷P1364 医院设置

P1364 医院设置 题目描述 设有一棵二叉树&#xff0c;如图&#xff1a; 其中&#xff0c;圈中的数字表示结点中居民的人口。圈边上数字表示结点编号&#xff0c;现在要求在某个结点上建立一个医院&#xff0c;使所有居民所走的路程之和为最小&#xff0c;同时约定&#xff0c…...

哈希表的理解和实现

目录 1. 哈希的概念 (是什么) 2. 实现哈希的两种方式 (哈希函数) 2.1. 直接定址法 2.2. 除留余数法 2.2.1. 哈希冲突 3. 补充知识 3.1. 负载因子 3.2. 线性探测和二次探测 4. 闭散列实现哈希表 (开放定址法) 4.1. 开放定址法的实现框架 4.2. Xq::hash_table::insert…...

分治算法(Divide-and-Conquer Algorithm)

分治算法&#xff08;Divide-and-Conquer Algorithm&#xff09;是一种重要的计算机科学和数学领域的通用问题解决策略。其基本思想是将一个复杂的大规模问题分割成若干个规模较小、结构与原问题相似但相对简单的子问题来处理。这些子问题相互独立&#xff0c;分别求解后再通过…...

Java项目:基于ssm框架实现的实验室耗材管理系统(B/S架构+源码+数据库+毕业论文+答辩PPT)

一、项目简介 本项目是一套基于ssm框架实现的实验室耗材管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 二、技术实现 jdk版本&#xff1a;1.8 …...

如何通过专业的二手机店erp优化手机商家运营!

在数字化浪潮席卷全球的大背景下&#xff0c;手机行业作为科技发展的前沿阵地&#xff0c;正经历着前所未有的变革。对于众多手机商家而言&#xff0c;如何在这场变革中抢占先机&#xff0c;实现数字化转型&#xff0c;成为了摆在他们面前的一大难题。幸运的是&#xff0c;途渡…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...