基础算法之“字符串类”

反转字符串中的单词Ⅲ

解题

1.通过空格分割字符串，每一项倒序再拼接

var reverseWords = function(s) {
    var list = s.split(' ')
    let result = list.map((res) => {
        return res.split('').reverse().join('')
    })

    return result.join(' ')
}

2.减少变量，空间复杂度优化

var reverseWords = function(s) {
    return s.split(/\s/g).map((res) => res.split('').reverse().join('')).join(' ')
}

3.正则表达式

var reverseWords = function(s) {
    return s.match(/[\w']+/g).map((res) => res.split('').reverse().join('')).join(' ')
}

使用到的Api

String.prototype.split

split() 方法使用指定的分隔符字符串将一个String对象分割成子字符串数组，以一个指定的分割字串来决定每个拆分的位置。

String.prototype.match

match() 方法检索返回一个字符串匹配正则表达式的结果。

Array.prototype.map

map() 方法创建一个新数组，其结果是该数组中的每个元素是调用一次提供的函数后的返回值。

Array.prototype.reverse

reverse() 方法将数组中元素的位置颠倒，并返回该数组。数组的第一个元素会变成最后一个，数组的最后一个元素变成第一个。该方法会改变原数组。

Array.prototype.join

join() 方法将一个数组（或一个类数组对象）的所有元素连接成一个字符串并返回这个字符串。如果数组只有一个项目，那么将返回该项目而不使用分隔符。

思维方法

要熟悉所有的API，知道在某些场景的实际应用

计数二进制子串

难度大的题目如何解？

算法的本质是寻找规律并实现

如何找到规律？

发现输入和输出的关系，寻找突破点

复杂的实现怎么办？

实现是程序 + 数据结构的结合体

找规律

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

把输出结果代入输入

会发现子串起始位置往右移，所以这里可以使用递归的方法，在子串中进行查找符合条件的子集

解题

var countBinarySubstrings = function(s) {
    let ptr = 0, n = s.length, last = 0, ans = 0;
    while (ptr < n) {
        const c = s.charAt(ptr);
        let count = 0;
        while (ptr < n && s.charAt(ptr) === c) {
            ++ptr;
            ++count;
        }
        ans += Math.min(count, last);
        last = count;
    }
    return ans;
};