题目描述
给你一个下标从 0 开始、长度为 n
的二进制字符串 s
,你可以对其执行两种操作:
选中一个下标 i
并且反转从下标 0
到下标 i
(包括下标 0
和下标 i
)的所有字符,成本为 i + 1
。
选中一个下标 i
并且反转从下标 i
到下标 n - 1
(包括下标 i
和下标 n - 1
)的所有字符,成本为 n - i
。
返回使字符串内所有字符 相等 需要的 最小成本。
反转 字符意味着:如果原来的值是 '0'
,则反转后值变为 '1'
,反之亦然。
样例
输入:s = "0011"
输出:2
解释:执行第二种操作,选中下标 i = 2,可以得到 s = "0000",成本为 2。
可以证明 2 是使所有字符相等的最小成本。
输入:s = "010101"
输出:9
解释:执行第一种操作,选中下标 i = 2,可以得到 s = "101101",成本为 3。
执行第一种操作,选中下标 i = 1,可以得到 s = "011101",成本为 2。
执行第一种操作,选中下标 i = 0,可以得到 s = "111101",成本为 1。
执行第二种操作,选中下标 i = 4,可以得到 s = "111110",成本为 2。
执行第一种操作,选中下标 i = 5,可以得到 s = "111111",成本为 1。
使所有字符相等的总成本等于 9。可以证明 9 是使所有字符相等的最小成本。
限制
1 <= s.length == n <= 10^5
s[i]
为'0'
或'1'
。
算法1
(动态规划,前后缀分解) $O(n)$
- 显然,最优策略一定存在一个位置 $p$,满足 $p$ 之前都是通过前缀变更的字符串,$p + 1$ 之后都是通过后缀变更的字符串。
- 可以通过动态规划预处理所有前缀位置变更的成本。设 $f_0(i)$ 表示将前 $i$ 个字符都变更为 $0$ 所需要成本,$f_1(i)$ 表示将前 $i$ 个字符都变更为 $1$ 所需要的成本。$i$ 的有效下标从 $1$ 开始。
- 初始时 $f_0(0) = f_1(0) = 0$,其余待定。
- 转移时,如果当前位置为 $0$,则 $f_0(i) = \min(f_0(i - 1), f_1(i - 1) + i - 1)$;$f_1(i) = \min(f_0(i - 1) + i, f_1(i - 1) + 2i - 1)$。如果当前位置为 $1$ 转移类似。
- 然后,从后往前遍历字符串,遍历过程中,仿照上述过程处理每个后缀变更所需要的成本,然后前后缀两个成本累加更新答案。
时间复杂度
- 两轮动态规划,每一轮动态规划的状态数为 $O(n)$,转移时间为常数,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储动态规划的状态。
C++ 代码
#define LL long long
class Solution {
public:
LL minimumCost(string s) {
const int n = s.size();
vector<LL> f0(n + 1), f1(n + 1);
f0[0] = f1[0] = 0;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '0') {
f0[i] = min(f0[i - 1], f1[i - 1] + i - 1);
f1[i] = min(f0[i - 1] + i, f1[i - 1] + 2 * i - 1);
} else {
f0[i] = min(f0[i - 1] + 2 * i - 1, f1[i - 1] + i);
f1[i] = min(f0[i - 1] + i - 1, f1[i - 1]);
}
}
LL ans = min(f0[n], f1[n]);
LL g0 = 0, g1 = 0;
for (int i = n; i >= 1; i--) {
LL t0 = g0, t1 = g1;
if (s[i - 1] == '0') {
g0 = min(t0, t1 + n - i);
g1 = min(t0 + n - i + 1, t1 + 2 * (n - i) + 1);
} else {
g0 = min(t0 + 2 * (n - i) + 1, t1 + n - i + 1);
g1 = min(t0 + n - i, t1);
}
ans = min(ans, min(f0[i - 1] + g0, f1[i - 1] + g1));
}
return ans;
}
};
算法2
(思维题) $O(n)$
- 注意到,每一次出现 $s(i) \neq s(i + 1)$ 的位置,必须前缀变动 $i$,或者后缀变动 $i + 1$。注意到,变动后,会使得 $s(i) = s(i + 1)$,且其他相邻位置的相等关系不收任何影响。
- 从前往后遍历字符串,遇到每一个上述位置,比较两次变动的代价,取最小的代价累加。
时间复杂度
- 遍历字符串一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
LL minimumCost(string s) {
const int n = s.size();
LL ans = 0;
for (int i = 0; i < n - 1; i++)
if (s[i] != s[i + 1])
ans += min(i + 1, n - i - 1);
return ans;
}
};
“且其他相邻位置的相等关系不收任何影响。”这里太重要了
第二个想法有点秀,感觉要靠一点直觉呢