資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究最大化給定二進位制陣列中需要翻轉的 0 的數量，使得兩個 1 之間至少有 K 個 0
二進位制陣列是一種特殊的陣列，只包含數字 0 和 1。在這個問題中，我們給定一個二進位制陣列和整數 K。我們的任務是計算在給定二進位制陣列中可以翻轉為 1 的最大 0 的數量，使得兩個 1 之間至少有 K 個 0。
示例
Input 1: arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }, K = 2
Output 1: yes
解釋
上述陣列中第 3 個和第 6 個索引是唯一有效的索引，可以翻轉它們，以保證兩個 1 之間至少有 2 個零。因此，結果陣列為 {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}
Input 2: arr[] = {0, 1, 0, 0, 0, 1}, k = 1
Output 2: 1
解釋
上述陣列中第 3 個索引是唯一有效的翻轉索引。
方法
我們已經看到了上面給定陣列和整數 k 的示例，讓我們來看一下方法 -
這種方法的思路是計算兩個 1 之間的連續零的個數，並檢查是否適合在它們之間將一些零翻轉為一。假設兩個 1 之間有 X 個 0。根據觀察，可以在它們之間翻轉的 0 的數量為 (X-K) / (K+1)。因此，遍歷陣列並記錄每個 1 對之間有多少個連續的 0。然後，將可以翻轉的 0 的數量新增到變數 count 中，這就是所需的答案。
讓我們逐步討論這種方法 -
首先，我們將建立一個函式 `onesCount`，它將給定的陣列 `arr` 和整數 `K` 作為引數，並將所需的整數 `count` 作為返回值。
建立變數 count 和 lastIdx。
將變數 count 初始化為 0，以儲存翻轉的 0 的數量。
將變數 lastIdx 初始化為 (-(K+1))，以儲存陣列中值為 1 的最後一個索引。
使用 for 迴圈遍歷陣列，如果當前元素為 1，則檢查兩個連續的 1 之間是否有足夠的 0 來在其間新增另一個 1。最後，更新值為 1 的最後一個索引的值。
編寫計算陣列最後一段 0 的條件，並將其新增到變數 count 中。
最後，返回最終答案 count。
示例
以下是計算最大化需要翻轉的 0 的數量的 C++ 程式，使得兩個 1 之間至少有 k 個 0。
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of the maximum number of 0s to be filliped
int onesCount(int arr[], int n, int k){
int count = 0; // Stores the count of 1's
int lastIdx = -(k + 1); // Stores the last index of value 1
// Traverse the array using for loop
for (int i = 0; i < n; i++) {
// If the current element is 1
if (arr[i] == 1) {
// Verify whether there are enough 0s between two consecutive 1s to add another 1 in between them.
if (i - lastIdx - 1 >= 2 * (k - 1)) {
count += (i - lastIdx - 1 - k) / (k + 1);
}
lastIdx = i; // Update the last index of the value 1 of the array
}
}
// condition to include the last section of 0s in the array
count += (n - lastIdx - 1) / (k + 1);
// Return the answer
return count;
}
int main(){
int arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }; // given array
int N = sizeof(arr) / sizeof(arr[0]); //getting size of an array
int K = 2; //given integer
// Call the function
int result = onesCount(arr, N, K);
cout<< "The count of Maximum filliped of 0's is "<< result ;
return 0;
}
輸出
The Count of Maximum filliped of 0's is 2
時間和空間複雜度
上述程式碼的時間複雜度為 O(N)，因為我們只遍歷一次陣列。其中 N 是給定陣列的大小。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。
結論
在本教程中，我們實現了一個程式，用於查詢在給定二進位制陣列中最大化需要翻轉的 0 的數量，使得兩個 1 之間至少有 K 個 0。透過計算兩個 1 之間的連續零，並檢查是否適合在它們之間將一些零翻轉為一，來解決此問題。時間複雜度為 O(N)，空間複雜度為 O(1)。其中 N 是字串的大小。
95 次瀏覽
