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

使字符串平衡的最少删除次数(简单动态规划)

给你一个字符串 s ,它仅包含字符 ab​​​​ 。

你可以删除 s 中任意数目的字符,使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ,且 s[i] = b 的同时 s[j]= a,此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

示例

input

s = "aababbab"

output

2

思路:
假设到i之前的字符串都是平衡的。对于当前位置i来说,
如果s[i] = a,那么处理方法能有两种

  • 将当前的字符a删除;
  • 保留当前的字符a,将i之前的所有b都删除。
  • 对于这两种操作取最小值,即为将s(1, i)变为平衡串的最小操作数。

如果s[i] = b,则不影响字符串平衡,所以不做处理。

在做完以上操作后,s(1, i)一定能成为一个平衡的串,我们也已知了将s(1, i)变为平衡串的最小操作数。所以对于i + 1也只需要做相同的操作即可。

代码:

class Solution {
public:int minimumDeletions(string s) {int countb = 0, ans = 0;for(int i = 0; i < s.size(); ++ i) {if(s[i] == 'a') {ans = min(ans + 1, countb);} else {countb ++;}}return ans;}
};

相关文章:

使字符串平衡的最少删除次数(简单动态规划)

给你一个字符串 s &#xff0c;它仅包含字符 a 和 b​​​​ 。 你可以删除 s 中任意数目的字符&#xff0c;使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j &#xff0c;且 s[i] b 的同时 s[j] a&#xff0c;此时认为 s 是 平衡 的。 请你返回使 s 平衡 的 最少 删除次…...

linux网络广播使用

广播使用的特殊的IP地址: 最后一位是255时的IP地址是给广播预留的IP地址, 如:192.168.1.255 UDP服务器在广播数据时,数据报使用的地址不是UDP服务器地址,而是广播地址 如:UDP服务器地址是:192.168.1.110 UDP服务器广播数据时使用地址是:192.168.1.255 UDP数据包发送给交换机…...

Kubernetes源码学习

kubernetes源码剖析 1.下载和编译源码 go 1.18.3 kubernetes 1.24.2 centos 7.9 进入目录$GOPATH/src/k8s.io/kubernetes&#xff0c;执行以下命令即可全量构建&#xff0c;并且构建结果只包含linux平台的&#xff1a; KUBE_BUILD_PLATFORMSlinux/amd64 make all GOFLAGS…...

筑基九层 —— 指针详解

目录 前言&#xff1a; 指针详解 前言&#xff1a; 1.CSDN由于我的排版不怎么好看&#xff0c;我的有道云笔记比较美观&#xff0c;请移步有道云笔记 2.修炼必备 1&#xff09;入门必备&#xff1a;VS2019社区版&#xff0c;下载地址&#xff1a;Visual Studio 较旧的下载 -…...

内存清理、动画制作、CPU检测等五款实用软件推荐

人类与99%的动物之间最大差别在于是否会运用工具&#xff0c;借助好的工具&#xff0c;能提升几倍的工作效率。 1.内存清理软件——MemReduct MemReduct是一款内存清理软件&#xff0c;现在越来越多的软件由于硬件的普遍发展&#xff0c;对内存的使用都开始肆无忌惮起来&…...

RocketMQ 5.0 学习笔记

1. 需求 背景&#xff1a;业务需要&#xff0c;平台将使用rocketMQ来实现消息的发送与消费&#xff0c;替代redis的消息功能。 需要在搭建好rocketMQ平台后&#xff0c;进行研究和验证。 技术&#xff1a;Springboot RocketMQ5.0 使用场景&#xff1a;签到活动&#xff0c…...

796.子矩阵的和

输入一个 n行 m列的整数矩阵&#xff0c;再输入 q个询问&#xff0c;每个询问包含四个整数 x1,y1,x2,y2&#xff0c;表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n&#xff0c;m&#xff0c;q。 接下来 n…...

【PySide6】信号(signal)和槽函数(slot),以及事件过滤器

说明 在PYQT中&#xff0c;父控件可以通过两种方式响应子控件的事件&#xff1a; 通过信号(signal)和槽函数(slot)机制连接子控件和父控件父控件可以通过设置eventFilter()方法来监听响应子控件的事件 一、信号(signal)和槽函数(slot) 示例 在PYQT中&#xff0c;每个组件都…...

