极客笔记C++ 将一个二进制字符串的所有字符转换为0的最小成本
一个二进制字符串是仅包含二进制数字的字符串。在这个问题中，我们给定一个二进制字符串，一个数组表示从第i个索引开始，每个索引上的1可以翻转的最后一个索引，翻转需要的成本在另一个成本数组中给出。我们需要对字符串执行一些操作，使字符串完全变为0。
示例
让我们通过一个例子来理解这个问题-
输入
string str = "101011"
int arr[] = {1, 2, 2, 4, 5, 5};
int cost[] = {3, 9, 2, 3, 7, 2}
输出
19
说明
在这里，我们必须翻转第一个位，所以成本将为3，接下来的0也将被翻转，然后我们必须再翻转一次，成本将为3 + 9，即12。再次，下一个1只被翻转一次，所以不需要再翻转它。这里没有翻转下一个0，所以也不需要再翻转它。
然后我们需要翻转倒数第二个1，它也将翻转下一个1，总成本为7，总成本为19。
方法1
在这个方法中，我们将使用优先队列来指示我们需要查找翻转影响的索引。
示例
#include <bits/stdc++.h>
using namespace std;
// function to get the required cost
int costReq(string s, int size, int arr[], int cost[]){
// store the elements in the priority queue all the elements will be stored in the smallest first side
priority_queue<int, vector<int>, greater<int>> pq;
// variable to store the number of times the string is flipped
int countFlips = 0;
// variable to store the required minimum cost or to store the answer
int ans = 0;
// using for loop traversing over the string
for(int i = 0; i < size; i++){
// remove all the values from the priority queue which have value less than current index
while(pq.empty() == false && pq.top() < i){
// poping the elements
pq.pop();
countFlips--; // reducing the count of the flips
}
// updating the value of the current character based on the number of times it have been flipped
if(countFlips & 1){
// if the count of the flips is odd then change the current index
if(s[i] == '1'){
s[i] = '0';
} else {
s[i] = '1';
}
}
// after updation if the current index is non-zero then we need to flip it
if (s[i] == '1'){
// update the count of the flips
countFlips++;
// add number of index upto which we are flipping
pq.push(arr[i]);
// add cost to answer
ans += cost[i];
}
}
return ans; // return the final answer
}
int main(){
string str = "101011"; // given string
int arr[] = {1, 2, 2, 4, 5, 5}; // given index array
int cost[] = {3, 9, 2, 3, 7, 2}; // given cost array
int n = str.length(); // getting length of the string
// calling to the function to get the answer
cout << "The minimum cost required to flip all the ones to zeros is: "<<costReq(str, n, arr, cost)<<endl;
return 0;
}
输出
The minimum cost required to flip all the ones to zeros is: 19
时间和空间复杂度
上述代码的时间复杂度为O(N * log(N))，其中N是给定字符串的大小，我们得到对数因子是由于优先队列。
上述代码的空间复杂度为O(N)，因为我们使用额外的空间作为优先队列。
方法2
在这个方法中，我们将使用差分数组来实现代码。
示例
#include <bits/stdc++.h>
using namespace std;
// function to get the required cost
int costReq(string s, int size, int arr[], int cost[]){
// vector to work as the difference array
vector<int> diff_arr(size + 1);
// variable to store the number of times the string is flipped
int countFlips = 0;
// variable to store the required minimum cost or to store the answer
int ans = 0;
// using for loop traversing over the string
for(int i = 0; i < size; i++){
// updating the value of the flips using the differ rence array
countFlips += diff_arr[i];
// updating the value of the current character based on the number of times it has been flipped
if(countFlips & 1){
// if the count of the flips is odd then change the current index
if(s[i] == '1'){
s[i] = '0';
} else {
s[i] = '1';
}
}
// after updation if the current index is non-zero then we need to flip it
if (s[i] == '1'){
// update the count of the flips
countFlips++;
// update the value of the difference array on the next index of the ending
diff_arr[arr[i] + 1]--;
// add cost to answer
ans += cost[i];
}
}
return ans; // return the final answer
}
int main(){
string str = "101011"; // given string
int arr[] = {1, 2, 2, 4, 5, 5}; // given index array
int cost[] = {3, 9, 2, 3, 7, 2}; // given cost array
int n = str.length(); // getting lenth of the string
// calling to the function to get the answer
cout << "The minimum cost required to flip all the ones to zeros is: "<<costReq(str, n, arr, cost)<<endl;
return 0;
}
输出
The minimum cost required to flip all the ones to zeros is: 19
时间和空间复杂度
上述代码的时间复杂度为O(N)，因为我们只是遍历字符串并维护一个数组。
上述代码的空间复杂度为O(N)，因为我们维护了差分数组。
结论
在本教程中，我们实现了一个程序，用于找到将给定的二进制字符串完全转换为零所需的最小成本。我们给出了一个数组，其中每个索引代表如果我们翻转此索引，向前的元素将被翻转的索引数，并且给出了成本。我们实现了两种方法，一种是使用优先队列和O(N*log(N))时间复杂度的方法，另一种是使用差分数组和O(N)时间复杂度的方法。