資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學Python3程式：查詢二進位制字串任意旋轉後開頭和結尾連續0的最大數量
在這個問題中，我們將編寫Python程式碼來計算二進位制字串任意旋轉後開頭和結尾連續0的最大和。
問題的解決方案可以分為兩個部分。第一部分是查詢字串的所有旋轉。第二部分是在二進位制字串的所有旋轉中查詢開頭和結尾的連續零。
解決此問題的另一種方法是計算最大連續零的個數。
問題陳述 – 我們需要找到給定二進位制字串任意旋轉後開頭和結尾連續零的最大總數。
示例
輸入
str = "00100100"
輸出
4
解釋 – 讓我們取給定字串的所有旋轉。
00100100 – 開頭零 – 2，結尾零 – 2，總和 – 4。
01001000 – 開頭零 – 1，結尾零 – 3，總和 – 4。
10010000 – 開頭零 – 0，結尾零 – 4，總和 – 4。
00100001 – 開頭零 – 2，結尾零 – 0，總和 – 2。
01000010 – 開頭零 – 1，結尾零 – 1，總和 – 2。
10000100 – 開頭零 – 0，結尾零 – 2，總和 – 2。
00001001 – 開頭零 – 4，結尾零 – 0，總和 – 4。
00010010 – 開頭零 – 3，結尾零 – 1，總和 – 4。
輸入
str = ‘00000000’
輸出
8
解釋 – 由於字串包含全部為零，答案等於字串長度。
輸入
str = ‘111111111’
輸出
0
解釋 – 由於字串包含全部為‘1’，答案為0。
方法一
我們將字串與自身連線起來，並從每個索引開始獲取長度為N的子字串以獲得旋轉字串。之後，我們將計算開頭和結尾零的總和。
演算法
步驟1 – 定義變數`totalOnes`來儲存給定二進位制字串中‘1’的個數。
步驟2 – 使用迴圈遍歷字串。如果str[p]等於‘1’，則將totalOnes加1。
步驟3 – 如果變數totalOnes的值為零，則列印字串的長度，因為字串只包含零。
步驟4 – 使用`+=`運算子將字串`str`與自身連線起來，並定義變數`maxZeros`。
步驟5 – 遍歷連線後的字串。定義變數`startZeros`和`endZeros`。
步驟6 – 遍歷從p到p + len索引的子字串。如果索引q處的字元不是‘0’，則中斷迴圈。否則，將totalZeros加1。
步驟7 – 遍歷從p + len -1到p的子字串。如果索引q處的字元不是‘0’，則中斷迴圈。否則，將`endZeros`的計數加1。
步驟8 – 獲取開頭和結尾零的總和。
步驟9 – 使用max()方法從sum和maxZeros中獲取最大值。
步驟10 – 列印maxZeros的值。
示例
def countStartEndZeros(str, len):
# variable to store count of ones
totalOnes = 0
# Traverse the string
for p in range(len):
if (str[p] == '1'):
totalOnes += 1
# If the string doesn't contain any 1, print the len value
if (totalOnes == 0):
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(len))
return
# Merge the string
str += str
# Maximum zeros
maxZeros = 0
# Traverse the merged string
for p in range(len):
startZeros = 0
endZeros = 0
# total zeros at start
for q in range(p, p + len):
if (str[q] != '0'):
break
else:
startZeros += 1
# total zeros at the end
for q in range(p + len - 1, p - 1, -1):
if (str[q] != '0'):
break
else:
endZeros += 1
# sum of zeros at start and end
sum = startZeros + endZeros
# change maxZeros if the sum is greater
maxZeros = max(sum, maxZeros)
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(maxZeros))
if __name__ == "__main__":
# Given string
str = "00100100"
str_size = len(str)
countStartEndZeros(str, str_size)
輸出
The maximum sum of starting and end zeros in the rotation of the string is - 4
時間複雜度 – 查詢每個字串旋轉為O(N*N)。
空間複雜度 – 儲存連線後的字串為O(N)。
方法二
在這種方法中，我們將根據對連續零的觀察來解決問題。問題的答案是原始二進位制字串中最大連續零或開頭和結尾零的總和。
演算法
步驟1 – 如果二進位制字串中‘1’的總數為0，則列印字串長度。
步驟2 – 定義變數`maxi`來儲存任意旋轉中開頭和結尾零的最大和。
步驟3 – 定義變數`zeroConsecutive`來儲存字串中最大連續零的個數。
步驟4 – 遍歷字串，如果第p個索引處的字元為‘0’，則將`zeroConsecutive`加1。否則，使用max()方法從`maxi`和`zeroConsecutive`中獲取最大值，並將結果儲存到`maxi`中。同時，將`zeroConsecutive`重新初始化為零。
步驟5 – 接下來，查詢字串開頭和結尾連續零的總數。
步驟6 – 如果`zeroConsecutive`的值大於`maxi`，則再次更新`maxi`的值。
步驟7 – 列印`maxi`變數的值。
示例
def countStartEndZeros(binStr, bin_size):
# one counts
cnt1 = 0
for p in range(bin_size):
if (binStr[p] == '1'):
cnt1 += 1
# print len if string size is equal to zero count
if (cnt1 == bin_size):
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(bin_size))
return
# maximum sum
maxi = 0
zeroConsecutive = 0
for p in range(bin_size):
if (binStr[p] == '0'):
zeroConsecutive += 1
else:
maxi = max(maxi, zeroConsecutive)
zeroConsecutive = 0
# Change value of maxi
maxi = max(maxi, zeroConsecutive)
# start and end zeros
left = 0
right = bin_size - 1
zeroConsecutive = 0
# lef tzeros
while (binStr[left] != '1' and left < bin_size):
zeroConsecutive += 1
left += 1
# right zeros
while (binStr[right] != '1' and right >= 0):
zeroConsecutive += 1
right -= 1
# Change value of maxi
maxi = max(maxi, zeroConsecutive)
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(maxi))
if __name__ == "__main__":
# Given string
str = "00100100"
str_size = len(str)
countStartEndZeros(str, str_size)
輸出
The maximum sum of starting and end zeros in the rotation of the string is - 4
時間複雜度 – 遍歷字串為O(N)。
空間複雜度 – O(1)
程式設計師應該始終嘗試找到問題的最佳化解決方案。首先，我們可以使用我們在第一種方法中所做的天真方法開始解決問題。之後，我們可以進一步最佳化它，就像我們在第二種方法中所做的那樣。
瀏覽量：113
