資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學統計由單個不同字元組成的子字串個數
在本文中，我們將討論計算給定字串中由單個不同字元組成的子字串個數的問題。我們將探討解決此問題的有效演算法，並提供C++程式碼來實現它。
問題陳述
給定一個字串S，任務是計算由單個不同字元組成的子字串的個數。
例如，如果輸入字串是“aaaaa”，則輸出應為15，因為有15個子字串由單個不同字元組成。這些子字串是“a”，“a”，“a”，“a”，“a”，“aa”，“aa”，“aa”，“aa”，“aaa”，“aaa”，“aaa”，“aaaa”，“aaaa”，“aaaaa”。
演算法
我們可以線上性時間複雜度內解決這個問題。我們可以遍歷輸入字串，並跟蹤當前字元和當前子字串的長度。每當我們遇到一個新字元或到達字串的末尾時，我們可以計算可以使用當前字元和當前子字串的長度形成的子字串的個數。
以下是解決此問題的逐步演算法：
將count和len初始化為1。
從索引1到n-1遍歷字串S。
如果當前字元與前一個字元相同，則將len加1。
如果當前字元與前一個字元不同，則將(len*(len+1))/2加到count中，並將len重置為1。
返回count。
讓我們以字串“aaaaa”為例來理解該演算法：
將count和len初始化為1。
從索引1到n-1遍歷字串
在索引1處，當前字元與前一個字元相同，因此將len加1。
在索引2處，當前字元與前一個字元相同，因此將len加1。
在索引3處，當前字元與前一個字元相同，因此將len加1。
在索引4處，當前字元與前一個字元相同，因此將len加1。
我們已經到達字串的末尾，因此將(len*(len+1))/2加到count中。count = count + (5*(5+1))/2 = 15。
返回count。
C++實現
以下是實現上述演算法的C++程式碼：
示例
以下是實現上述演算法的程式：
#include <stdio.h>
#include <string.h>
int countSubstrings(char S[]) {
int n = strlen(S);
int count = 1, len = 1; // Initialize counters for substrings and consecutive characters
for (int i = 1; i < n; i++) {
if (S[i] == S[i - 1]) { // Check if the current character is the same as the previous one
len++; // If yes, increment the length of consecutive characters
} else {
count += (len * (len + 1)) / 2; // Calculate and accumulate substrings formed by consecutive characters
len = 1; // Reset the length for new set of consecutive characters
}
}
count += (len * (len + 1)) / 2; // Account for the last set of consecutive characters
return count - 1; // Return the total count of substrings
}
int main() {
char S[] = "aaaaa";
int count = countSubstrings(S);
printf("%d\n", count);
return 0;
}
輸出
15
#include<bits/stdc++.h>
using namespace std;
int countSubstrings(string S) {
int n = S.length();
int count = 1, len = 1;
for (int i = 1; i < n; i++) {
if (S[i] == S[i-1]) {
len++;
} else {
count += (len*(len+1))/2;
len = 1;
}
}
count += (len*(len+1))/2;
return count-1;
}
int main() {
string S = "aaaaa";
int count = countSubstrings(S);
cout << count << endl;
return 0;
}
輸出
15
public class SubstringCounter {
public static int countSubstrings(String S) {
int n = S.length(); // length of the input string
int count = 1, len = 1; // Initialize counters for substrings and consecutive characters
for (int i = 1; i < n; i++) {
if (S.charAt(i) == S.charAt(i - 1)) { // Check if the current character is the same as the previous one
len++; // If yes, increment the length of consecutive characters
} else {
count += (len * (len + 1)) / 2; // Calculate and accumulate substrings formed by consecutive characters
len = 1; // Reset the length for new set of consecutive characters
}
}
count += (len * (len + 1)) / 2; // Account for the last set of consecutive characters
return count - 1; // Return the total count of substrings
}
public static void main(String[] args) {
String S = "aaaaa";
int count = countSubstrings(S);
System.out.println(count);
}
}
輸出
15
def count_substrings(S):
n = len(S)
count = 1 # Initialize counters for substrings
length = 1 # Initialize counter for consecutive characters
for i in range(1, n):
if S[i] == S[i - 1]: # Check if the current character is the same as the previous one
length += 1 # If yes, increment the length of consecutive characters
else:
count += (length * (length + 1)) // 2 # Calculate and accumulate substrings formed by consecutive characters
length = 1 # Reset the length for new set of consecutive characters
count += (length * (length + 1)) // 2 # Account for the last set of consecutive characters
return count - 1
def main():
S = "aaaaa"
count = count_substrings(S) # Call the function to count substrings
print(count)
if __name__ == "__main__":
main()
輸出
15
結論
在本文中，我們討論了計算給定字串中由單個不同字元組成的子字串個數的問題。我們提供了一個有效的演算法，可以線上性時間複雜度內解決此問題，並用C++實現了它。這個問題也可以使用其他技術來解決，但是上述演算法提供了
201 次檢視
