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

leetcode 2606.找到最大开销的子字符串

思路:dp

这道题是不是很像最大子数组和那道题呢?从这里我们其实能看出来一类题的蹊跷规律来:

也就是说,在涉及到子字符串,子数组这样的字眼的时候,并且有最值问题,我们可以基本上确定是动态规划,其次,这类动态规划我们可以设dp数组为以....为尾的含义。

子序列等不连续的也可以这样设dp数组,只不过会多一维循环。

这道题的子数组那道题一样,只不过这里需要做一些改动,那就是我们需要知道这里的价值是多少。题目中给了一部分,其他部分我们也可以自己用循环求。但是这种字符串和数值之间的映射我们应该怎么办?

说到映射,我们一定会想到用一个数据结构,那就是哈希表。OK,这样的话就轻松了。我们直接按照题目要求映射哈希表就行了,然后再对数组进行dp数组转移。

注意:我们最后求出来的结果并不是dp到最后的下标对应的值,而是其中dp数组最大值,因为这里需要求最大子字符串价值,这一点不要忽略,在比较的时候我们的变量要注意从dp[0]开始赋值,然后依次比较,dp[0]我们一开始就直接赋值为一开始所给字符的价值就行了。

上代码:

class Solution {
public:int maximumCostSubstring(string s, string chars, vector<int>& vals) {map<char,int>m;char c='a';for(int i=1;i<=26;i++){m[c++]=i;}for(int i=0;i<chars.size();i++){m[chars[i]]=vals[i];}vector<int>dp(s.size()+1,0);dp[0]=m[s[0]];int res=dp[0];for(int i=1;i<s.size();i++){if(dp[i-1]<=0)dp[i]=m[s[i]];elsedp[i]=dp[i-1]+m[s[i]];res=max(dp[i],res);}return res>0?res:0;}
};

相关文章:

leetcode 2606.找到最大开销的子字符串

思路&#xff1a;dp 这道题是不是很像最大子数组和那道题呢?从这里我们其实能看出来一类题的蹊跷规律来&#xff1a; 也就是说&#xff0c;在涉及到子字符串&#xff0c;子数组这样的字眼的时候&#xff0c;并且有最值问题&#xff0c;我们可以基本上确定是动态规划&#xf…...

超标量处理器设计:重排序缓存(ROB)

★超标量处理器的很多地方用到了重排序缓存&#xff0c;但是我对它不是很了解&#xff0c;所以我整理一下重排序缓存的知识点。 重排序缓存(ROB)在确保乱序执行的指令能够正确地完成和提交(Commit)&#xff0c;也可以用来寄存器重命名。 ROB是一个先进先出的表&#xff0c;每个…...

nginx常用内置变量

名称说明$arg_name请求中的name参数$args请求中的参数$content_lengthhttp请求信息里的"Content-Length"$content_type请求信息里的"Content-Type"$host请求信息中的"Host"&#xff0c;如果请求中没有Host&#xff0c;则等于设置的服务器名$host…...

MySQL技能树学习——数据库组成

数据库组成&#xff1a; 数据库是一个组织和存储数据的系统&#xff0c;它由多个组件组成&#xff0c;这些组件共同工作以确保数据的安全、可靠和高效的存储和访问。数据库的主要组成部分包括&#xff1a; 数据库管理系统&#xff08;DBMS&#xff09;&#xff1a; 数据库管理系…...

OpenCV入门1:Python基础编程

目录 环境配置 Python基础语法 import 与 from...import If ... Else 语句 While 循环 For 循环 集合数据类型 列表 函数 类和对象 环境配置 详情请参考&#xff1a;Pycharm环境配置完整教程 Python基础语法 import 与 from...import 在 python 用 import 或者 f…...

C++ Builder XE EnumWindowsProc遍历所有窗口的名称

