数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告