【字符串】【C++算法】828.统计子串中的唯一字符

简介: 【字符串】【C++算法】828.统计子串中的唯一字符

作者推荐

【动态规划】【map】【C++算法】1289. 下降路径最小和 II

本文涉及知识点

子数组(串) 字符串

LeetCoce828.统计子串中的唯一字符

我们定义了一个函数 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 <= 105

s 只包含大写英文字符

分析

累加各字符在各子串中出现的次数。s[i] 是那些子串的唯一字符?令iPre<i ,且s[iPre]==s[i]。如果有多个iPre,取最大值。如果不存在iPre,取-1。令iNext>i,且s[i]==s[iNext] ,如果有多个合法的iNext,取最小值。如果不存在,取s.length。

left 取(iPre,i] right取[i,iNext) 。 s[i] 是子串[left,right]的唯一字符,且s[i]不是其它子串的唯一字符。

vNext[i] 记录 ‘A’+i 的所有下标,最前面加上-1,最后加上s.length。

枚举vNext[i] 首尾元素外的所有元素。

代码

核心代码

class Solution {
public:
  int uniqueLetterString(string s) {
    vector<vector<int>> indexs(26);
    for (auto& v : indexs)
    {
      v.emplace_back(-1);
    }
    for (int i = 0 ; i < s.length();i++ )
    {
      indexs[s[i] - 'A'].emplace_back(i);
    }
    int iRet = 0;
    for (auto& v : indexs)
    {
      v.emplace_back(s.length());
      for (int i = 1; i + 1 < v.size(); i++)
      {
        iRet += (v[i] - v[i - 1]) * (v[i + 1] - v[i]);
      }
    }
    return iRet;
  }
};

测试用例

2023年1月 第一版

class Solution {

public:

int uniqueLetterString(string s) {

for (int j = 0; j < 26; j++)

{

setCharIndexs[j].push_back(-1);

}

for (int i = 0; i < s.length();i++)

{

const auto& ch = s[i];

Add(setCharIndexs[ch - ‘A’], i);

}

for (int j = 0; j < 26; j++)

{

Add(setCharIndexs[j], s.length());

}

return m_iNum;

}

void Add(std::vector& v,int i )

{

if (v.size() == 3)

{

v[0] = v[1];

v[1] = v[2];

v[2] = i;

}

else

{

v.push_back(i);

}

if (3 == v.size())

{

m_iNum += (v[1] - v[0])*(v[2] - v[1]);

}

}

std::vector setCharIndexs[26];

int m_iNum = 0;

};

2023年 1月 第二版

class Solution {

public:

int uniqueLetterString(string s) {

int iNum = 0;

for (int i = 0; i < s.length();i++)

{

const auto& ch = s[i];

{

auto& curSet = setCharIndexs[ch - ‘A’];

if (curSet.size() == 2)

{

curSet[0] = curSet[1];

curSet[1] = i;

}

else

{

curSet.push_back(i);

}

}

for (int j = 0; j < 26; j++)

{

auto& charSet = setCharIndexs[j];

if (charSet.empty())

{

continue;

}

if (2 == charSet.size())

{

iNum += charSet[1] - charSet[0];

}

else

{

iNum += charSet[0] + 1;

}

}

}

return iNum;

}

std::vector setCharIndexs[26];

};

2023年1月 第三版

class Solution {

public:

int uniqueLetterString(string s) {

int iNum = 0;

for (int i = 0; i < s.length();i++)

{

const auto& ch = s[i];

{

auto& curSet = setCharIndexs[ch - ‘A’];

curSet.insert(i);

if (curSet.size() > 2)

{

curSet.erase(curSet.begin());

}

}

for (int j = 0; j < 26; j++)

{

auto& charSet = setCharIndexs[j];

if (charSet.empty())

{

continue;

}

if (2 == charSet.size())

{

iNum += *charSet.rbegin() - *charSet.begin();

}

else

{

iNum += *charSet.rbegin() + 1;

}

}

}

return iNum;

}

std::set setCharIndexs[26];

};


目录
打赏
0
0
0
0
36
分享
相关文章
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
72 0
|
15天前
|
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
37 15
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
42 12
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
13 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
c++ linux通过实现独立进程之间的通信和传递字符串 demo
的进程间通信机制,适用于父子进程之间的数据传输。希望本文能帮助您更好地理解和应用Linux管道,提升开发效率。 在实际开发中,除了管道,还可以根据具体需求选择消息队列、共享内存、套接字等其他进程间通信方
59 16
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
65 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
3月前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
67 4