資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究統計每個字元出現頻率為偶數且最多隻有一個字元出現頻率為奇數的子字串
在這個問題中，我們將統計給定字串中包含所有字元出現頻率為偶數或僅有一個字元出現頻率為奇數的子字串的數量。
我們將使用位掩碼技術來解決這個問題。在位掩碼中，二進位制字串的每個位都表示一個字元。
問題陳述
我們給定一個長度為 N 的字串 alpha。還給定 'a' <= alpha[i] <= 't'。我們需要統計所有字元出現頻率為偶數或僅有一個字元出現頻率為奇數且其他字元出現頻率為偶數的子字串的數量。
示例
輸入
alpha = "pqq";
輸出
5
解釋 − 有效的子字串為 pqq、p、q、q 和 qq。
輸入
alpha = "mnbn";
輸出
5
解釋 − 有效的子字串為 nbn、m、n、b 和 n。
方法 1
此方法使用位掩碼來統計包含所有字元出現頻率為偶數或僅一個字元出現頻率為奇數的子字串的數量。
邏輯 − 當我們對兩個相同的整數進行異或運算時，結果為 0。
因此，我們將遍歷字串，並將每個字元的值與初始位掩碼值進行異或運算。如果之前出現過相同的位掩碼，我們可以說該子字串包含所有字元出現頻率為偶數，因為掩碼的差值為 0。此外，我們將新增和刪除每個字元以統計包含單個字元出現頻率為奇數的子字串。
演算法
步驟 1 − 初始化大小為 220 的矩陣列表。
步驟 2 − 將 'bitMask' 初始化為 0，表示初始掩碼，並將 'cnt' 初始化為 0 以儲存有效子字串的數量。
步驟 3 − 將 matrix[0] 初始化為 1，因為空字串始終有效。
步驟 4 − 開始遍歷字串。
步驟 5 − 將 1 左移 char 值，並將其與 bitmask 值進行異或運算。這意味著我們將當前字元新增到掩碼中。
步驟 6 − 將矩陣列表中相同 bitMask 的數量新增到 'cnt' 中。例如，在字串 'acbbe' 中，第 1 個和第 3 個索引處的位掩碼變為相同。因此，我們可以取子字串 'bb'。
步驟 7 − 使用迴圈進行 0 到 20 次迭代。在每次迭代中，將 1 左移 p，並將其與 bitmask 進行異或運算以從子字串中刪除字元。再次將之前出現的相同掩碼的數量新增到 'cnt' 變數中。
步驟 8 − 增加列表中當前 bitmask 的值。
步驟 9 − 返回 'cnt' 值。
示例
以下是上述演算法的程式 −
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 220
long long matrix[1 << 20];
long long getSubStrings(char *alpha) {
long long bitMask = 0, cnt = 0;
// One possible way for empty mask
matrix[0] = 1;
for (int i = 0; alpha[i]; i++) {
char c = alpha[i];
// Change the bitmask at char - 'a' value
bitMask ^= 1 << (c - 'a');
// Get valid substrings with the same mask
cnt += matrix[bitMask];
// Traverse all the possible masks
for (int p = 0; p < 20; p++) {
// Change mask and add count of valid substrings to cnt
cnt += matrix[bitMask ^ (1 << p)];
}
// Update frequency of mask
matrix[bitMask]++;
}
return cnt;
}
int main() {
char alpha[] = "pqq";
printf("The total number of substrings according to the problem statement is %lld\n", getSubStrings(alpha));
return 0;
}
輸出
The total number of substrings according to the problem statement is 5
#include <bits/stdc++.h>
using namespace std;
vector<int> matrix;
long long getSubStrings(string &alpha) {
matrix.resize(1 << 20);
long long bitMask = 0, cnt = 0;
// One possible way for empty mask
matrix[0] = 1;
for (auto c : alpha) {
// Change the bitmask at char - 'a' value
bitMask ^= 1 << (c - 'a');
// Get valid substrings with the same mask
cnt += matrix[bitMask];
// Traverse all the possible masks
for (int p = 0; p < 20; p++) {
// Change mask and add count of valid substrings to cnt
cnt += matrix[bitMask ^ (1 << p)];
}
// Update frequency of mask
matrix[bitMask]++;
}
return cnt;
}
int main() {
string alpha = "pqq";
cout << "The total number of substrings according to the problem statement is " << getSubStrings(alpha);
return 0;
}
輸出
The total number of substrings according to the problem statement is 5
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String alpha = "pqq";
System.out.println("The total number of substrings according to the problem statement is " + getSubStrings(alpha));
}
public static long getSubStrings(String alpha) {
long[] matrix = new long[1 << 20];
long bitMask = 0;
long cnt = 0;
// One possible way for empty mask
matrix[0] = 1;
for (char c : alpha.toCharArray()) {
// Change the bitmask at char - 'a' value
bitMask ^= 1 << (c - 'a');
// Get valid substrings with the same mask
cnt += matrix[(int) bitMask];
// Traverse all the possible masks
for (int p = 0; p < 20; p++) {
// Change mask and add count of valid substrings to cnt
cnt += matrix[(int) (bitMask ^ (1 << p))];
}
// Update frequency of mask
matrix[(int) bitMask]++;
}
return cnt;
}
}
輸出
The total number of substrings according to the problem statement is 5
def getSubStrings(alpha):
matrix = [0] * (1 << 20)
bitMask = 0
cnt = 0
# One possible way for empty mask
matrix[0] = 1
for c in alpha:
# Change the bitmask at char - 'a' value
bitMask ^= 1 << (ord(c) - ord('a'))
# Get valid substrings with the same mask
cnt += matrix[bitMask]
# Traverse all the possible masks
for p in range(20):
# Change mask and add count of valid substrings to cnt
cnt += matrix[bitMask ^ (1 << p)]
# Update frequency of mask
matrix[bitMask] += 1
return cnt
alpha = "pqq"
print("The total number of substrings according to the problem statement is", getSubStrings(alpha))
輸出
The total number of substrings according to the problem statement is 5
時間複雜度 − 遍歷字串的 O(N)。
空間複雜度 − O(2M)，其中 M 是字串中唯一的字元。
程式設計師可以透過獲取每個子字串並檢查該子字串是否根據問題陳述有效來解決問題。但是，位掩碼是解決此類問題的最佳技術。
185 次瀏覽
