資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究二進位制字串中最長非遞減子序列
在這個問題中，我們需要找到給定字串中最長的非遞減子序列。
非遞減的意思是字元應該相同或按降序排列。由於二進位制字串只包含“0”和“1”，因此結果字串應該以“1”開頭，以“0”結尾，或者以“0”或“1”開頭和結尾。
為了解決這個問題，我們將計算字串每個位置的字首“1”和字尾“0”，並找到字首“1”和字尾“0”的最大和。
問題陳述 - 我們給定一個二進位制字串str。我們需要找到給定字串中最長的非遞減子序列。
示例
Input – str = "010100"
Output – 4
解釋
最長的非遞減子序列是“1100”。
Input – str = "010110010"
Output – 6
解釋
最長的非遞減子序列是“111000”。
Input – str = ‘00000000’
Output – 8
解釋
最長的非遞減子序列是“00000000”，它等於給定的字串。
方法一
在這種方法中，我們將為每個索引儲存字首“1”和字尾“0”的計數。之後，我們從兩個陣列的相同索引獲取值，將它們相加，並找到最大和。
演算法
步驟1 - 定義pre1s和suffix0s陣列來儲存字首1和字尾0。並將所有陣列元素初始化為0。
步驟2 - 使用for迴圈遍歷字串並計算每個索引的字首1。如果i > 0，則將前一個元素的值新增到當前元素。
步驟3 - 如果當前字元是“1”，則將pre1s[i]的當前值加1。
步驟4 - 現在，計算給定字串中的字尾0。從末尾開始遍歷字串。
步驟5 - 如果“i”的值不等於“n – 1”，則獲取“i + 1”元素的值並將其新增到當前元素。
步驟6 - 如果當前元素是“0”，則將當前元素加1。
步驟7 - 現在，將“res”變數初始化為0。
步驟8 - 使用迴圈遍歷“pre1s”和“suffix0s”。
步驟9 - 從“pre1s”和“suffix0s”陣列的第i個索引獲取值，並將它們相加。如果“sum”大於“res”變數的當前值，則將“res”變數的值更改為“sum”值。
步驟10 - 返回“res”變數的值。
示例
對於輸入“010100”，字首陣列將為[0, 1, 1, 2, 2, 2]，字尾0陣列將為[4, 3, 3, 2, 2, 1]。和陣列將為[4, 4, 4, 4, 4, 3]，和陣列中的最大值為4。所以答案將是4。
#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
// To store the prefix count of '1's and suffix count of '0's
int pre1s[n] = {0},
suffix0s[n] = {0};
for (int i = 0; i < n; i++){
// get the prefix count of '1's
if (i > 0){
pre1s[i] += pre1s[i - 1];
}
// If the current character is '1', then update the pre1s array by adding 1; else, keep it as it is.
if (str[i] == '1'){
pre1s[i] += 1;
}
}
// get suffix count of '0's
for (int i = n - 1; i >= 0; i--) {
// add the suffix count of '0's
if (i != n - 1)
suffix0s[i] += suffix0s[i + 1];
// If the current character is '0', then update the suffix0s array by adding 1; else, keep it as it is.
if (str[i] == '0')
suffix0s[i] += 1;
}
// to store the final result value
int res = 0;
// iterate over the pre1s[] and suffix0s[] array and find the maximum value of pre1s[i] + suffix0s[i]
for (int i = 0; i < n; i++){
res = max(res, pre1s[i] + suffix0s[i]);
}
// Return the result
return res;
}
// Driver Code
int main(){
string str = "010100";
int N = str.length();
cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
return 0;
}
輸出
The length of the longest non-increasing subsequence in the given binary string is - 4
時間複雜度 - O(N)，因為我們需要初始化字首1和字尾0陣列。
空間複雜度 - O(N)，因為我們將字首1和字尾0儲存在陣列中。
方法二
在這種方法中，我們將首先計算零的總數。之後，我們開始遍歷字串並繼續計數“1”並在找到0時減少“0”。此外，我們在每次迭代中對零和一的計數求和，並找到最大的結果值。
演算法
步驟1 - 定義“count1”、“count0”和“res”變數並將它們初始化為0，分別儲存1、0和最終結果的計數。
步驟2 - 透過遍歷字串並將結果儲存在“count0”變數中來計算零的總數。
步驟3 - 現在，使用迴圈迭代字串。
步驟4 - 在迴圈中，如果當前字元是“1”，則將“count1”的值增加1，否則將“count0”的值減少1。
步驟5 - 此外，將“res”和“count0 + count1”中的最大值儲存到“res”變數中。
步驟6 - 當迴圈終止時，返回“res”變數的值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
int count1 = 0, count0 = 0;
int res = 0;
// counting total zeros in the string
for (int i = 0; i < n; i++){
if (str[i] == '0')
count0++;
}
// counting 1s from left, subtracting zeros from total zeros and adding both counts.
for (int i = 0; i < n; i++){
if (str[i] == '1')
count1++;
else
count0--;
res = max(res, count1 + count0);
}
return res;
}
int main(){
string str = "010110010";
int N = str.length();
cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
return 0;
}
輸出
The length of the longest non-increasing subsequence in the given binary string is - 6
時間複雜度 - O(N)，因為我們計算字串中零的總數並遍歷字串以找到最長的子序列。
空間複雜度 - O(1)
結論
在這裡，兩種方法的時間複雜度相同，但空間複雜度不同。第二種方法使用常量空間，因為我們優化了程式碼，但第一種方法使用動態空間來儲存字首1和字尾0的總數。
211 次瀏覽