canal admin管理端配置(二)

下载安装 下载地址&#xff1a; 下载解压即可 配置 修改canal.admin-1.1.5\conf\application.yml server:port: 8089 #端口根据是否冲突修改 spring:jackson:date-format: yyyy-MM-dd HH:mm:sstime-zone: GMT8spring.datasource:address: 192.0.16.12:3306#数据库ip和端口…...

Servlet 生命周期

Servlet的生命周期有四个阶段&#xff1a;加载并实例化、初始化、请求处理、销毁。主要涉及到的方法有init、service、doGet、doPost、destory等 加载并实例化 Servlet容器负责加载和实例化Servelt。当Servlet容器启动时&#xff0c;或者在容器检测到需要这个Servlet来响应第一…...

redis集群模式登陆

总结redis单机模式时&#xff0c;登陆redis的命令格式&#xff1a; ./redis-cli -h 地址 -p 端口redis集群模式时&#xff0c;登陆redis的命令格式&#xff1a; ./redis-cli -h 地址 -p 端口 -c举例1&#xff1a;redis单机模式下登陆rootubuntu:/usr/local/redis/redis-7.0.0/b…...

04-useMemo 、React.memo、useCallback

useMemo 、React.memo、useCallback 一、useMemo 基本用法 缓存数据&#xff0c;模拟 Vue 中的计算属性。 同样useMemo跟vue中component一样&#xff0c;也是有缓存的&#xff0c;会将结果缓存下来 import React, { useMemo, useState } from react;export default functio…...

windows下安装emqx Unable to load emulator DLL@if ===/ SET data_dir=“

1.报错内容 I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\bin>emqx start Unable to load emulator DLL (I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\erts-12.3.2.9\bin\beam.smp.dll) 此时不应有 SET。 I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\bin&…...

Redis常见问题(未完待续)

Redis常见问题Redis为什么快 &#xff1f;Redis为什么快 &#xff1f; 根据官方数据&#xff0c;Redis 的 QPS 可以达到约 100000&#xff08;每秒请求数&#xff09;&#xff1b; 基于内存 对于磁盘数据库来说&#xff0c;首先要将数据通过 IO 操作读取到内存里再读取&#x…...

2024秋招BAT核心算法 | 详解图论

图论入门与最短路径算法 图的基本概念 由节点和边组成的集合 图的一些概念&#xff1a; ①有向边&#xff08;有向图&#xff09;&#xff0c;无向边&#xff08;无向图&#xff09;&#xff0c;权值 ②节点&#xff08;度&#xff09;&#xff0c;对应无向图&#xff0c;…...

凝聚共识,锚定未来 | 第四届OpenI/O 启智开发者大会NLP大模型论坛成功举办!

2023年2月24日下午&#xff0c;第四届OpenI/O启智开发者大会NLP大模型分论坛在深圳人才研修院隆重举办。该论坛以“开源集智创新探索中文NLP大模型生态发展”为主题&#xff0c;众多业内人士和研发者在此共享NLP领域的前沿动态和研发经验&#xff0c;畅想中国NLP领域的发展前景…...

99.【Git】

Git(一)、什么是版本控制1.什么是版本控制2、常见的版本控制工具(二)、版本控制分类1、本地版本控制2、集中版本控制 SVN3、分布式版本控制 Git(三)、Git与SVN的主要区别1、Git历史(四)、Git下载与环境配置1.git下载2、启动Git(五)、常用的Linux命令1.Linux常用命令(六)、Git必…...

Linux驱动交叉编译把驱动文件放入开发板,以及printk函数打印级别

上一篇介绍了一个最简单的驱动程序和驱动程序大体结构&#xff0c;但那还是用本地编译只能在Ubuntu上运行&#xff0c;我们该怎么编译一个能加载到开发板上呢&#xff0c;就需要交叉编译&#xff0c;交叉编译通常都是在嵌入式开发中使用到的。 交叉编译 理解交叉编译前先了解…...

力扣(LeetCode)433. 最小基因变化(2023.03.07)

基因序列可以表示为一条由 8 个字符组成的字符串&#xff0c;其中每个字符都是 ‘A’、‘C’、‘G’ 和 ‘T’ 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如&#xff0c;“AACCGGTT”…...

