数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究最小删除次数，使得相邻数字的异或值最多为1
在这个问题中，我们将学习如何找到所需的最小删除次数，以便当我们对任何两个相邻元素进行异或运算时，结果应该为0或1。
我们将使用异或运算的特性来解决这个问题。例如，当我们对相同的数字进行异或运算时，结果总是0；当我们对连续的偶数和奇数进行异或运算时，结果为1。
问题陈述
我们得到一个包含数字字符的字符串num_str。我们需要计算所需的最小删除次数，以便任何两个相邻剩余数字的异或运算结果最多为1。
示例
Input: num_str = "454545"; Output: 0
解释
给定字符串中任何两个相邻数字的异或运算结果为1。因此，我们不需要删除任何数字。
示例
Input: num_str = "7775477"; Output: 2
解释
我们需要从字符串中删除“54”。因此，当我们对“77777”中任何两个相邻数字进行异或运算时，结果为0或1。
示例
Input: num_str = "5556767675" Output: 4
解释
这里，我们有两个选择。第一个是当我们对“5555”字符串中任何两个相邻数字进行异或运算时，结果为0。因此，我们需要删除“676767”。
另一个选择是当我们对“676767”字符串中任何两个相邻数字进行异或运算时，结果为1。因此，我们需要删除“5555”字符串。
我们选择了最小的删除次数，即4。
方法1
在这种方法中，我们将根据所需的最小删除次数保留所有相同的数字或一对连续的偶数和奇数。
因此，我们只保留有效的数字，删除所有其他数字。
算法
步骤1 - 定义‘freq’映射来存储字符串字符及其频率。
步骤2 - 遍历字符串并将每个字符的频率存储在映射中。
步骤3 - 将‘validNums’变量初始化为0，以存储有效数字的数量。
步骤4 - 开始遍历频率映射。如果数字能被2整除，并且下一个数字也存在于映射中，则将‘validNums’的值更新为‘validNums’和当前数字与下一个数字频率之和的最大值。
步骤5 - 如果当前数字不能被2整除，则将validNums变量的值更新为‘validNums’和第二个数字频率的最大值。
步骤6 - 返回从字符串长度减去‘validNums’变量的值后的结果值。
示例
以下是上述算法的程序：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int totalDeletions(char *num_str) {
// To store the frequency of each digit
int freq[10] = {0};
// Calculating the frequency of each digit
for (int p = 0; p < strlen(num_str); p++) {
freq[num_str[p] - '0']++;
}
int validNums = 0;
// Traversing the frequency array
for (int i = 0; i < 10; i++) {
// If the digit is even, create a pair of (digit, digit+1)
if (i % 2 == 0) {
// Update the validNums with the maximum of validNums and (freq of digit + freq of digit+1)
if (i + 1 < 10) {
validNums = (validNums > (freq[i] + freq[i + 1])) ? validNums : (freq[i] + freq[i + 1]);
}
}
// Update the validNums with the maximum of validNums and freq of digit
validNums = (validNums > freq[i]) ? validNums : freq[i];
}
// Return the minimum number of deletions required
return strlen(num_str) - validNums;
}
int main() {
char num_str[] = "454545";
printf("The total number of deletions required to get at most when we take XOR of all digits is %d\n", totalDeletions(num_str));
return 0;
}
输出
The total number of deletions required to get at most when we take XOR of all digits is 0
#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 at most when we take XOR of all digits is 0
import java.util.HashMap;
public class Main {
public static int totalDeletions(String num_str) {
// To store the frequency of each digit
HashMap<Integer, Integer> freq = new HashMap<>();
// Calculating the frequency of each digit
for (int p = 0; p < num_str.length(); p++) {
int digit = Character.getNumericValue(num_str.charAt(p));
freq.put(digit, freq.getOrDefault(digit, 0) + 1);
}
int validNums = 0;
// Traversing the map
for (int digit : freq.keySet()) {
// If the digit is even, create a pair of (digit, digit+1)
if (digit % 2 == 0) {
// Update the validNums with the maximum of validNums and (freq of digit + freq of digit+1)
if (freq.containsKey(digit + 1)) {
validNums = Math.max(validNums, freq.get(digit) + freq.get(digit + 1));
}
}
// Update the validNums with the maximum of validNums and freq of digit
validNums = Math.max(validNums, freq.get(digit));
}
// Return the minimum number of deletions required
return num_str.length() - validNums;
}
public static void main(String[] args) {
String num_str = "454545";
System.out.println("The total number of deletions required to get at most when we take XOR of all digits is " + totalDeletions(num_str));
}
}
输出
The total number of deletions required to get at most when we take XOR of all digits is 0
def total_deletions(num_str):
# To store the frequency of each digit
freq = {}
# Calculating the frequency of each digit
for digit in num_str:
freq[digit] = freq.get(digit, 0) + 1
valid_nums = 0
# Traversing the map
for digit, count in freq.items():
# If the digit is even, create a pair of (digit, digit+1)
if int(digit) % 2 == 0:
# Update the validNums with the maximum of validNums and (freq of digit + freq of digit+1)
if str(int(digit) + 1) in freq:
valid_nums = max(valid_nums, count + freq[str(int(digit) + 1)])
# Update the validNums with the maximum of validNums and freq of digit
valid_nums = max(valid_nums, count)
# Return the minimum number of deletions required
return len(num_str) - valid_nums
num_str = "454545"
print(f"The total number of deletions required to get at most when we take XOR of all digits is {total_deletions(num_str)}")
输出
The total number of deletions required to get at most when we take XOR of all digits is 0
时间复杂度 - 遍历字符串为 O(N)。
空间复杂度 - O(1)，因为我们只需要使用映射来存储10个数字的频率。
有时，我们应该了解特定运算的特性才能解决问题，就像我们在这个例子中使用异或运算的特性一样。程序员应该记住，相同数字的异或运算结果总是零。
更新于：2023年10月27日
81 次浏览
广告