数据结构
网络
关系数据库管理系统 (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 次浏览
