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

【贡献法】2262. 字符串的总引力

本文涉及知识点

贡献法

LeetCode2262. 字符串的总引力

字符串的 引力 定义为:字符串中 不同 字符的数量。
例如,“abbca” 的引力为 3 ,因为其中有 3 个不同字符 ‘a’、‘b’ 和 ‘c’ 。
给你一个字符串 s ,返回 其所有子字符串的总引力 。
子字符串 定义为:字符串中的一个连续字符序列。

示例 1:
输入:s = “abbca”
输出:28
解释:“abbca” 的子字符串有:

  • 长度为 1 的子字符串:“a”、“b”、“b”、“c”、“a” 的引力分别为 1、1、1、1、1,总和为 5 。
  • 长度为 2 的子字符串:“ab”、“bb”、“bc”、“ca” 的引力分别为 2、1、2、2 ,总和为 7 。
  • 长度为 3 的子字符串:“abb”、“bbc”、“bca” 的引力分别为 2、2、3 ,总和为 7 。
  • 长度为 4 的子字符串:“abbc”、“bbca” 的引力分别为 3、3 ,总和为 6 。
  • 长度为 5 的子字符串:“abbca” 的引力为 3 ,总和为 3 。
    引力总和为 5 + 7 + 7 + 6 + 3 = 28 。
    示例 2:
    输入:s = “code”
    输出:20
    解释:“code” 的子字符串有:
  • 长度为 1 的子字符串:“c”、“o”、“d”、“e” 的引力分别为 1、1、1、1 ,总和为 4 。
  • 长度为 2 的子字符串:“co”、“od”、“de” 的引力分别为 2、2、2 ,总和为 6 。
  • 长度为 3 的子字符串:“cod”、“ode” 的引力分别为 3、3 ,总和为 6 。
  • 长度为 4 的子字符串:“code” 的引力为 4 ,总和为 4 。
    引力总和为 4 + 6 + 6 + 4 = 20 。
    提示:
    1 <= s.length <= 105
    s 由小写英文字母组成

贡献法

n = s.length
累计s[i]的对各子串贡献的引力。
s[left…r] 如果有相等的字符,则引力算到第一个字符上,下标最小字符。
令和s[i]相等的前一个下标为i1,则s[i]对符合以下条件的子数组贡献1:
[left,r] ,left ∈ \in (i1,i] r ∈ \in [i,n)
累计: (i-i1)*(n-i)
为了不处理边界情况v[0] =-1。

代码

核心代码

class Solution {
public:long long appealSum(string s) {vector<vector<int>> indexs(26, vector<int>(1, -1));const int N = s.length();for (int i = 0; i < N; i++) {indexs[s[i] - 'a'].emplace_back(i);}long long llRet = 0;for (const auto& v : indexs) {for (int i = 1; i < v.size(); i++) {llRet += (long long)(v[i] - v[i - 1]) * (N - v[i]);}}return llRet;}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{	string s;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){s = "c";auto res = Solution().appealSum(s);AssertEx(1LL, res);}TEST_METHOD(TestMethod03){s = "cc";auto res = Solution().appealSum(s);AssertEx(3LL, res);}TEST_METHOD(TestMethod01){s = "abbca";auto res = Solution().appealSum(s);AssertEx(28LL, res);}TEST_METHOD(TestMethod02){s = "code";auto res = Solution().appealSum(s);AssertEx(20LL, res);}};
}

扩展阅读

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:

【贡献法】2262. 字符串的总引力

本文涉及知识点 贡献法 LeetCode2262. 字符串的总引力 字符串的 引力 定义为&#xff1a;字符串中 不同 字符的数量。 例如&#xff0c;“abbca” 的引力为 3 &#xff0c;因为其中有 3 个不同字符 ‘a’、‘b’ 和 ‘c’ 。 给你一个字符串 s &#xff0c;返回 其所有子字符…...

C#基于SkiaSharp实现印章管理(3)

