資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究計算字首具有質數個不同字元的字串的偶數下標
在這個問題中，我們將找出給定字串中的總無效字元。如果特定偶數索引之前所有不同字元的總數是質數，則可以將字元稱為無效。
我們可以使用對映資料結構來統計遍歷字串時的不同字元總數。此外，我們可以使用字元字串來跟蹤不同數字。此外，對於每個字元，我們可以檢查其索引是否是偶數以及不同字元是否是質數。
問題陳述 - 我們給定了一個包含 N 個字元的字串 alpha。我們需要找出給定字串中的總無效字元。如果不同字元的總數是 [0, index] 範圍內的質數，則字元無效，其中 0 <= index < N 且索引為偶數。
示例
輸入
alpha = "ppqprs"
輸出
2
說明
第 2 個索引是偶數，不同的字元總數為 2，是質數。因此，第 2 個索引無效。
第 4 個索引也是偶數，不同的字元總數為 3，是質數。因此，第 4 個索引也無效。
輸入
alpha = "tttttt";
輸出
0
說明
不同的字元總數為 1，因為字串的所有字元都相同。
輸入
alpha = "abcdefgh";
輸出
3
說明
在第 2nd 索引，不同的字元總數為 3。
在第 4th 索引，不同的字元總數為 5。
在第 6th 索引，不同的字元總數為 7。
方法 1
在此方法中，我們將在 0 到 1000000 範圍內找到所有質數。在此之後，我們將使用對映資料結構來儲存不同的字元。如果在任何偶數索引處，不同字元的數量是質數，我們將把該索引計數為無效索引。
演算法
步驟 1 − 執行 computePrimeNums() 函式以找到 0 到 1000000 範圍內所有質數。
步驟 1.2 − 在 computePrimeNums() 函式中，初始化 ‘primeNum’ 陣列元素為 1，初始時假定所有數字都是質數。
步驟 1.3 − 如果數字不是質數，我們需要將元素從 1 更新為 0。因此，更新第 0 和第 1 個索引的元素，因為它們不是質數。
步驟 1.4 − 在所有偶數索引處，用 0 替換 1，因為偶數不是質數。
步驟 1.5 − 接下來，對於每個奇數，我們需要檢查它是否是質數。因此，開始遍歷奇數。
步驟 1.6 − 使用另一個巢狀迴圈來遍歷奇數並替換 p*q 索引處的元素，因為它不是質數。
步驟 2 − 用 0 初始化 ‘diffChars’ 變數以儲存特定索引處所有不同字元的總數。此外，使用 ‘cnt’ 初始化無效字元的計數。我們將使用 ‘freq’ 對映來儲存字元的頻次。
步驟 3 − 開始迭代字串，並且對映中字元的頻次為 0，將字元新增到對映中，並將 ‘difChars’ 增大 1。
步驟 4 − 如果 p 可以被 0 整除，並且 ‘diffChars’ 是質數，將 ‘cnt’ 的值增大 1。
步驟 5 − 返回 ‘cnt’ 的值。
示例
以下是上述演算法的示例 −
#include <stdio.h>
#include <string.h>
// Array to store prime numbers
int primeNum[300];
// Function to calculate prime numbers
void computePrimeNums() {
// Initialize array with 1
memset(primeNum, 1, sizeof(primeNum));
primeNum[0] = primeNum[1] = 0;
// All even numbers are non-prime
for (int p = 4; p <= 300; p += 2)
primeNum[p] = 0;
// For odd numbers
for (int p = 3; p * p <= 300; p += 2) {
if (primeNum[p]) {
// Handling non-prime numbers
for (int q = 3; q * p <= 300; q += 2)
primeNum[p * q] = 0;
}
}
}
int getInvalidChars(int len, char* alpha) {
computePrimeNums();
int diffChars = 0;
// To store final answer
int cnt = 0;
// For storing the frequency of characters
int freq[256] = {0}; // Assuming ASCII characters
// Traverse the string
for (int p = 0; p < len; p++) {
// If we got a character for the first time
if (freq[alpha[p]] == 0) {
freq[alpha[p]]++;
diffChars++;
}
// For even index and diffChars is prime
if ((p % 2 == 0) && primeNum[diffChars]) {
cnt++;
}
}
return cnt;
}
int main() {
int len = 6;
char alpha[] = "ppqprs";
printf("The number of invalid characters is %d\n", getInvalidChars(len, alpha));
return 0;
}
輸出
The number of invalid characters is 2
#include <bits/stdc++.h>
using namespace std;
// Array to store prime numbers
int primeNum[300];
// Function to calculate prime numbers
void computePrimeNums() {
// Initialize array with 1
memset(primeNum, 1, sizeof primeNum);
primeNum[0] = primeNum[1] = 0;
// All even numbers are non-prime
for (int p = 4; p <= 300; p += 2)
primeNum[p] = 0;
// For odd numbers
for (int p = 3; p * p <= 300; p += 2) {
if (primeNum[p]) {
// Handling non-prime numbers
for (int q = 3; q * p <= 300; q += 2)
primeNum[p * q] = 0;
}
}
}
int getInvalidChars(int len, string alpha) {
computePrimeNums();
int diffChars = 0;
// To store final answer
int cnt = 0;
// For storing the frequency of characters
unordered_map<char, int> freq;
// Traverse the string
for (int p = 0; p < len; p++) {
// If we got a character for the first time
if (freq[alpha[p]] == 0) {
freq[alpha[p]]++;
diffChars++;
}
// For even index and diffChars is prime
if (((p % 2) == 0) and primeNum[diffChars]) {
cnt++;
}
}
return cnt;
}
int main(){
int len = 6;
string alpha = "ppqprs";
cout << "The number of invalid characters is " << getInvalidChars(len, alpha) << endl;
return 0;
}
輸出
The number of invalid characters is 2
import java.util.HashMap;
public class Main {
// Array to store prime numbers
static boolean[] primeNum = new boolean[301];
// Function to calculate prime numbers
static void computePrimeNums() {
// Initialize array with true
for (int i = 0; i < 301; i++) {
primeNum[i] = true;
}
primeNum[0] = primeNum[1] = false;
// All even numbers are non-prime
for (int p = 4; p <= 300; p += 2) {
primeNum[p] = false;
}
// For odd numbers
for (int p = 3; p * p <= 300; p += 2) {
if (primeNum[p]) {
// Handling non-prime numbers
for (int q = 3; q * p <= 300; q += 2) {
primeNum[p * q] = false;
}
}
}
}
static int getInvalidChars(String alpha) {
computePrimeNums();
int diffChars = 0;
int cnt = 0;
HashMap<Character, Integer> freq = new HashMap<>();
// Traverse the string
for (int p = 0; p < alpha.length(); p++) {
// If we got a character for the first time
if (freq.getOrDefault(alpha.charAt(p), 0) == 0) {
freq.put(alpha.charAt(p), 1);
diffChars++;
}
// For even index and diffChars is prime
if (p % 2 == 0 && primeNum[diffChars]) {
cnt++;
}
}
return cnt;
}
public static void main(String[] args) {
String alpha = "ppqprs";
System.out.println("The number of invalid characters is " + getInvalidChars(alpha));
}
}
輸出
The number of invalid characters is 2
import math
# Function to calculate prime numbers
def compute_prime_nums():
prime_nums = [True] * 301
prime_nums[0] = prime_nums[1] = False
# All even numbers are non-prime
for p in range(4, 301, 2):
prime_nums[p] = False
# For odd numbers
p = 3
while p * p <= 300:
if prime_nums[p]:
# Handling non-prime numbers
for q in range(3, 301, 2):
if p * q <= 300:
prime_nums[p * q] = False
p += 2
return prime_nums
def get_invalid_chars(alpha):
prime_nums = compute_prime_nums()
diff_chars = 0
cnt = 0
freq = {}
# Traverse the string
for p in range(len(alpha)):
# If we got a character for the first time
if freq.get(alpha[p], 0) == 0:
freq[alpha[p]] = 1
diff_chars += 1
# For even index and diffChars is prime
if p % 2 == 0 and prime_nums[diff_chars]:
cnt += 1
return cnt
def main():
alpha = "ppqprs"
print("The number of invalid characters is", get_invalid_chars(alpha))
if __name__ == "__main__":
main()
輸出
The number of invalid characters is 2
時間複雜度 − O(N + 300)，因為我們遍歷字串並在 300 範圍內計算所有質數。
空間複雜度 − O(1)，因為我們使用常量空間來儲存質數。
方法 2
在此方法中，我們將使用字串來跟蹤不同的字元。此外，我們將隨時檢查質數，而不是預先計算質數。
演算法
步驟 1 − 使用 0 初始化 ‘cnt’，使用空字串初始化 ‘diffChars’。
步驟 2 − 在遍歷字串時，使用 find() 方法檢查字串的 pth 索引處的字元是否存在於 ‘diffCHars’ 字串中。如果不存在，則將一個字元追加到 ‘diffChars’ 字串中。
步驟 3 − 如果索引是偶數並且 ‘diffChars’ 字串的長度是質數，則將 ‘cnt’ 值增大 1。
步驟 3.1 − 在 checkForPrime() 函式中，如果數字小於或等於 1，則返回 false。
步驟 3.2 − 否則，進行迭代，直至 index*index 小於數字值。
步驟 3.3 − 在迴圈中，如果數字可以被索引值整除，則返回 false。
步驟 3.4 − 最後，返回 true。
步驟 4 − 最後，返回 “cnt” 值。
示例
以下是上述演算法的示例 −
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
// Function to check if a number is prime
bool checkForPrime(int num) {
if (num <= 1) {
return false;
}
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
return false; // not a prime number
}
}
// Number is a prime number
return true;
}
int getInvalidChars(int len, char alpha[]) {
// To store final answer
int cnt = 0;
char diffChars[256] = {0}; // Assuming ASCII characters
// Traverse the string
for (int p = 0; p < len; p++) {
// If we got a character for the first time
if (strchr(diffChars, alpha[p]) == NULL) {
diffChars[strlen(diffChars)] = alpha[p];
}
// For even index and diffChars is prime
if ((p % 2 == 0) && checkForPrime(strlen(diffChars))) {
cnt++;
}
}
return cnt;
}
int main() {
int len = 6;
char alpha[] = "ppqprs";
printf("The number of invalid characters is %d\n", getInvalidChars(len, alpha));
return 0;
}
輸出
The number of invalid characters is 2
#include <bits/stdc++.h>
using namespace std;
bool checkForPrime(int num) {
if (num <= 1) {
return false;
}
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
return false; // not a prime number
}
}
// Number is a prime number
return true;
}
int getInvalidChars(int len, string alpha) {
// To store final answer
int cnt = 0;
string diffChars = "";
// Traverse the string
for (int p = 0; p < len; p++) {
// If we got a character for the first time
if (diffChars.find(alpha[p]) == string::npos) {
diffChars += alpha[p];
}
// For even index and diffChars is prime
if (((p % 2) == 0) and checkForPrime(diffChars.length())) {
cnt++;
}
}
return cnt;
}
int main() {
int len = 6;
string alpha = "ppqprs";
cout << "The number of invalid characters is " << getInvalidChars(len, alpha) << endl;
return 0;
}
輸出
The number of invalid characters is 2
public class Main {
// Function to check if a number is prime
static boolean checkForPrime(int num) {
if (num <= 1) {
return false;
}
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
return false; // not a prime number
}
}
// Number is a prime number
return true;
}
static int getInvalidChars(String alpha) {
// To store final answer
int cnt = 0;
StringBuilder diffChars = new StringBuilder();
// Traverse the string
for (int p = 0; p < alpha.length(); p++) {
// If we got a character for the first time
if (diffChars.indexOf(String.valueOf(alpha.charAt(p))) == -1) {
diffChars.append(alpha.charAt(p));
}
// For even index and diffChars is prime
if (p % 2 == 0 && checkForPrime(diffChars.length())) {
cnt++;
}
}
return cnt;
}
public static void main(String[] args) {
String alpha = "ppqprs";
System.out.println("The number of invalid characters is " + getInvalidChars(alpha));
}
}
輸出
The number of invalid characters is 2
# Function to check if a number is prime
def check_for_prime(num):
if num <= 1:
return False
for p in range(2, int(num**0.5) + 1):
if num % p == 0:
return False # not a prime number
return True
def get_invalid_chars(alpha):
# To store final answer
cnt = 0
diff_chars = ""
# Traverse the string
for p in range(len(alpha)):
# If we got a character for the first time
if alpha[p] not in diff_chars:
diff_chars += alpha[p]
# For even index and diffChars is prime
if p % 2 == 0 and check_for_prime(len(diff_chars)):
cnt += 1
return cnt
def main():
alpha = "ppqprs"
print("The number of invalid characters is", get_invalid_chars(alpha))
if __name__ == "__main__":
main()
輸出
The number of invalid characters is 2
時間複雜度 − O(N*D)，其中 N 表示字串長度，D 表示給定字串中總的不同字元。
空間複雜度 − O(1)，因為我們不使用任何額外空間。
我們學習了兩種不同的方法來查詢給定字串中的無效字元。當給定一個包含數百萬個字元的大字串時，第一種方法非常快。第二種方法更注重空間最佳化，因為它不使用任何動態空間。
更新於：2023 年 10 月 16 日
90 次瀏覽
廣告