Leetcode.828 统计子串中的唯一字符
题目链接
Leetcode.828 统计子串中的唯一字符 Rating : 2034
题目描述
我们定义了一个函数 countUniqueChars(s)来统计字符串 s中的唯一字符,并返回唯一字符的个数。
例如:s = "LEETCODE",则其中 "L", "T","C","O","D"都是唯一字符,因为它们只出现一次,所以 countUniqueChars(s) = 5。
本题将会给你一个字符串 s,我们需要返回 countUniqueChars(t)的总和,其中 t是 s的子字符串。输入用例保证返回值为 32 位整数。
注意,某些子字符串可能是重复的,但你统计时也必须算上这些重复的子字符串(也就是说,你必须统计 s的所有子字符串中的唯一字符)。
示例 1:
输入: s = “ABC”
输出: 10
解释: 所有可能的子串为:“A”,“B”,“C”,“AB”,“BC” 和 “ABC”。
其中,每一个子串都由独特字符构成。
所以其长度总和为:1 + 1 + 1 + 2 + 2 + 3 = 10
示例 2:
输入: s = “ABA”
输出: 8
解释: 除了 countUniqueChars(“ABA”) = 1 之外,其余与示例 1 相同。
示例 3:
输入:s = “LEETCODE”
输出:92
提示:
- 1<=s.length<=1051 <= s.length <= 10^51<=s.length<=105
s只包含大写英文字符
分析:动态规划
对于 s的一个子串 s[0~i-1],我们分别计算添加 s[i],会增加多少唯一字符a和 减少多少唯一字符b,a-b就是
此次 s[0~i-1]添加 s[i]的贡献。我们只需要对 s[0 ~ n - 1]用一样的逻辑即可。
我们下面讨论,把 A添加到 BCADEAFG的贡献。