本系列第一篇文章中创建的基本框架限定了印章形状为矩形&#xff0c;但常用的印章有方形、圆形等多种形状&#xff0c;本文调整程序以支持定义并显示矩形、圆角矩形、圆形、椭圆等4种形式的印章背景形状。   定义印章背景形状枚举类型&#xff0c;矩形、圆形、椭圆相关的尺寸…...

如何理解泛型的编译期检查

既然说类型变量会在编译的时候擦除掉&#xff0c;那为什么我们往 ArrayList 创建的对象中添加整数会报错呢&#xff1f;不是说泛型变量String会在编译的时候变为Object类型吗&#xff1f;为什么不能存别的类型呢&#xff1f;既然类型擦除了&#xff0c;如何保证我们只能使用泛型…...

计算机组成原理:海明校验

在上图中&#xff0c;对绿色的7比特数据进行海明校验&#xff0c;需要添加紫色的4比特校验位&#xff0c;总共是蓝色的11比特。紫色的校验位pi分布于蓝色的hi的1, 2, 4, 8, 16, 32, 64位&#xff0c;是2i-1位。绿色的数据位bi分布于剩下的位。 在下图中&#xff0c;b1位于h3&a…...

信息学奥赛初赛天天练-39-CSP-J2021基础题-哈夫曼树、哈夫曼编码、贪心算法、满二叉树、完全二叉树、前中后缀表达式转换

PDF文档公众号回复关键字:20240629 2022 CSP-J 选择题 单项选择题&#xff08;共15题&#xff0c;每题2分&#xff0c;共计30分&#xff1a;每题有且仅有一个正确选项&#xff09; 5.对于入栈顺序为a,b,c,d,e的序列&#xff0c;下列( )不合法的出栈序列 A. a&#xff0c;b&a…...

第11章 规划过程组(收集需求)

第11章 规划过程组&#xff08;一&#xff09;11.3收集需求&#xff0c;在第三版教材第377~378页&#xff1b; 文字图片音频方式 第一个知识点&#xff1a;主要输出 1、需求跟踪矩阵 内容 业务需要、机会、目的和目标 项目目标 项目范围和 WBS 可…...

探索WebKit的守护神:深入Web安全策略

探索WebKit的守护神&#xff1a;深入Web安全策略 在数字化时代&#xff0c;网络已成为我们生活的一部分&#xff0c;而网页浏览器作为我们探索网络世界的窗口&#xff0c;其安全性至关重要。WebKit作为众多流行浏览器的内核&#xff0c;例如Safari&#xff0c;其安全性策略是保…...

unity ScrollRect裁剪ParticleSystem粒子

搜了下大概有这几种方法 通过模板缓存通过shader裁剪区域&#xff1a;案例一&#xff0c;案例二&#xff0c;案例三&#xff0c;三个案例都是类似的方法&#xff0c;需要在c#传入数据到shader通过插件 某乎上的模板缓存方法link&#xff0c;&#xff08;没有登录看不到全文&a…...

凤仪亭 | 第7集 | 大丈夫生居天地之间,岂能郁郁久居人下 | 司徒一言,令我拨云见日,茅塞顿开 | 三国演义 | 逐鹿群雄

&#x1f64b;大家好&#xff01;我是毛毛张! &#x1f308;个人首页&#xff1a; 神马都会亿点点的毛毛张 &#x1f4cc;这篇博客分享的是《三国演义》文学剧本第Ⅰ部分《群雄逐鹿》的第7️⃣集《凤仪亭》的经典语句和文学剧本全集台词 文章目录 1.经典语句2.文学剧本台词 …...

React实战学习(一)_棋盘设计

需求&#xff1a; 左上侧&#xff1a;状态左下侧&#xff1a;棋盘&#xff0c;保证胜利就结束 和 下过来的不能在下右侧&#xff1a;“时光机”,保证可以回顾&#xff0c;索引 语法&#xff1a; 父子之间属性传递&#xff08;props&#xff09;子父组件传递&#xff08;写法上&…...

【LeetCode】每日一题:三数之和

