blob: 35e0e0ccf078c30714b594aa82eb65d6edb6387b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include "leetcode.h"
/*
* a binary string is monotone increasing if it consists of some number
* of 0's (none is valid), followed by some number of 1's (none is valid)
* given: binary string 's'. you can flip 's[i]' changing for 0 to 1 or vice
* versa. return the minimum number of flips to make 's' monotone increasing.
*/
class Solution {
public:
int minFlipsMonoIncr(string s) {
int flips = 0, cnt = 0;
for (auto i : s) {
if (i == '1')
cnt++;
else
flips++;
flips = min(flips, cnt);
}
return flips;
}
};
int main() {
Solution obj;
cout << obj.minFlipsMonoIncr("00110") << endl;
// expect: 1
// flip last digit to get 00111
cout << obj.minFlipsMonoIncr("010110") << endl;
// expect: 2
// flip s[1] s[5] to get 000111
cout << obj.minFlipsMonoIncr("00011000") << endl;
// expect: 2
// flip s[3] s[4] to get 00000000
}
|