做网站有名的公司,wordpress支付看文章,网站开发开发优势,正能量网站地址链接免费文章目录1. 题目2. 解题1. 题目
如果一个由 0 和 1 组成的字符串#xff0c;是以一些 0#xff08;可能没有 0#xff09;后面跟着一些 1#xff08;也可能没有 1#xff09;的形式组成的#xff0c;那么该字符串是单调递增的。
我们给出一个由字符 0 和 1 组成的字符串…
文章目录1. 题目2. 解题1. 题目
如果一个由 0 和 1 组成的字符串是以一些 0可能没有 0后面跟着一些 1也可能没有 1的形式组成的那么该字符串是单调递增的。
我们给出一个由字符 0 和 1 组成的字符串 S我们可以将任何 0 翻转为 1 或者将 1 翻转为 0。
返回使 S 单调递增的最小翻转次数。
示例 1
输入00110
输出1
解释我们翻转最后一位得到 00111.示例 2
输入010110
输出2
解释我们翻转得到 011111或者是 000111。示例 3
输入00011000
输出2
解释我们翻转得到 00000000。提示
1 S.length 20000
S 中只包含字符 0 和 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/flip-string-to-monotone-increasing 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
动态规划dp0[i]表示在相应字符处以0结束的最小翻转次数dp1[i]表示在相应字符处以1结束的最小翻转次数注意预处理得到前缀 1 的个数见注释
class Solution {
public:int minFlipsMonoIncr(string S) {int n S.size();vectorint one(n);for(int i 0; i n; i)one[i] (i 0 ? one[i-1] : 0) (S[i]1);// 前缀 1 的个数vectorint dp0(n1, n), dp1(n1, n);// dp0[i] 表示 以 0 结束递增的最小翻转次数// dp1[i] 表示 以 1 结束递增的最小翻转次数dp0[0] dp1[0] 0;for(int i 0; i n; i){if(S[i] 0)//当前是0{dp0[i1] min((i 0 ? one[i-1] : 0), dp0[i]);//以0结束 把前面的 1 都翻过来 or 前面以0结束dp1[i1] min(dp0[i], dp1[i])1;//以1结束 前面以0或1结束都可以再把当前0翻转为11}else//当前是 1{dp0[i1] min((i 0 ? one[i-1] : 0), dp0[i])1;//以0结束 把前面的 1 都翻过来 or 前面以0结束 再把当前1翻转为01dp1[i1] min(dp0[i], dp1[i]);//以1结束 前面以0或1结束都可以}}return min(dp0[n], dp1[n]);}
};12 ms 9.1 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