解题思路 最开始是打算沿着二数之和的思路做&#xff0c;即固定了最大的&#xff0c;然后小的开始遍历&#xff0c;因为这种遍历方式只需要遍历一轮就能完成&#xff0c;所以复杂度应该是O&#xff08;n2&#xff09;&#xff0c;但是最后几个示例还是超时了&#xff0c;可能进…...

逆风而行:提升逆商,让困难成为你前进的动力

一、引言 生活&#xff0c;总是充满了未知与变数。有时&#xff0c;我们会遇到阳光明媚的日子&#xff0c;享受着宁静与和谐&#xff1b;但更多时候&#xff0c;我们却不得不面对那些突如其来的坏事件&#xff0c;如工作的挫折、人际关系的困扰、健康的挑战等。这些事件如同突…...

新能源汽车CAN总线故障定位与干扰排除的几个方法

CAN总线是目前最受欢迎的现场总线之一,在新能源车中有广泛应用。新能源车的CAN总线故障和隐患将影响驾驶体验甚至行车安全,如何进行CAN总线故障定位及干扰排除呢? 目前,国内机动车保有量已经突破三亿大关。由于大量的燃油车带来严峻的环境问题,因此全面禁售燃油车的日程在…...

【涵子来信】——社交宝典:克服你心中的内向,世界总有缺陷

内向&#xff0c;你是内向的吗&#xff1f;想必每个人不同&#xff0c;面对的情形也是不同的。 暑假是一个很好的机会&#xff0c;我是可以去多社交社交。但是&#xff0c;面对着CSDN上这么多技术人er&#xff0c;那么&#xff0c;我的宝典&#xff0c;对于大家&#xff0c;有…...

LabVIEW项目外协时选择公司与个人兼职的比较

​在选择LabVIEW项目外协合作伙伴时&#xff0c;外协公司和个人兼职各有优劣。个人兼职成本较低且灵活&#xff0c;但在可靠性、技术覆盖面、资源和风险管理上存在不足。而外协公司拥有专业团队、丰富资源、完善的项目管理和风险控制&#xff0c;尽管成本较高&#xff0c;但能提…...

汽车电子工程师入门系列——CAN 规范系列通读

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...

泽众云真机-平台华为机型HarmonyOS NEXT系统已上线!

泽众云真机平台华为机型HarmonyOS NEXT系统已上线&#xff01; 之前文章《泽众云真机-平台即将升级支持华为机型HarmonyOS NEXT系统泽众云真机-平台即将升级支持华为机型HarmonyOS NEXT系统》&#xff0c;为什么要升级HarmonyOS NEXT系统&#xff1f;我们之前有说过&#xff0c…...

AI基础:从线性回归到梯度下降

一个简单的问题&#xff1a; 如果此时你正站在迷路缭绕的山坡上&#xff0c;能见度不高&#xff0c;但是你又想去往最低的山谷的位置&#xff0c;怎么走&#xff1f; 很简单&#xff0c;哪里陡那就往那里走呗——而这就是梯度下降算法的思想。 古话说&#xff1a;“先发制于人…...

AI产品经理面试

把优秀当习惯把优秀当习惯肯定不是口头说说&#xff0c;那有什么判断标准吗&#xff1f; 当我做完一件事儿的时候&#xff0c;我会看它有没有突破我的舒适圈、能不能惊艳到我自己。这就是我的判断标准。 在自我介绍和经历介绍时&#xff0c;面试者应该注重以下几个方面&#xf…...

二进制方式部署consul单机版

1.consul的下载 mkdir -p /root/consul/data && cd /root/consul wget https://releases.hashicorp.com/consul/1.18.0/consul_1.18.0_linux_amd64.zip unzip consul_1.18.0_linux_amd64.zip mv consul /usr/local/bin/ 2.配置文件 // 配置文件路径&#xff1a; /roo…...

SpringBoot整合Quartz实现动态定时任务

