LeetCode 828. 统计子串中的唯一字符

一开始想的是两次前缀和,发现自己蠢了

看了灵神的题解,类似于DP的思想

我们维护以每个字符串结尾的子字符串对答案的贡献,s[i]的贡献是多少?首先我们知道他需要自己单独一个串或者接在以s[i-1]结尾的那些字符串的后面,我们应当怎么操作?

我们发现那些以s[i-1]结尾的字符串可以分为三类:

记当前字符是c

1.出现过 c    1次

2.出现过 c    2次或者以上

3.没有出现过c

第一类接上c以后会让原来的那个答案-=1,第二类不影响,第三类+=1

所以我们只需要维护c上一次出现的位置,以及c上上次出现的位置就好了

然后你再用一下乘法原理  看看起点的种数就好了~~~~

class Solution {
public:
    int uniqueLetterString(string s) {
        int last0[100];
        int last1[100];
        memset(last0,-1,sizeof last0);
        memset(last1,-1,sizeof last1);


        int ans = 0,total=0;
        for(int i=0;i<s.size();i++){
            int t  = s[i]-'A';
            total += i+last1[t]-2*last0[t];
            ans+=total;
            last1[t] = last0[t];
            last0[t] = i;
        }

        return ans;

    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/362425.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【C++】类和对象(1)

上节我们学习了C入门的一些语法知识&#xff0c;这篇博客来学习类和this指针。 目录 面向过程和面向对象的初步认识 类的引入 类的定义 类的访问限定符及封装 访问限定符 封装 类的作用域 类的实例化 类对象大小 this指针 this指针特性 面向过程和面向对象的初步认识…

Transformer 自然语言处理(二)

原文&#xff1a;Natural Language Processing with Transformers 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第五章&#xff1a;文本生成 基于 Transformer 的语言模型最令人不安的特点之一是它们生成的文本几乎无法与人类写的文本区分开。一个著名的例子是 Ope…

Redis 管道技术——Pipeline

背景 面试官&#xff1a;Redis 管道技术pipeline用过吗&#xff1f;为什么要用&#xff1f;解决什么问题&#xff1f;使用过程中应该注意什么&#xff1f; 我&#xff1a;一键三连&#xff0c;内心gg了&#xff0c;没听说过&#xff0c;也不知道用来干什么的&#xff0c;我只能…

C++ //练习 3.10 编写一段程序,读入一个包含标点符号的字符串,将标点符号去除后输出字符串剩余的部分。

C Primer&#xff08;第5版&#xff09; 练习 3.10 练习 3.10 编写一段程序&#xff0c;读入一个包含标点符号的字符串&#xff0c;将标点符号去除后输出字符串剩余的部分。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 代码块 /**…

Pycharm 关闭/退出烦人的Pytest模式

Pycharm 遇到&#xff1a;Run Python tests in ***.py &#xff0c;但很多时候我们并不需要&#xff0c;真心烦人&#xff01; 如何解决: 1 打开File-Settings &#xff08;图片是新版界面&#xff0c;旧版同样操作&#xff09; 2 Tools 中的Python Integrated Tools 在Tes…

[office] excel2010双向条形图制作 #经验分享#微信

excel2010双向条形图制作 本教程为大家介绍一下excel2010中excel2010双向条形图制作方法。 1.选中工作区域 2.点击插入-->图表,选择条形图 3.为美观可将中间竖线可去掉 4.方法是选中竖线,右击-->删除 5.接下来将图例靠上,选中图例,右击-->设置图例格式-->图例选项…

独立按键控制LED(基于51单片机)

师从江科大 独立按键 轻触按键&#xff1a; 相当于是一种电子开关&#xff0c;按下开关接通&#xff0c;松开开关断开&#xff0c;实现原理是通过轻触按键内部的金属弹片受力弹动来实现接通好和断开 独立按键原理图&#xff1a; 注&#xff1a;没有按下独立按键是高电平&am…

对同一文件多次mmap

abstract 问&#xff1a;对同一个文件多次mmap&#xff0c;返回的地址相同吗? 答&#xff1a;不相同 code #ifdef __linux__#include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <sys/mman.h> …

1.D支撑线

从时间复杂度上来看&#xff0c;极点是O(n4)&#xff0c;极边是O(n3)&#xff0c;那么&#xff0c;还有没有可能使时间复杂度更小呢&#xff1f; 如上图所示将外部点X加入到原凸包&#xff0c;&#xff08;即S黄Vt蓝V所在的凸包&#xff09;那么可以观察到&#xff0c;将会组成…

【Java程序设计】【C00205】基于(JavaWeb+SSM)的商场停车服务管理系统(论文+PPT)

基于&#xff08;JavaWebSSM&#xff09;的商场停车服务管理系统&#xff08;论文PPT&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于ssm的商场停车服务管理系统 本系统分为管理员和用户2个功能模块。 管理员&#xff1a;管理员进入主页面&…

网络协议与攻击模拟_12DNS协议及Windows部署DNS服务器

1、了解域名的结构 2、DNS查询过程 3、Windwos server部署DNS服务器 4、分析流量 实施DNS欺骗 再分析 一、DNS域名系统 1、DNS简介 DNS&#xff08;Domain Name system&#xff09;域名系统&#xff0c;作为将域名的IP地址的相互映射关系存放在一个分布式的数据库&#xff0c…

二分查找-迭代法

Go 算法 每天5道&#xff0c;开心快乐每一天 一点都不开心 哈哈哈哈哈哈 -2.1 day 1 1.22&#xff08;1.23 1.25 1.29&#xff09; 1.23 已复习 704. 二分查找 力扣题目链接 //左闭右开 func search(nums []int, target int) int { right : len(nums) left : 0; for le…

6个AI写作工具,让你的文字变得生动有力

写作是一项需要耐心和技巧的任务&#xff0c;对于许多人来说&#xff0c;写作可能是一项困难的挑战。然而&#xff0c;随着人工智能的发展&#xff0c;AI智能写作软件逐渐崭露头角&#xff0c;为我们提供了更加便捷和高效的写作体验。在本文中&#xff0c;我们将介绍几款好用的…

算法练习01——哈希部分双指针

目录 1. 两数之和(*)242. 有效的字母异位词(easy)49. 字母异位词分组(*)349. 两个数组的交集202. 快乐数(1.使用Set存哈希&#xff0c;2.快慢指针)454. 四数相加 II383. 赎金信15. 三数之和*(双指针)18. 四数之和*(双指针)128. 最长连续序列 1. 两数之和(*) https://leetcode.…

边缘计算网关在智能制造中有哪些应用?-天拓四方

在智能制造和工业生产环境中&#xff0c;数据已经成为新的生产要素&#xff0c;工业生产对实时性、灵活性和智能化也提出了更高的要求。而在这个过程中&#xff0c;边缘计算网关发挥着不可或缺的作用。它作为设备层与网络层之间的关键桥梁&#xff0c;确保了数据的实时、高效处…

STM32F407移植OpenHarmony笔记6

继上一篇笔记&#xff0c;编译好STM32的裸机程序&#xff0c;能点亮LED灯了。 下一步就是启动liteos_m内核了。 不过为了更好的调试代码&#xff0c;需要先把printf重定向到串口&#xff0c;基于gcc的printf重定向和Keil不一样。 直接新建printf.c&#xff0c;在里面重写printf…

基于 NOVATEK NT98530 Multiview Stitching 应用解决方案

感测技术近来于影像监控系统应用有了进一步的发展&#xff0c;多镜头的应用也与日俱增&#xff0c;如 AI 视觉感测会议相机&#xff0c;能满足远端多人聚会、远距教育训练的多元需求等&#xff0c;相关应用层面广泛涵盖了在生活中所面对的各种场景&#xff0c;带动更加可观的潜…

【安装指南】nodejs下载、安装与配置详细教程

目录 &#x1f33c;一、概述 &#x1f340;二、下载node.js &#x1f337;三、安装node.js &#x1f341;四、配置node.js &#x1f33c;一、概述 Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行时&#xff0c;用于构建可扩展的网络应用程序。Node.js 使用事件驱动、…

各品牌主板快速启动热键对照表及CMOS进入方法

各品牌主板快速启动热键对照表 主板品牌 启动按键 笔记本品牌 启动按键 主机品牌 启动按键 华硕主板 F8 联想笔记本 F12 联想台式机 F12 技嘉主板 F12 宏碁笔记本 F12 惠普台式机 F12 微星主板 F11 华硕笔记本 ESC 宏碁台式机 F12 梅捷主板 F9 惠普笔…

机器学习数学基础

机器学习基础 1、标量、向量、矩阵、张量2、概率函数、概率分布、概率密度、分布函数3、向量的线性相关性4、最大似然估计5、正态分布(高斯分布)6、向量的外积(叉积)7、向量的内积(点积)8、超平面(H)1、标量、向量、矩阵、张量 标量、向量、矩阵和张量是线性代数中不同…