資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中給定字串所有子串的唯一字元計數
假設我們想定義一個名為countUniqueChars(s)的函式，它將返回s中唯一字元的數量。如果s = "HELLOWORLD"，則"H"、"E"、"W"、"R"、"D"是唯一字元，因為它們在s中只出現一次，因此countUniqueChars(s) = 5。
現在在這個問題中，給定一個字串s，我們必須找到countUniqueChars(t)的總和，其中t是s的子串。（這裡有些子串可能會重複，在這種情況下，我們也必須計算重複的子串。）
由於答案可能非常大，我們可以返回答案模10^9+7。
因此，如果輸入像"HELLOWORLD"，則輸出將為128。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式add()，它將接收a, b，
返回(a mod m) + (b mod m)
定義一個函式mul()，它將接收a, b，
返回(a mod m) * (b mod m)
從主方法中執行以下操作：
n := s的大小
ans := 0
定義一個大小為26的陣列cnt
對於初始化i := 0，當i < n時，更新（i增加1），執行：
x := s[i]
如果cnt[x - 'A']的大小與0相同，則：
在cnt[x - 'A']的末尾插入-1
在cnt[x - 'A']的末尾插入i
對於初始化i := 0，當i < 26時，更新（i增加1），執行：
如果cnt[i]的大小與0相同，則：
忽略以下部分，跳到下一個迭代
在cnt[i]的末尾插入n
對於初始化j := 1，當j < cnt[i]的大小時，更新（j增加1），執行：
temp := mul(cnt[i, j] - cnt[i, j - 1], cnt[i, j + 1] - cnt[i, j])
ans := add(ans, temp)
返回ans
讓我們看看下面的實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return (a % m) + (b % m);
}
lli mul(lli a, lli b){
return (a % m) * (b % m);
}
int uniqueLetterString(string s) {
int n = s.size();
int ans = 0;
vector<int> cnt[26];
for (int i = 0; i < n; i++) {
char x = s[i];
if (cnt[x - 'A'].size() == 0) {
cnt[x - 'A'].push_back(-1);
}
cnt[x - 'A'].push_back(i);
}
for (int i = 0; i < 26; i++) {
if (cnt[i].size() == 0)
continue;
cnt[i].push_back(n);
for (int j = 1; j < cnt[i].size() - 1; j++) {
lli temp = mul(cnt[i][j] - cnt[i][j - 1], cnt[i][j +
1] - cnt[i][j]);
ans = add(ans, temp);
}
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.uniqueLetterString("HELLOWORLD"));
}輸入
"HELLOWORLD"
輸出
128
542 次檢視
