【字符串】【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];

};


相关文章
|
2月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
53 0
|
29天前
|
JSON 算法 数据挖掘
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读,主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析(如入度、出度、度中心性)、节点属性分析(如品牌、价格等属性的分布与聚类)、节点标签分析(如不同标签的分布及标签间的关联)。边序列分析则关注边的权重分析(如关联强度)、边的类型分析(如管理、协作等关系)及路径分析(如最短路径计算)。结合节点和边序列的分析,如子图挖掘和图的动态分析,可以帮助深入理解图的结构和功能。例如,通过子图挖掘可以发现具有特定结构的子图,而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用,能够从多个角度全面解读图谱数据,为决策提供有力支持。
|
2月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
675 0
高精度算法(加、减、乘、除,使用c++实现)
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
47 0
|
2月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
2月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
2月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
2月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
19天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。