資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Java程式：查詢二進位制字串任意旋轉後開頭和結尾連續0的最大數量
在本問題中，我們將編寫Java程式碼來查詢任何字串旋轉後開頭和結尾連續零的最大和。首先，我們將使用一種簡單的方法來解決這個問題，該方法生成二進位制字串的所有旋轉並計算開頭和結尾連續的零。之後，我們將學習一種最佳化的演算法來計算最大連續零。
問題陳述 – 在這裡，我們有一個大小為N的字串，其中只包含0和1字元。我們需要找到給定字串任何旋轉後開頭和結尾連續零的最大和。
示例
輸入
str = ‘001’
輸出
2
解釋 – 讓我們計算每次旋轉中開頭和結尾零的總和。
在“001”中，開頭連續零為2，結尾零為01。因此，最終總和為2。
在“011”中，開頭連續零為1，結尾零為1。因此，最終總和為2。
在“100”中，開頭連續零為0，結尾零為2。因此，最終總和為2。
最大和為2。
輸入
str = ‘11’
輸出
0
解釋 – 字串不包含任何零。
輸入
str = ‘1000001’
輸出
5
解釋
1000001 – 開頭零 = 0，結尾零 = 0，總和 = 0。
0000011 – 開頭零 = 5，結尾零 = 0，總和 = 5。
0000110 – 開頭零 = 4，結尾零 = 1，總和 = 5。
0001100 – 開頭零 = 3，結尾零 = 2，總和 = 5。
0011000 – 開頭零 = 2，結尾零 = 3，總和 = 5。
0110000 – 開頭零 = 1，結尾零 = 4，總和 = 5。
1100000 – 開頭零 = 0，結尾零 = 5，總和 = 5。
最終總和為5。
方法1
這是解決問題的簡單方法。首先，我們將字串與自身合併。之後，我們將從第p個索引開始，長度等於原始字串的子字串。它為我們提供了旋轉二進位制字串p次後得到的最終字串。
演算法
步驟1 – 將“cnt0”變數初始化為0，以儲存給定字串中零的計數。
步驟2 – 如果“cnt0”和“len”相等，則返回“len”，因為字串只包含零。
步驟3 – 定義字串s，並將alpha + alpha儲存在其中。
步驟4 – 定義“maxZeros”變數來儲存開頭和結尾零的最大和。
步驟5 – 使用迴圈進行總迭代次數等於字串長度。在迴圈中，“left”和“right”變數用於儲存最大連續開頭零和結尾零。
步驟6 – 從第m個索引到(m + len)個索引開始遍歷字串。使用charAt()方法訪問第m個索引的字元，如果它等於“0”，則將“left”變數的值增加1。否則，使用“break”關鍵字終止迴圈。
步驟7 – 從(m + len -1)個索引到m個索引開始遍歷字串，直到我們得到零為止，增加“right”變數的值。
步驟8 – 對left和right求和。如果總和大於其值，則更新maxZeros。
步驟9 – 返回maxZeros變數的值，該變數包含任何字串旋轉後開頭和結尾零的最大和。
示例
import java.util.*;
public class Main {
static int getMaxZeros(String alpha, int len) {
// count zeros in the string
int cnt0 = 0;
// Traverse the string
for (int m = 0; m < len; ++m) {
if (alpha.charAt(m) == '0')
cnt0++;
}
// If total zeros are equal to len, return len
if (cnt0 == len) {
return cnt0;
}
// Merge string to find rotations
String s = alpha + alpha;
// to store the maximum sum of zeros
int maxZeros = 0;
// Traverse string
for (int m = 0; m < len; ++m) {
// to store zeros at the start and end
int left = 0;
int right = 0;
// calculate starting zeros in the current rotation
for (int n = m; n < m + len; ++n) {
if (s.charAt(n) == '0') {
left++;
} else {
break;
}
}
// Calculate ending zeros
for (int n = m + len - 1; n >= m; --n) {
if (s.charAt(n) == '0') {
right++;
} else {
break;
}
}
// Get max value
maxZeros = Math.max(left + right, maxZeros);
}
return maxZeros;
}
public static void main(String[] args) {
String alpha = "10001";
// string length
int len = alpha.length();
System.out.println("The maximum sum of start and end zeros in the rotations of the given string is - "
+ getMaxZeros(alpha, len));
}
}
輸出
The maximum sum of start and end zeros in the rotations of the given string is - 3
時間複雜度 – O(N^2)，因為長度為N的字串可以有總共N個旋轉。
空間複雜度 – O(N)，因為我們儲存合併後的字串以使用它獲得旋轉。
方法2
這種方法計算給定字串中連續零的總數。當我們旋轉字串時，我們可以觀察到開頭和結尾連續零的總和保持不變。
例如，當我們旋轉字串“0000011”時，我們得到字串“0000110”，其開頭和結尾零的總和等於連續零。
演算法
步驟1 – 在第一步中，計算字串中零的總數，如果零的計數等於字串長度，則返回長度值。
步驟2 – maxZeros變數用於儲存開頭和結尾連續零的最大和。此外，maxConsZeros變數用於儲存最大連續零的計數。
步驟3 – 透過遍歷字串來計算字串中最大連續的零。
步驟4 – 也更新maxZeros變數的值。
步驟5 – 計算字串開頭連續零的總數。另外，計算字串結尾連續零的總數。
步驟6 – 如果開頭和結尾連續零的總和大於maxZeros，則更新maxZeros值，並返回更新後的值。
示例
import java.util.*;
public class Main {
static int getMaxZeros(String alpha, int len) {
// count zeros in the string
int cnt0 = 0;
// Traverse the string
for (int m = 0; m < len; ++m) {
if (alpha.charAt(m) == '0')
cnt0++;
}
// If total zeros are equal to len, return len
if (cnt0 == len) {
return cnt0;
}
// to store maximum sum of zeros
int maxZeros = 0;
// to store max consecutive zeros
int maxconZeros = 0;
for (int m = 0; m < len; m++) {
if (alpha.charAt(m) == '0')
maxconZeros++;
else {
// update max consecutive zeros
maxZeros = Math.max(maxZeros, maxconZeros);
maxconZeros = 0;
}
}
// Change max zeros if required
maxZeros = Math.max(maxZeros, maxconZeros);
// Calculate the sum of zeros at the start and end
int left = 0, right = len - 1;
maxconZeros = 0;
// total zeros at start
while (alpha.charAt(left) != '1' && left < len) {
maxconZeros++;
left++;
}
// total zeros at end
while (alpha.charAt(right) != '1' && right >= 0) {
maxconZeros++;
right--;
}
// Change the maximum sum of zeros
maxZeros = Math.max(maxZeros, maxconZeros);
return maxZeros;
}
public static void main(String[] args) {
String alpha = "10001";
// string length
int len = alpha.length();
System.out.println("The maximum sum of start and end zeros in the rotations of the given string is - "
+ getMaxZeros(alpha, len));
}
}
輸出
The maximum sum of start and end zeros in the rotations of the given string is - 3
時間複雜度 – O(N)，用於遍歷給定的二進位制字串。
空間複雜度 – O(1)
127 次瀏覽
