資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時裝研究
法律研究使用 C++，求解使陣列中所有元素變成 0 所需的最少操作次數。
問題陳述
給定一個大小為 N 的陣列，其中每個元素要麼為 1，要麼為 0。任務是計算使所有元素都變成 0 所需的最少操作次數。可以執行以下操作 −
如果某個元素為 1，則可以將其值更改為 0，那麼 −
如果相鄰的下一個元素是 1，它會自動轉換為 0
如果相鄰的下一個元素已經是 0，則不會發生任何事。
If arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1} then 4
operation are required to make all elements zero演算法
1.If the current element is 1 then increment the count and search for the next 0 as all consecutive 1’s will be automatically converted to 0. 2. Return final count
示例
#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int performMinOperation(int *arr, int n){
int i, cnt = 0;
for (i = 0; i < n; ++i) {
if (arr[i] == 1) {
int j;
for (j = i + 1; j < n; ++j) {
if (arr[j] == 0) {
break;
}
}
i = j - 1;
++cnt;
}
}
return cnt;
}
int main(){
int arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1};
cout << "Minimum required operations = " << performMinOperation(arr, SIZE(arr)) << endl;
return 0;
}輸出
當編譯並執行上述程式時，它會生成以下輸出 −
Minimum required operations = 4
更新於： 31-10-2019
328 次瀏覽
廣告