目录 1、Quartz简介1.1 Quartz的三大核心组件1.2 CronTrigger配置格式 2、SpringBoot整合Quartz框架2.1 创建项目2.2 实现定时任务 1、Quartz简介 Quartz是一个开源的任务调度服务&#xff0c;它可以独立使用&#xff0c;也可与其它的Java EE&#xff0c;Java SE应用整合使用。…...

qt 用宏控制静态接口的统一

1.概要 /** * 单件宏实验 * 创建一个可以生成单件的宏 * 起因&#xff1a;想让有些控件单件&#xff0c;但是c不支持静态的继承&#xff08;c#支持&#xff09; * 那么如果保证这些接口的统一呢&#xff0c;用宏 */ 2.代码 2.1 a.h #ifndef A_H #define A_H#include &…...

pdf怎么转换成jpg,本地转换还是在线转换?

PDF&#xff08;Portable Document Format&#xff09;和JPG&#xff08;Joint Photographic Experts Group&#xff09;这两种文件格式在我们的日常生活和工作中扮演着举足轻重的角色。PDF因其跨平台、保持原样性强的特点&#xff0c;被广泛应用于文件传输和存储&#xff1b;而…...

【物联网】802.15.4简介

目录 一、概述 二、802.15.4主要特点 2.1 工作频段和数据速率 2.2 支持简单器件 2.3 信标方式和超帧结构 2.4 数据传输和低功耗 三、低功耗 一、概述 802.15.4包括用于低速无线个人域网(LR-WPAN)的物理层和媒体接入控制层两个规范。它能支持消耗功率最少&#xff0c;一般…...

C++基础语法:复制构造函数,赋值构造函数及浅复制,深复制

前言 "打牢基础,万事不愁" .C的基础语法的学习 引入 前一篇帖子C基础语法:类构造函数之普通构造函数-CSDN博客讲了普通构造函数,还有 复制构造函数,赋值运算符以及延伸出来的浅复制和深复制问题,做个补充. 内容主要参考自<<C Prime Plus>> 6th Edition …...

架构是怎样练成的-楼宇监控系统案例

目录 概要 项目背景 原系统设计方案 改进后的设计方案 小结 概要 绝大多数人掌握的架构都是直接学习&#xff0c;慢慢地才能体会到一个架构的好处。架构是一种抽象&#xff0c;是为了复用目的而对代码做的抽象。通过一个项目的改造&#xff0c;理解架构是如何产生的&…...

valgrind使用浅谈

1、Valgrind 简介 Valgrind是一款用于内存调试、内存泄漏检测以及性能分析的软件开发工具&#xff0c;它可在以下平台上运行&#xff1a; X86/Linux、AMD64/Linux、ARM/Linux、ARM64/Linux、PPC32/Linux、PPC64/Linux、PPC64LE/Linu x、S390X/Linux、MIPS32/Linux、MIPS64/Li…...

强化学习专题:强化学习知识梳理(一)

2024/6/23&#xff1a; 前段时间有幸完成了大学期间的第一篇论文。在面试之前复盘一下关于自己论文中DQN的一些相关点。 浅谈主要区别&#xff08;在线 or 离线&#xff09; 首先&#xff0c;一切的开始是强化学习中时序差分方程&#xff0c;这体现了强化学习方法的优化策略。在…...

深入JVM:详解JIT即时编译器

文章目录 深入JVM&#xff1a;详解JIT即时编译器一、序言二、基础概念1、何为JIT即时编译2、热点代码 三、HotSpot内置的即时编译器1、C1编译器2、C2编译器3、分层编译3.1 协作流程 四、常见JIT优化技术1、方法内联2、逃逸分析&#xff08;1&#xff09;同步锁消除&#xff08;…...

ORBSLAM3_ROS_Ubuntu18_04环境搭建安装

orbslam3安装 ORB-SLAM3配置及安装教程&#xff08;2023.3&#xff09;_orbslam3安装-CSDN博客 换源&#xff0c;换成国内的 搜索software 安装工具 sudo apt install git sudo apt update sudo apt install gcc g cmake安装 cmake安装新版本 ubuntu20.04安装cmake详细…...