力扣热题——使所有字符相等的最小成本（难度：中等）
目录
题目链接：2712. 使所有字符相等的最小成本 - 力扣（LeetCode）
题目描述
解法一：规律发现
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
解法二：动态规划
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
总结
题目链接：2712. 使所有字符相等的最小成本 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：
- 选中一个下标
i并且反转从下标0到下标i（包括下标0和下标i）的所有字符，成本为i + 1。 - 选中一个下标
i并且反转从下标i到下标n - 1（包括下标i和下标n - 1）的所有字符，成本为n - i。
返回使字符串内所有字符 相等 需要的 最小成本 。
反转 字符意味着：如果原来的值是 \'0\' ，则反转后值变为 \'1\' ，反之亦然。
示例 1：
输入：s = \"0011\"输出：2解释：执行第二种操作，选中下标i = 2，可以得到s = \"0000\" ，成本为 2。可以证明 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 <= 105s[i]为\'0\'或\'1\'
解法一：规律发现
- 循环遍历字符串：从第二个字符（索引1）开始遍历到字符串末尾，检查当前字符与前一个字符是否不同。
- 条件判断：当发现相邻字符不同时，计算两种翻转方式的最小成本：
- 翻转前i个字符的成本是i（因为前i个字符的位置是0到i-1，共i个字符）。
- 翻转后面字符的成本是字符串总长度减去i（即剩余字符的数量）。
- 类型转换：将字符串长度转换为
long long以确保类型一致性，避免潜在的整数溢出问题。 - 累加结果：将每次的最小成本累加到结果中。
Java写法：
class Solution { public long minimumCost(String s) { // 根据示例2其实你不难看出来，他的翻转逻辑 /// 找到两个相邻位置但是是不同值的位置，看是翻转前面的成本高还是后面的 // 选择成本低的进行翻转 long res = 0; for(int i = 1;i < s.length();i++){ if(s.charAt(i) != s.charAt(i - 1)){ res += Math.min(i-1+1,s.length()-i); } } return res; }}C++写法：
class Solution {public: long long minimumCost(string s) { long long res = 0; for(int i = 1; i < s.size(); i++) { if(s[i] != s[i - 1]) { res += min(i, (long long)s.size() - i); } } return res; }};运行时间
记得改成long不然会砸缸
时间复杂度和空间复杂度
解法二：动态规划
-
后缀翻转成本计算 (
suffixCost)-
suffixCost[i][0]：将s[i]到s[n-1]变成全0的最小成本。 -
suffixCost[i][1]：将s[i]到s[n-1]变成全1的最小成本。
计算方法：
-
若
s[i] == \'1\'：-
suffixCost[i][1] = suffixCost[i+1][1]（保持1无需翻转）。 -
suffixCost[i][0] = suffixCost[i+1][1] + (n-i)（翻转1 → 0）。
-
-
若
s[i] == \'0\'：-
suffixCost[i][1] = suffixCost[i+1][0] + (n-i)（翻转0 → 1）。 -
suffixCost[i][0] = suffixCost[i+1][0]（保持0无需翻转）。
-
-
-
前缀翻转成本计算 (
prefixCost)-
prefixCost[0]：当前前缀变成全0的最小成本。 -
prefixCost[1]：当前前缀变成全1的最小成本。
计算方法：
-
若
s[i] == \'1\'：-
prefixCost[0] = prefixCost[1] + (i+1)（翻转1 → 0）。
-
-
若
s[i] == \'0\'：-
prefixCost[1] = prefixCost[0] + (i+1)（翻转0 → 1）。
-
-
-
合并最优解
-
通过遍历
i，找到prefixCost和suffixCost的最小组合。
-
Java写法：
class Solution { public long minimumCost(String s) { int n = s.length(); // 记录后缀翻转成本 long[][] suffixCost = new long[n + 1][2]; // 计算后缀翻转成本 for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == \'1\') { // 保持1的成本 suffixCost[i][1] = suffixCost[i + 1][1]; // 变0的成本 suffixCost[i][0] = suffixCost[i + 1][1] + (n - i); } else { // 变1的成本 suffixCost[i][1] = suffixCost[i + 1][0] + (n - i); // 保持0的成本 suffixCost[i][0] = suffixCost[i + 1][0]; } } // 记录前缀翻转成本 long[] prefixCost = new long[2]; // 记录最终结果 long minCost = Long.MAX_VALUE; // 计算前缀翻转成本并求最优解 for (int i = 0; i < n; i++) { if (s.charAt(i) == \'1\') { // 变0的成本 prefixCost[0] = prefixCost[1] + (i + 1); } else { // 变1的成本 prefixCost[1] = prefixCost[0] + (i + 1); } // 计算使所有字符相等的最小成本 minCost = Math.min(minCost, Math.min(prefixCost[0] + suffixCost[i + 1][0], prefixCost[1] + suffixCost[i + 1][1])); } return minCost; }}C++写法：
运行时间
时间复杂度和空间复杂度
总结
w我嘞个动态规划啊
