資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告