灯泡开关 IV
本菜鸡的代码
想法是这样的：
首先把连续的0或者1都缩成一个,比如：
000111100111001
可以变成：
010101
除了第一位是一开始就是0，无需任何操作之外。
后面的每个都要反转一次，所以最终答案就是5。
class Solution {
public:int minFlips(string s) {int n = s.size(), l = 0, ans = 0 ;while(s[l]=='0' && l<n){if(l<n) ++l;}while(l<n){if(s[l]=='1'){while(s[l]=='1' && l<n){l++;}}else{while(s[l]=='0' && l<n){l++;}}ans++;}return ans;}
};
看了零神的代码。
class Solution {
public:int minFlips(string target) {int cnt = 0 , ans = 0;for(char c:target){int d = c-'0';if(d!=cnt){cnt ^= 1;ans ++; }}return ans;}
};
DP写法
class Solution {
public:int minFlips(string target) {int n = target.size();vector<int> dp(n);dp[0]= target[0]-'0';for(int i=1;i<n;i++){if(target[i]==target[i-1]){dp[i] = dp[i-1];}else{dp[i] = dp[i-1]+1;}}return dp[n-1];}
};
但是上面的做法实际上都是贪心的解决。