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 统一数据平台为西安交通大学云平台业务提供可靠的备份空间和强大的容灾能力,同时确保数据安全。西安交通大学(简称“西安交大”)是我国最早兴办、享誉海内外的著名高等学府,是教育部直属重点大学。学校现有兴庆、雁塔、曲江和…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
Linux 下 DMA 内存映射浅析
序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存,但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程,可以参考这篇文章,我觉得写的非常…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
