数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中查找使数组“美丽”所需的最小操作数
在这个问题中，我们得到一个二进制数组bin[]，它包含n个二进制值（0和1）。我们的任务是找到使数组“美丽”所需的最小操作数。
“美丽”数组是一种特殊的二进制数组，它具有交替的0和1模式。
**问题描述** − 我们需要找到使数组“美丽”所需的最小操作次数。一个操作包括以下步骤：
**步骤1** − 将数组分成两半。
**步骤2** − 反转其中一半。
**步骤3** − 将两半重新连接。
我们将计算使数组成为“美丽”数组所需的总操作次数。
让我们来看一个例子来理解这个问题：
输入
bin[] = {1, 0, 1, 0, 0, 1}输出
1
解释
我们将分割数组，创建一个子数组bin[4, 5]，将其反转，然后重新连接。
解决方案方法
问题的解决方案基于查找最小交换次数，这等于连续零的个数。基本情况是：
如果数组大小为1，则它是一个“美丽”数组。如果数组大小为奇数，则它永远不可能是一个“美丽”数组。
对于所有偶数长度，我们将检查连续零或一的总数，这将是需要执行的操作次数。
算法
初始化 − zeroCount , oneCount, consZero = 0
**步骤1** − if ( n = 1), 返回 0
**步骤2** − if (n%2 != 0), 返回 -1。
**步骤3** − 循环 i -> 0 到 n-1。
**步骤3.1** − if bin[i] == bin[i+1] == 0, consZero++。
**步骤4** − if bin[n-1] == bin[0] == 0, consZero++。
**步骤5** − 返回 consZero。
程序演示了我们解决方案的工作原理：
示例
#include <iostream>
using namespace std;
int minOperations(int bin[], int n) {
if(n == 1)
return 0;
if(n%2 != 0)
return -1;
int consZero = 0;
for (int i = 0; i < n; ++i) {
if (i + 1 < n) {
if (bin[i] == 0 && bin[i + 1] == 0)
consZero++;
}
}
if (bin[0] == bin[n - 1] && bin[0] == 0)
consZero++;
return consZero;
}
int main() {
int bin[] = { 1, 0, 1, 0, 0, 1};
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The minimum operations needed to make an Array beautiful is "<<minOperations(bin, n);
return 0;
}输出
The minimum operations needed to make an Array beautiful is 1
更新于：2021年3月12日
518 次浏览
广告