classSolution{ publicintcountBinarySubstrings(String s){ List<Integer> counts = new ArrayList<>(); int ans = 0; //生成 counts 数组 char cur = s.charAt(0); int c = 0; for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == cur){ ++c; }else{ counts.add(c); cur = s.charAt(i); c = 1; } } counts.add(c); //计算贡献和 for(int i = 1; i < counts.size(); i++){ ans += Math.min(counts.get(i), counts.get(i - 1)); } return ans; }
}
时间复杂度和空间复杂度都为 O(n)。
我们可以发现,在对每一个数计算贡献时,我们只用到了前一个值,我们使用 last 来保存。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution{ publicintcountBinarySubstrings(String s){ int ptr = 0, n = s.length(), last = 0, ans = 0; while(ptr < n){ char c = s.charAt(ptr); int count = 0; while(ptr < n && s.charAt(ptr) == c){ ++ptr; ++count; }
ans += Math.min(count, last); last = count; } return ans; }
v1.5.2