C++ 计算具有素数个不同字符的字符串的偶数索引

在这个问题中，我们将找到给定字符串中的无效字符的总数。如果特定的偶数索引之前的总不同字符数是素数，我们可以说该字符是无效的。

我们可以使用映射数据结构来计算遍历字符串时总不同字符的数量。此外，我们还可以使用字符串来跟踪不同的字符。对于每个字符，我们可以检查其索引是否为偶数，以及不同的字符是否是素数。

问题陈述：我们给出了一个包含N个字符的字符串alpha。我们需要找到给定字符串中的总无效字符数。如果在范围[0，index]中的不同字符的总数量是素数，那么该字符是无效的，其中0 <= index < N且index是偶数。

示例

输入

alpha = "ppqprs"

输出

解释

第2个索引是偶数，并且总共有2个不同的字符，是一个素数。所以，第2个索引是无效的。
第4个索引也是偶数，并且总共有3个不同的字符，是一个素数。所以，第4个索引也是无效的。

输入

alpha = "tttttt";

结果

说明

不同字符的总数为1，因为字符串的所有字符都是相同的。

输入

alpha = "abcdefgh";

输出

解释

在第2个索引处，不同字符的总数为3。
在第4个索引处，不同字符的总数为5。
在第6个索引处，不同字符的总数为7。

方法1

在这个方法中，我们将找到0到10,00,000范围内的所有素数。然后，我们将使用映射数据结构来存储不同的字符。如果在任何偶数索引处，不同字符的数量是素数，我们将计算该索引为无效索引。

算法

步骤1 − 执行computePrimeNums()函数，以找到0到10,00,000范围内的所有素数。
步骤1.2 − 在computePrimeNums()函数中，将’primeNum’数组元素初始化为1，认为所有数字最初都是素数。
步骤1.3 − 如果数字不是素数，则将元素从1更新为0。因此，将索引0和1的元素更新为0，因为它们不是素数。
步骤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 <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

时间复杂度 − 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 − 否则，在索引*索引小于数字值的情况下进行迭代。
步骤3.3 − 在循环中，如果数字可被索引值整除，则返回false。
步骤3.4 − 最后，返回true。
步骤4 − 最后，返回’cnt’值。

示例

#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;
}