给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作： 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。 返回使字符串内所有字符 相等 需要的 最小成本 。

首先，如果字符串中有不止一种字符，则无法将所有字符变为相等的，因此最小成本为-1。

接下来，我们只考虑字符串中只有一种字符的情况。因为我们只能通过反转来改变字符串，因此我们可以首先计算出反转所有前缀或后缀所需的成本，然后选择最小的那个。例如，假设字符串是00000，我们可以计算出反转前缀的成本分别为1、2、3、4、5，反转后缀的成本分别为5、4、3、2、1，因此我们选择反转前缀的成本最小，即1。

代码如下：

def minCost(s: str) -> int:
    n = len(s)
    if len(set(s)) > 1:
        return -1
    cost = [0] * (n + 1)
    for i in range(1, n + 1):
        if s[i-1] == '0':
            cost[i] = cost[i-1] + i
        else:
            cost[i] = cost[i-1]
    min_cost = float('inf')
    for i in range(n+1):
        min_cost = min(min_cost, cost[i] + (n-i)*(n-i+1)//2 - (cost[n]-cost[i]))
    return min_cost

其中，cost数组记录了反转前缀所需的成本，min_cost记录了反转前缀和反转后缀所需的最小成本。时间复杂度为O(n)。

相关问题

c语言实现：给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作： 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。 返回使字符串内所有字符 相等 需要的 最小成本 。

以下是C语言实现代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int minCost(char *s) {
    int n = strlen(s);
    int i, j, cnt0 = 0, cnt1 = 0;
    for (i = 0; i < n; i++) {
        if (s[i] == '0') {
            cnt0++;
        } else {
            cnt1++;
        }
    }
    if (cnt0 > 0 && cnt1 > 0) {  // 如果有不止一种字符，则无法将所有字符变为相等的
        return -1;
    }
    int *cost = (int *)malloc(sizeof(int) * (n + 1));
    memset(cost, 0, sizeof(int) * (n + 1));
    for (i = 1; i <= n; i++) {
        if (s[i-1] == '0') {
            cost[i] = cost[i-1] + i;
        } else {
            cost[i] = cost[i-1];
        }
    }
    int min_cost = INT_MAX;
    for (i = 0; i <= n; i++) {
        min_cost = min(min_cost, cost[i] + (n-i)*(n-i+1)/2 - (cost[n]-cost[i]));
    }
    free(cost);
    return min_cost;
}

int main() {
    char s[] = "00000";
    printf("%d\n", minCost(s));
    return 0;
}

其中，cost数组记录了反转前缀所需的成本，min_cost记录了反转前缀和反转后缀所需的最小成本。时间复杂度为O(n)。

用c++编译程序，给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作： 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。 返回使字符串内所有字符 相等 需要的 最小成本 。 反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然

这道题可以使用贪心算法解决。考虑将整个字符串变成全0或全1，那么我们需要统计出每个位置变成0或1的代价。假设我们要将字符串变成全0，那么对于位置i，它变成0的代价为i+1，变成1的代价为n-i。同样的，如果我们要将字符串变成全1，那么对于位置i，它变成1的代价为i+1，变成0的代价为n-i。

我们可以通过比较这两个代价，选择更小的那个进行翻转。具体来说，我们从左往右遍历每个位置，统计变成0或1的代价，并记录当前的最小代价。然后再从右往左遍历每个位置，统计变成0或1的代价，并记录当前的最小代价。最后比较两个方向的最小代价，选择更小的那个进行翻转，直到整个字符串变成全0或全1。

以下是C++代码实现：

int minCost(string s) {
    int n = s.size();
    int cost0 = 0, cost1 = 0;
    int res = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            cost0 += i + 1;
        } else {
            cost1 += i + 1;
        }
    }
    res = min(cost0, cost1);
    int cur0 = cost0, cur1 = cost1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '0') {
            cur0 += n - i;
            cur1 -= n - i;
        } else {
            cur1 += n - i;
            cur0 -= n - i;
        }
        res = min(res, min(cur0, cur1));
    }
    return res;
}

时间复杂度：O(n)