資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢二進位制字串任意旋轉後，開頭和結尾連續放置的0的最大數量
在這個問題中，我們需要找到字串旋轉後開頭和結尾連續出現的0的最大數量。我們可以採用兩種方法來解決這個問題。第一種方法是找到給定字串的所有旋轉，並計算開頭和結尾的0的數量。第二種方法是計算字串中連續0的最大數量，並得到答案。
問題陳述 – 我們給定一個名為str的二進位制字串，其大小等於'len'。我們需要計算該字串任意旋轉後開頭和結尾連續出現的0的最大數量。
示例
輸入
str = ‘101’
輸出
1
解釋 – 讓我們計算字串每個旋轉中開頭和結尾0的總和。
101 – 開頭0的數量 = 0，結尾0的數量 = 0，總和 = 0
011 – 開頭0的數量 = 1，結尾0的數量 = 0，總和 = 1
110 – 開頭0的數量 = 0，結尾0的數量 = 1，總和 = 1
所有總和中的最大值為1。
輸入
str = ‘111111111111111’
輸出
0
解釋 -由於字串不包含0，因此字串的任何旋轉都不能在開頭或結尾處有0。
輸入
str = ‘110000010’
輸出
5
解釋
110000010 – 總和 = 1。
100000101 - 總和 = 0。
000001011 - 總和 = 5。
000010110 – 總和 =5。
000101100 – 總和 =5。
001011000 – 總和 =5。
010110000 – 總和 =5。
101100000 – 總和 =5。
011000001 – 總和 =1。
所有總和中的最大值為5。
方法1
在這種方法中，我們將找到二進位制字串的每個旋轉。之後，我們將計算開頭和結尾0的總和。我們將列印輸出中的最大總和值。
演算法
步驟1 – 初始化'count0'變數以儲存給定字串中0的總數。
步驟2 – 現在，我們需要計算給定字串中0的總數。使用迴圈遍歷字串，如果當前字元為'0'，則將count0的值增加1。
步驟3 – 如果count0和字串長度相等，則表示字串僅包含0。因此，返回字串的長度。
步驟4 – 現在，將二進位制字串與自身合併。
步驟5 – 接下來，初始化'maximumZeros'變數為零，以儲存開頭和結尾0的最大和。
步驟6 – 開始遍歷字串並定義startZeros和endZeros變數。
步驟7 – 使用迴圈查詢連續的開頭0。
步驟8 – 之後，在字串旋轉中查詢連續的結尾0。
步驟9 – 獲取startZeros和endZeros的總和。如果其小於開頭和結尾0的總和，則更新maximumZeros的值。
步驟10 – 返回maximumZeros變數的值。
示例
#include <bits/stdc++.h>
using namespace std;
int maxStartEndZeros(string str, int len){
// To store the total count of zeros in the string
int count0 = 0;
// Traverse binary string
for (int p = 0; p < len; ++p){
if (str[p] == '0')
count0++;
}
// If the string contains all zeros, return len
if (count0 == len){
return len;
}
// Merge string
str = str + str;
// to store maximum zeros at the start and end
int maximumZeros = 0;
// Traverse string
for (int p = 0; p < len; ++p){
// variables to store the count of zeros at the start and end
int startZeros = 0;
int endZeros = 0;
// Get starting zeros in the current rotation
for (int q = p; q < p + len; ++q){
if (str[q] == '0')
startZeros++;
else
break;
}
// Get end zeros in the current rotation
for (int q = p + len - 1; q >= p; --q){
if (str[q] == '0')
endZeros++;
else
break;
}
// Get maximum zeros
maximumZeros = max(startZeros + endZeros, maximumZeros);
}
// Return the final answer
return maximumZeros;
}
int main(){
// Given string
string str = "110000010";
// get string size
int len = str.size();
cout << "The maximum sum of start and end zeros in any rotation of binary string is " << maxStartEndZeros(str, len);
return 0;
}
輸出
The maximum sum of start and end zeros in any rotation of binary string is 5
時間複雜度 – O(N*N)，因為我們找到給定字串的所有旋轉。
空間複雜度 – O(N)，因為我們儲存了連線的字串。
方法2
在這種方法中，我們將找到給定二進位制字串中連續0的最大數量。此外，我們還將找到原始字串中開頭和結尾0的總和。我們將根據最大值在總和和連續0的最大數量之間進行選擇。
演算法
步驟1 – 最初，我們需要計算給定字串中0的總數。
步驟2 – 如果0的總數等於字串長度，則返回字串長度。
步驟3 – 定義'maximumZeros'和'maxConsZeros'變數以儲存最大值和連續0的最大數量。
步驟4 – 在迴圈遍歷字串時，如果當前字元為'0'，則將maxConsZeros的值增加1。
步驟5 – 如果當前字元為'1'，則更新maximumZeros變數的值並重新初始化maxConsZeros變數的值。
步驟6 – 定義left和right變數以儲存字串的索引。
步驟7 – 從開頭遍歷字串，直到我們得到'1'，並將left和maxConsZeros變數的值增加。
步驟8 - 從結尾遍歷字串，直到我們得到'1'，減少right的值，並增加maxConsZeros變數的值。
步驟9 – 更新後返回maximumZeros的值。
示例
#include <bits/stdc++.h>
using namespace std;
int maxStartEndZeros(string alpha, int len){
// To store the total count of zeros in the string
int count0 = 0;
// Traverse binary string
for (int p = 0; p < len; ++p){
if (alpha[p] == '0')
count0++;
}
// If string contains all zeros, return len
if (count0 == len){
return len;
}
// to store maximum zeros at start and end
int maximumZeros = 0;
// to store maximum consecutive zeros
int maxConsZeros = 0;
for (int p = 0; p < len; p++) {
if (alpha[p] == '0')
maxConsZeros++;
else {
maximumZeros = max(maximumZeros, maxConsZeros);
// reinitialize maxConsZeros
maxConsZeros = 0;
}
}
// Get maximum consecutive zeros in the string
maximumZeros = max(maximumZeros, maxConsZeros);
// Get sum of consecutive zeros at start and end
int left = 0, right = len - 1;
maxConsZeros = 0;
// Consecutive zeros at the left
while (alpha[left] != '1' && left < len) {
maxConsZeros++;
left++;
}
// Consecutive zeros at the right
while (alpha[right] != '1' && right >= 0){
maxConsZeros++;
right--;
}
// Get max value
maximumZeros = max(maximumZeros, maxConsZeros);
// return final result
return maximumZeros;
}
int main(){
// Given string
string str = "110000010";
// get string size
int len = str.size();
cout << "The maximum sum of start and end zeros in any rotation of binary string is " << maxStartEndZeros(str, len);
return 0;
}
輸出
The maximum sum of start and end zeros in any rotation of binary string is 5
時間複雜度 – O(N)，因為我們只迭代一次字串。
空間複雜度 – O(1)，因為我們沒有使用任何動態空間。
第二種方法在時間和空間複雜度方面都更最佳化，因為我們只遍歷一次字串，而沒有使用任何額外的空間。程式設計師還可以嘗試查詢字串開頭和結尾處'1'的最大數量，以獲得更多類似問題的練習。
瀏覽量 118
