Minimum Suffix Flips
给一个string, 里面是0和1, 给一个操作, 可以flip所有在i后的字符, 求最少flip几次.
这题通过观察, 可以发现如果从左往右考虑, 从0到1的flip和从1到0的flip, 其实都不会影响左边已经flip过的字符, 故操作次数只与当前的字符是不是和前一个字符相同有关.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public int minFlips(String target) { int cur = 0; int res = 0; for(int i = 0; i < target.length(); i++) { if(cur != (target.charAt(i) - '0')){ if(cur == 0) cur = 1; else cur = 0; res++; } } return res; } } |