A本身 ; 把A添加到G;把A添加到FG;都会增加1个唯一字符。- 把
A添加到AFG;把A添加到EAFG;把A添加到DEAFG; 都会减少1个唯一字符。 - 把
A添加到ADEAFG;把CADEAFG添加到BCADEAFG;把A添加到DEAFG; 都不会发生变化。
我们发现,当添加一个字符 s[i]时:
- 增加的贡献:i -
s[i]上一次出现的位置 - 减少的贡献:
s[i]上一次出现的位置 -s[i]上上一次出现的位置
我们用 pre记录 s[i]上一次出现的位置,用 prepre记录 s[i]上上一次出现的位置。
添加 s[i]后总的变化量为(i - pre[s[i]]) - (pre[s[i]] - prepre[s[i]])
我们每次都用 total维护 以 s[i]结尾的 唯一字符数量。
每次都添加到答案 ans上。
时间复杂度: O(n)O(n)O(n)
C++代码:
class Solution {
public:int uniqueLetterString(string s) {int n = s.size();int pre[26],prepre[26];memset(pre,-1,sizeof pre);memset(prepre,-1,sizeof prepre);int ans = 0 , total = 0;;for(int i = 0;i < n;i++){int t = s[i] - 'A';total += i - 2 * pre[t] + prepre[t];ans += total;prepre[t] = pre[t];pre[t] = i;}return ans;}
};
Java代码:
class Solution {public int uniqueLetterString(String s) {int n = s.length();int[] pre = new int[26];int[] prepre = new int[26];Arrays.fill(pre,-1);Arrays.fill(prepre,-1);int ans = 0;int total = 0;for(int i = 0;i < n;i++){int t = s.charAt(i) - 'A';total += (i - pre[t]) - (pre[t] - prepre[t]);ans += total;prepre[t] = pre[t];pre[t] = i;}return ans;}
}相关文章:
Leetcode.828 统计子串中的唯一字符
题目链接 Leetcode.828 统计子串中的唯一字符 Rating : 2034 题目描述 我们定义了一个函数 countUniqueChars(s)来统计字符串 s中的唯一字符,并返回唯一字符的个数。 例如:s "LEETCODE",则其中 "L", "…...
Hibernate 相关特性
1. Hibernate一般使用hql进行查询,但也有sql执行的方法 Native sql 查询,。需要注意的是,使用Native SQL查询可能会破坏Hibernate的缓存机制,并可能导致性能问题 String sql "SELECT * FROM users WHERE age > :age"; Query …...
【研究生学术英语读写教程翻译 中国科学院大学Unit1-Unit8】
Unit1 Descartes Was Wrong 笛卡尔错了:“他人在,故我在” Unit2 Are we ready for the next volcanic catastrophe?我们准备好应对下一次火山灾难了吗? Unit3 Theorists,experimentalists and the bias in popular physics理论家,实验家和大众物理学的偏见 unit4 Magic Nu…...
ListView 控件的使用
第一步:找到ListView的控件通过findViewById 找到ListView的控件 ListView listView findViewById(R.id.listView);第二步:创建Bean类 得到set和get的方法解析获取的数据创建Bean类 得到set和get的方法public class Bean {String nanm""; pub…...
域控制器搭建以及成员加入
需要iso:windows server 2016软件使用:vmwarewindows server 2016系统搭建自己选iso,一直下一步就可以安装完成。(记得要设置密码)(密码要求大小写字母数字符号)等待就能安装完成。安装和配置Ac…...
利用 MLP(多层感知器)和 RBF(径向基函数)神经网络解决的近似和分类示例问题(Matlab代码实现)
目录 💥1 概述 📚2 运行结果 🎉3 参考文献 👨💻4 Matlab代码 💥1 概述 1、径向基神经网络 径向基函数网络是由三层构成的前向网络:第一层为输入层,节点个数的能与输入的维数&…...
进阶C语言——数据的存储【详解】
文章目录1. 数据类型介绍1.1 类型的基本归类2. 整形在内存中的存储2.1 原码、反码、补码2.2 大小端介绍2.3 练习3. 浮点型在内存中的存储3.1 一个例子3.2 浮点数存储的规则1. 数据类型介绍 前面我们已经学习了基本的内置类型: char //字符数据类型 short //短整型 …...
KUKA机器人修改机器人名称和IP地址的具体方法示例
KUKA机器人修改机器人名称和IP地址的具体方法示例 修改机器人名称 如下图所示,首先切换用户组到管理员,输入默认密码:kuka, 如下图所示,点击菜单键—投入运行—机器人数据, 如下图所示,此时可以看到机器人的名称为rrr445, 如下图所示,修改之后,点击左侧的“”…...
【数据分析师求职面试指南】必备基础知识整理
数据分析师基础知识统计 数据分析知识基础概念随机变量常用特征正态分布与大数定律、中心极限定律假设检验模型、数据挖掘知识常用概念数据集划分欠拟合过拟合模型分类方法常见模型介绍线性回归模型:逻辑回归模型决策树模型随机森林模型Boosting模型XGBoost模型模型…...
《开关电源宝典 降压电路(BUCK)的原理与应用》
嗨,硬件攻城狮或电源工程师同行们,我想写本专门解析BUCK电源电路的书籍,以下是“前言”内容的部分摘录以及当前的目录,当前已经完成22万多字500多页了,即使如此,离真正出版书籍,还有很长的路要走…...
R语言基础(一):注释、变量
R语言用于统计分析和绘制图表等操作。不同于Java等其它语言,R用于统计,而不是做一个网站或者软件,所以R的一些开发习惯和其它语言不同。如果你是一个编程小白,那么可以放心大胆的学。如果你是一个有编程基础的人,那么需…...
Java 集合进阶(二)
文章目录一、Set1. 概述2. 哈希值3. 元素唯一性4. 哈希表5. 遍历学生对象6. LinkedHashSet7. TreeSet7.1 自然排序7.2 比较器排序8. 不重复的随机数二、泛型1. 概述2. 泛型类3. 泛型方法4. 泛型接口5. 类型通配符6. 可变参数7. 可变参数的使用一、Set 1. 概述 Set 集合特点&am…...
小孩用什么样的台灯比较好?2023眼科医生青睐的儿童台灯推荐
小孩子属于眼睛比较脆弱的人群,所以选购护眼台灯时,选光线温和的比较好,而且调光、显色效果、色温、防蓝光等方面也要出色,否则容易导致孩子近视。 1、调光。台灯首先是照度高,国AA级+大功率发光࿰…...
Ubuntu c++ MySQL数据库操作
mysql安装sudo apt-get install updatesudo apt-get install mysql-server libmysqlclient-dev mysql-workbenchmysql启动/重启/停止sudo service mysql start/restart/stop登录mysql命令:mysql -uroot -p错误异常:解决办法:修改mysqld.cnf配…...
C++11:lambda表达式
文章目录1. 概念2. 语法3. 示例示例1示例2示例3示例44. 捕捉方式基本方式隐式和混合补充5. 传递lambda表达式示例6. 原理7. 内联属性1. 概念 lambda表达式实际上是一个匿名类的成员函数,该类由编译器为lambda创建,该函数被隐式地定义为内联。因此&#…...
【Android -- 开源库】表格 SmartTable 的基本使用
介绍 1. 功能 快速配置自动生成表格;自动计算表格宽高;表格列标题组合;表格固定左序列、顶部序列、第一行、列标题、统计行;自动统计,排序(自定义统计规则);表格图文、序列号、列标…...
自动化测试实战篇(9),jmeter常用断言方法,一文搞懂9种测试字段与JSON断言
Jmeter常用的断言主要有,JSON断言和响应断言这两种方式。 断言主要就是帮助帮助人工进行快速接口信息验证避免繁杂的重复的人工去验证数据 第一种响应断言Apply to:表示应用范围测试字段:针对响应数据进行不同的匹配响应文本响应代码响应信息…...
vue-virtual-scroll-list虚拟列表
当DOM中渲染的列表数据过多时,页面会非常卡顿,非常占用浏览器内存。可以使用虚拟列表来解决这个问题,即使有成百上千条数据,页面DOM元素始终控制在指定数量。 一、参考文档 https://www.npmjs.com/package/vue-virtual-scroll-li…...
C++学习笔记(以供复习查阅)
视频链接 代码讲义 提取密码: 62bb 文章目录1、C基础1.1 C初识(1) 第一个C程序(2)注释(3)变量(4)常量(5)关键字(6)标识符命名规则1.2 …...
备份时间缩短为原来 1/4,西安交大云数据中心的软件定义存储实践
XEDP 统一数据平台为西安交通大学云平台业务提供可靠的备份空间和强大的容灾能力,同时确保数据安全。西安交通大学(简称“西安交大”)是我国最早兴办、享誉海内外的著名高等学府,是教育部直属重点大学。学校现有兴庆、雁塔、曲江和…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
