資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學根據給定條件查詢二進位制字串中最後剩下的字元
二進位制字串只包含兩個字元，通常是數字0和1，它代表一系列二進位制數字。
問題陳述
在本問題中，我們得到一個包含零和一的二進位制字串。在解決問題時，我們需要注意兩個條件。首先，一個數字可以刪除另一個數字，例如‘1’可以刪除‘0’，反之亦然。其次，如果在任何時刻整個字串只包含0和1，則列印相應的數字。這裡，二進位制字串將作為使用者給我們的輸入。讓我們看看我們應該如何解決這個問題。
例如
讓我們透過一些例子來理解這個問題。
Input: s = "100100" Output: 0
解釋
這裡，第一個數字是1，它將刪除第二個數字0 // 10100
現在，第三個數字是0，它將刪除第一個數字1 // 0100
現在，第四個數字是1，它將刪除第五個數字0 // 010
現在，第六個數字是0，它將刪除第四個數字1 // 00
現在，由於兩者都是零，並且沒有剩餘的1，所以它將返回最終輸出為0
Input: s = "10110" Output: 1
解釋
這裡，第一個數字是1，它將刪除第二個數字0 // 1110
現在，第五個數字是0，它將刪除第四個數字1 // 110
現在，第三個數字是1，它將刪除第五個數字0 // 11
現在，由於兩者都是一，並且沒有剩餘的0，所以它將返回最終輸出為1
問題解釋
讓我們嘗試理解這個問題並找到它的解決方案。我們知道二進位制字串僅包含1和0。
解決方案方法
演算法
定義陣列a[2]和count[2]分別跟蹤已刪除的字元和剩餘的字元。
建立一個佇列q來儲存二進位制字串的字元。
遍歷二進位制字串，將字元轉換為整數，並在count中遞增相應的計數。
只要同時存在剩餘的0和1：
從佇列中獲取前一個元素t。
如果a[t]大於0：
遞減a[t]以指示已刪除的字元。
遞減count[t]以指示型別t的剩餘字元減少一個。
否則：
遞增a[t XOR 1]以指示相反型別的字元可以刪除字元t的下一個出現。
將t推回佇列。
迴圈結束後，如果還有剩餘的0，則返回"0"，否則返回"1"。
虛擬碼
// helper function
function helper(binary_string, N):
Declare array a[2] = {0, 0}
Declare array count[2] = {0, 0}
Declare queue q
for i = 0 to N - 1:
Convert binary_string[i] to integer and store in x
Increment count[x]
Push x into queue q
while count[0] > 0 and count[1] > 0:
t = q.front()
Pop the front element from queue q
if a[t] > 0:
Decrement a[t]
Decrement count[t]
else:
Increment a[t XOR 1]
Push t into queue q
if count[0] > 0:
Return "0"
else:
Return "1"
// Main function
function main():
Initialize binary_string = "101101000001"
Set N as the length of binary_string
Print "The last remaining Character in the Binary String is: " + helper(binary_string, N)
Call the main function
示例：C++ 程式碼
#include <bits/stdc++.h>
using namespace std;
// Define a helper function to find the last remaining Character in the Binary String according to the given conditions
string helper(string str, int N){
// Define an array to delete the counters, this will count the deleted values of each 1's and 0's
int a[] = { 0, 0 };
// Define another array that would keep count of the characters left from each 1's and 0's
int count[] = { 0, 0 };
// Define a queue to store the given string
queue<int> q;
// Run a for loop to initialize the queue
for (int i = 0; i < N; i++){
// change character to integer type
int x = str[i]-'0';
// Add in counter array followed by pushing the element in the queue
count[x]++;
q.push(x);
}
// Run another loop till at least 1 digit is left from both 0's and 1's
while (count[0] > 0 && count[1] > 0){
// Store the front element in a variable
int t = q.front();
q.pop();
// We will increment the deleted counter for the opposite digit without a floating removal for the current character else delete the current character and move forward
if (a[t] > 0){
a[t]--;
count[t]--;
}
else{
a[t ^ 1]++;
q.push(t);
}
}
// If at the end 0 are left then the answer is 0, otherwise the answer is 1
if (count[0] > 0){
return "0";
}
return "1";
}
// Main function
int main(){
// Input string given for an example
string s = "101101000001";
// Store size of String in a variable
int size = s.length();
// Call the helper function that returns the last remaining Character in the Binary String
cout << "The last remaining Character in the Binary String is: " << helper(s, size);
return 0;
}
輸出
The last remaining Character in the Binary String is: 1
上述程式碼的複雜度
時間複雜度 − O(n); 其中n表示給定字串中數字的個數。
空間複雜度 − O(n); 我們在上述程式碼中使用佇列儲存字串以解決問題。
結論
在本文中，根據給定條件查詢二進位制字串中最後剩下的字元。上述解決方案使用佇列和陣列來跟蹤計數和刪除狀態。它遍歷二進位制字串，應用字元刪除規則，直到沒有相鄰的重複項。該演算法有效地處理字串，根據給定條件刪除字元。最終結果是在這些操作之後字串中最後剩下的字元。這種方法確保解決方案以O(N)的時間複雜度執行，其中N是二進位制字串的長度。
47 次瀏覽