BOOL CALLBACK EnumWindowsProc(HWND hwnd, LPARAM lParam) { // 这里可以添加你的处理逻辑 // 例如&#xff0c;将句柄添加到列表中或者其他操作 // 这里我们仅仅输出到调试窗口 OutputDebugString(L"枚举窗口句柄: "); char windowHandle[10];…...

Qt QInputDialog详解

1.简介 QInputDialog是一个对话框类&#xff0c;用于从用户那里获取一个单一的值。这个值可以是字符串、数字、或者一个列表中的选项。QInputDialog提供了一个方便的方式来快速创建一个输入对话框&#xff0c;无需自己从头开始构建。 QInputDialog支持多种输入类型&#xff1…...

最新盘点!2024年20大好用的项目管理软件(后续持续更新)

项目管理软件&#xff0c;作为一种高效的项目管理工具&#xff0c;正逐渐成为企业运营中不可或缺的一环。它包括任务分配、进度跟踪、团队协作、风险预测等多个方面&#xff0c;为企业提供了全方位的项目管理解决方案。 在如今竞争激烈的市场环境下&#xff0c;企业要想在有限…...

Linux:配置客户端默认autofs服务

Linux&#xff1a;配置客户端autofs服务 安装autofs软件 [rootserver200 ~]# dnf install autofs -y开启并设置开机自启autofs服务 [rootserver200 ~]# systemctl enable --now autofs访问默认autofs挂载机制 当autofs启动后系统默认会在/net目录中访问nfs服务器 [rootser…...

Kotlin版本的Gradle全局配置init.gradle.kts及参考文档

工欲善其事&#xff0c; 必先利其器。 文章目录 init.gradle.ktsGroovy版本的init.gradle其他有用的settings.gradle.ktskotlin 与 compose 版本对应关系agp 与 gradle 版本对应关系gradle下载器 直接在.gradle文件夹下添加文件init.gradle / init.gradle.kt for kotlin dsl. …...

react18【实战】tab切换,纯前端列表排序(含 lodash 和 classnames 的安装和使用)

技术要点 动态样式 className{tabItem ${currentType item.value && "active"}}安装 lodash npm i --save lodash使用 lodash 对对象数组排序&#xff08;不会改变源数组&#xff09; _.orderBy(dataList, "readNum", "desc")src\De…...

C++学习第二十七课:C++ 输入输出流详解:从基础到高级应用

在 C 中&#xff0c;流&#xff08;stream&#xff09;是一种用于实现输入输出操作的抽象概念。流可以看作是字节的流动&#xff0c;这些字节可以从一个地方流向另一个地方&#xff0c;例如从键盘输入到程序中&#xff0c;或者从程序输出到屏幕。C 提供了一套完整的流库来处理各…...

【Unity AR开发系列】介绍如何使用这个支持热更的AR开发插件,快速地开发AR应用

预告 Unity开发AR系列 本专栏将介绍如何使用这个支持热更的AR开发插件&#xff0c;快速地开发AR应用。 更新 二、使用插件一键安装HybridCLR和ARCore 三、配置带HybridCLR的ARCore开发环境...

Nginx - 配置文件结构(一)

安装Nginx 以 Ubuntu 为例&#xff0c;安装命令为 sudo apt install nginx常用指令 # 检查配置文件是否有问题 nginx -t# 热加载配置文件 nginx -s reload# 等待处理完当前请求并退出 nginx -s quit# 快速退出 nginx -s stop目录结构 nginx 默认安装位置一般在 /etc/nginx …...

暗区突围进不去/游戏无法启动/掉帧卡顿/报错的解决方法

暗区突围是一款高拟真硬核射击手游&#xff0c;打造了全新的沉浸式暗区战局体验&#xff0c;发行商是腾讯公司。这个游戏名词虽然看起来有些陌生&#xff0c;但其本身的玩法内核毫无疑问的是&#xff0c;这款游戏在画面质量和枪械操作方面&#xff0c;都是手游市场上同类游戏中…...

基于FPGA的视频矩阵 视频拼接 无缝切换解决方案

视频矩阵 视频矩阵 视频拼接 无缝切换 1. 最大支持144路HDMI视频输入&#xff0c;最大支持144路路HDMI输出&#xff0c;完全交叉切换。 2. 与包括1080p/60的所有HDTV分辨率和高达1920*1200的PC的分辨率兼容&#xff1b; 3. 支持HDMI 1.3a、HDCP 1.3、HDCP 1.4、以及DVI 1.0协…...

LeetCode 513.找树左下角的值

LeetCode 513.找树左下角的值 1、题目 题目链接&#xff1a;513. 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1示例 2: 输入: [1,2,3,4,null…...

redis分片java实践、redis哨兵机制实现、redis集群搭建

redis分片java实践 linux安装redishttps://mp.csdn.net/mp_blog/creation/editor/134864302复制redis.conf配置文件成redis1.conf、redis2.conf、redis3.conf 修改redis的端口信息和存pid文件的路径。存pid文件的路径只要不同就行了&#xff0c;没什么特别要求。 指定配置文件…...

2024年四千价位段最具统治力的投影仪,坚果N1S 4K: 4K+三色激光=下一代4K

更高的亮度与分辨率、更强的对比度、更广的色域、更低的价格&#xff0c;家用智能投影企业在性能和价格上加速内卷。作为该领域的龙头和“卷王之王”&#xff0c;坚果投影率先将激光投影仪的价格拉入万元内&#xff0c;近期其又祭出一把杀手锏——坚果N1S 4K。该产品是首款4000…...

MySQL8.3升级踩坑记录

之前用的mysql5.7&#xff0c;目前被省公司发现有漏洞&#xff0c;需要升级mysql8.3&#xff0c;无奈只好升级&#xff0c;记录下踩坑经过 1、安装完以后设置环境变量&#xff0c;网上操作一大堆&#xff0c;以便于方便使用client 2、双击client 登录&#xff0c;开启远程访问…...

别再死记硬背MIPI状态转换图了!用Python脚本模拟单向/双向Data Lane状态机

用Python脚本动态解析MIPI状态机&#xff1a;从理论到实践的可视化之旅 每次打开MIPI协议文档看到那些密密麻麻的状态转换图&#xff0c;是不是感觉像在解读外星密码&#xff1f;作为嵌入式开发者&#xff0c;我们需要的不是死记硬背那些LP-11→LP-01的箭头指向&#xff0c;而…...

3步掌握WindowResizer:免费强制调整任意窗口大小的终极方案

3步掌握WindowResizer&#xff1a;免费强制调整任意窗口大小的终极方案 【免费下载链接】WindowResizer 一个可以强制调整应用程序窗口大小的工具 项目地址: https://gitcode.com/gh_mirrors/wi/WindowResizer 还在为那些顽固的窗口尺寸而烦恼吗&#xff1f;无论你面对的…...

ComfyUI效果实测:多插件加持下的高清AI绘画生成对比

ComfyUI效果实测&#xff1a;多插件加持下的高清AI绘画生成对比 1. 引言&#xff1a;为什么选择ComfyUI 在AI绘画领域&#xff0c;ComfyUI以其独特的工作流设计方式脱颖而出。与传统的AI绘画工具不同&#xff0c;ComfyUI采用节点式工作流设计&#xff0c;让用户可以像搭积木一…...

大数据领域 OLAP 技术的发展趋势展望

大数据领域OLAP技术的发展趋势展望 关键词:OLAP、大数据分析、实时决策、云原生、AI融合 摘要:本文从超市老板的"销售密码"故事出发,用通俗易懂的语言拆解OLAP(在线分析处理)技术的核心逻辑,结合当前大数据技术演进趋势,深入探讨OLAP在实时化、云原生化、AI融…...

RWKV7-1.5B-g1a参数调优教程:temperature=0.1稳输出 vs 0.8活生成,效果差异实测

RWKV7-1.5B-g1a参数调优教程&#xff1a;temperature0.1稳输出 vs 0.8活生成&#xff0c;效果差异实测 1. 模型简介 rwkv7-1.5B-g1a是基于RWKV-7架构的多语言文本生成模型&#xff0c;特别适合以下场景&#xff1a; 基础问答文案续写简短总结轻量中文对话 这个1.5B参数的版…...

Phi-4-mini-reasoning效果实测:在高考数学压轴题上的分步推导与结论匹配度

Phi-4-mini-reasoning效果实测&#xff1a;在高考数学压轴题上的分步推导与结论匹配度 1. 模型能力概述 Phi-4-mini-reasoning是一款专注于推理任务的文本生成模型&#xff0c;特别擅长处理需要多步逻辑推导的数学题和逻辑题。与通用聊天模型不同&#xff0c;它被设计为直接接…...

Graphormer部署案例:中小企业AI药物研发团队低成本GPU算力部署方案

Graphormer部署案例&#xff1a;中小企业AI药物研发团队低成本GPU算力部署方案 1. 项目背景与价值 在药物研发领域&#xff0c;分子属性预测是核心环节之一。传统实验方法成本高昂且周期漫长&#xff0c;而Graphormer作为基于纯Transformer架构的图神经网络&#xff0c;为这一…...

告别底噪和电流声:DIY蓝牙音箱的音频电路避坑指南(从TPA2019布线到电源滤波)

蓝牙音箱DIY进阶指南&#xff1a;从电路设计到音质优化的全流程解析 在电子DIY领域&#xff0c;蓝牙音箱制作看似简单&#xff0c;但要实现专业级的音质表现却需要跨越诸多技术门槛。许多爱好者完成基础组装后&#xff0c;常会遇到底噪明显、高频失真或低频浑浊等问题——这往往…...

PyTorch 2.8镜像实际效果:torch.compile+FlashAttention-2双优化下的吞吐量提升对比

PyTorch 2.8镜像实际效果&#xff1a;torch.compileFlashAttention-2双优化下的吞吐量提升对比 1. 镜像环境与技术亮点 PyTorch 2.8深度学习镜像为开发者提供了一个开箱即用的高性能计算环境。基于RTX 4090D 24GB显卡和CUDA 12.4的深度优化组合&#xff0c;这个镜像特别适合需…...

Word文档自动更新日期技巧

设置Word文档自动显示当天日期打开Word文档后&#xff0c;可以通过插入日期字段实现每次打开时自动更新为当天日期。方法1&#xff1a;使用日期字段在Word文档中定位光标到需要显示日期的位置。点击菜单栏"插入"→"文本"→"日期和时间"。在弹出的…...