网络基础(2)

目录1. 端口号2. 套接字socket3. 网络通信3.1 sockaddr与sockaddr_in3.2 接口服务端3.2.1 创建套接字&#xff0c;打开网络文件3.2.2 给该服务器绑定端口和ip&#xff08;特殊处理&#xff09;3.2.3 初始化相关服务器3.2.4 提供服务客户端3.2.5 绑定3.2.6 使用服务4. makefile实…...

跨语言沟通的革命性突破:FunASR语音翻译系统全解析

跨语言沟通的革命性突破&#xff1a;FunASR语音翻译系统全解析 你是否还在为国际会议中的语言障碍而烦恼&#xff1f;是否因跨国团队协作中的沟通不畅而效率低下&#xff1f;FunASR语音翻译系统将彻底改变这一现状&#xff0c;让跨语言交流如母语般自然流畅。读完本文&#xf…...

开发者社区生存手册:从潜水到活跃贡献者的5个关键步骤

开发者社区生存手册&#xff1a;从潜水到活跃贡献者的5个关键步骤 在数字时代的代码丛林里&#xff0c;开发者社区如同一个个闪烁着智慧火光的营地。你可能已经加入了几十个Slack频道&#xff0c;关注了无数技术大牛的Twitter&#xff0c;在GitHub上star了上百个仓库&#xff0…...

Axure RP 10实战:3分钟搞定Tab切换效果(附交互样式设置技巧)

Axure RP 10高级Tab切换效果&#xff1a;从基础实现到专业级交互设计 在当今快节奏的数字化产品设计领域&#xff0c;Tab切换作为最常见的用户界面元素之一&#xff0c;其交互体验的优劣直接影响用户对产品的第一印象。Axure RP 10作为行业领先的原型设计工具&#xff0c;提供了…...

IT 流程越来越完整,但管理反而变得更难了

在很多企业的 IT 管理过程中&#xff0c;一个非常明显的趋势是&#xff1a;流程在不断增加。 从最初的简单问题处理&#xff0c;到后来的事件管理、问题管理、变更管理&#xff0c;再到审批流程、发布流程&#xff0c;各类流程逐渐被建立起来。从管理角度看&#xff0c;这是一种…...

符号回归的工程化实践:基于深度学习的物理定律自动发现与工业部署

1. 符号回归&#xff1a;当深度学习遇见物理定律发现 第一次接触符号回归时&#xff0c;我被它的"反套路"特性惊艳到了——大多数深度学习模型都在努力变得更复杂&#xff0c;而它却在追求用最简单的数学公式解释世界。三年前我在化工厂做反应釜监控项目时&#xff0…...

抖音无水印视频批量下载器:从零开始的高效内容采集指南

抖音无水印视频批量下载器&#xff1a;从零开始的高效内容采集指南 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 你是否曾遇到过这样的困境&#xff1f;想要保存抖音上的精彩视频用于学习参考&#xff0c;…...

破局B站音频提取难题:BilibiliDown革新性解决方案全解析

破局B站音频提取难题&#xff1a;BilibiliDown革新性解决方案全解析 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors…...

League Toolkit:重新定义英雄联盟游戏体验的智能辅助工具

League Toolkit&#xff1a;重新定义英雄联盟游戏体验的智能辅助工具 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 价值定位&am…...

智能高效的离线OCR解决方案:Umi-OCR从基础到进阶的全方位应用指南

智能高效的离线OCR解决方案&#xff1a;Umi-OCR从基础到进阶的全方位应用指南 【免费下载链接】Umi-OCR Umi-OCR: 这是一个免费、开源、可批量处理的离线OCR软件&#xff0c;适用于Windows系统&#xff0c;支持截图OCR、批量OCR、二维码识别等功能。 项目地址: https://gitco…...

神经网络实战之dsp实现神经网络vad-1

vad神经网络有很多不同的实现&#xff0c;这里的神经网络是基于pytorch实现的&#xff0c;网络结构如下&#xff1a; class MiniVAD(nn.Module):def __init__(self, n_fft512):super().__init__()self.input48 #输入B T 48# 融合层self.fusion nn.Sequential(nn.Linear(self.i…...