力扣
我的力扣题解
参考了官方题解的思路：
把连续子串分组，相邻的两个连续子串最小值，即这两个子串的连续数计算值
手动吐槽一下自己的代码，写注释的时候发现要被自己的算法绕晕了… 变量太多了…
其他解题思路的代码，等缓一缓过几天再解
AC 代码
v 1.0.0
2020年08月13日
统计
虽然性能好像还凑和
| 版本 |
耗时 |
超越 |
内存 |
超越 |
更新时间 |
| 1.0.0 |
108 ms |
48.77% |
39.9 MB |
62.93% |
2020年08月13日23:00:00 |
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
37
38
39
40
41
42
43
|
/**
* @param {string} s
* @return {number}
* 思路：把连续子串分组，相邻的两个连续子串最小值，即这两个子串的连续数计算值
* 计算：计算第 i 个子串的连续长度 val(i) = Min(len(i),len(i - 1))
* 注意：第 i 个子串，必须遍历到第 i + 1 个子串才能确定 i 的连续长度
*/
var countBinarySubstrings = function(s) {
const length = s.length; // 缓存数组长度
let total = 0; // 返回结果
let currentCount = 0; // 第 i 个子串的连续长度
let prevCount = 0; // 第 i - 1 个子串的连续长度
let current = -1; // 初始状态当前值 -1
// 遇到新值个数，计算 Min(len(i),len(i - 1)) 需要遍历到 i + 1 项，即需要遇到 2 个新值
let newValueCount = 0;
for (let i = 0; i < length; i++) {
// 计算第 0 到 第 i - 1 个子串
if(s[i] !== current) {
newValueCount++;
// 每次遇到第 i 个新子串时，可以确定 len(i - 1) 和 len(i -2) 子串的连续长度
// 即： val(i - 1) = Min(len(i - 1), len(i - 2))
// 遇到新值时，不同位置，有两种情况要考虑
// 1. 非最后一位，按上述公式计算，遇到 i + 1 项时计算
// 2. 最后一位，不用且无法遍历到 i + 1（此时仍计算的是 i - 1 个子串）
if(newValueCount === 2 || i === length - 1) {
total = total + Math.min(currentCount, prevCount)
prevCount = currentCount;
// 注意：非初始值时本身（i）对于第 i - 1 项就是一个新值，所以每次重置为 1
newValueCount = 1;
}
current = s[i];
currentCount = 1;
} else {
// 统计当前字符串连续数量
currentCount++;
}
// 计算第 i 个子串的情况
if(i === length - 1) {
total = total + Math.min(currentCount, prevCount)
}
}
return total;
};
|
清风迅来