C++ 最小删除使得相邻数字的异或值最多为1

在这个问题中，我们将学习找到所需的最小删除次数，以便当我们对任意两个相邻元素进行异或运算时，我们应该得到0或1。

我们将使用异或运算的性质来解决这个问题。例如，当我们对相同的数字进行异或运算时，我们总是得到0；当我们对相邻的偶数和奇数进行异或运算时，我们得到1。

问题陈述 −我们给定一个包含数字字符的num_str字符串。我们需要计算所需的最小删除次数，以便任何相邻剩余数字的异或运算结果最多为1。

示例示例

输入

num_str = "454545";

输出

0

解释

给定字符串中任意两个相邻数字的异或操作结果为1。因此，我们不需要删除任何数字。

输入

num_str = "7775477";

输出结果

2

解释

我们需要从字符串中删除“54”。因此，当我们从“77777”中取任意两个相邻数字的异或值时，结果要么是0，要么是1。

输入

num_str = "5556767675"

输出：

4

说明

这里有两个选择。第一个选择是当我们对“5555”字符串中的任何相邻数字进行XOR运算时，结果为0。因此，我们需要删除“676767”。

另一个选择是当我们对“676767”字符串中的任何两个相邻数字进行XOR运算时，结果为1。因此，我们需要删除“5555”字符串。

我们选择了最小的删除数目，即4。

方法1

在这个方法中，我们将根据需要最小删除的情况，保留所有相同的数字或一对连续的偶数和奇数数字。

因此，我们只保留有效的数字，删除所有其他数字。

算法

• 步骤1 - 定义“freq”映射来存储字符串字符和其频率。

• 步骤2 - 遍历字符串，并在映射中存储每个字符的频率。

• 步骤3 - 使用0初始化“validNums”变量，用于存储有效数字的数量。

• 步骤4 - 开始遍历频率映射。如果数字可以被2整除，并且下一个数字也存在于映射中，则将“validNums”的值更新为“validNums”与当前和下一个数字频率之和的最大值。

• 步骤5 - 如果当前数字不能被2整除，则将validNums变量的值更新为“validNums”和第二个数字的频率的最大值。

• 步骤6 - 将字符串长度减去“validNums”变量的值，返回结果值。

示例

#include <bits/stdc++.h>
using namespace std;

int totalDeletions(string num_str){
   // To store the frequency of each digit
   unordered_map<int, int> freq;

   // Calculating the frequency of each digit
   for (int p = 0; p < num_str.size(); p++)    {
      freq[num_str[p]]++;
   }
   int validNums = 0;

   // Traversing the map
   for (auto p : freq) {

      // If the digit is even, create pair of (digit, digit+1)
      if ((p.first - '0') % 2 == 0) {

         // Update the validNums with the maximum of validNums and (freq of digit + freq of digit+1)
         if (freq.find(p.first + 1) != freq.end()){
            validNums = max(validNums, (p.second + freq[p.first + 1]));
         }
      }

      // Update the validNums with the maximum of validNums and freq of digit
      validNums = max(validNums, p.second);
   }

   // Return the minimum number of deletions required
   return num_str.size() - validNums;
}
int main(){
   string num_str = "454545";
   cout << "The total number of deletions required to get atmost when we take XOR of all digits is " << totalDeletions(num_str);
   return 0;
}

输出结果

The total number of deletions required to get atmost when we take XOR of all digits is 0

时间复杂度 – O(N) 用于遍历字符串。

空间复杂度 – O(1)，因为我们只需要使用映射来存储10个数字的频率。

有时候，我们应该了解特定操作的属性来解决问题，就像我们在这个例子中使用了XOR的属性一样。程序员应该记住，相同数字的XOR始终为零。