序章

咱们把字符串、数组、正则、排序、递归归为简略算法。接下来系列里，将系列文章里将为大家逐个介绍。

字符串

翻转字符串中的单词

给定一个字符串，你须要反转字符串中每个单词的字符程序，同时仍保留空格和单词的初始程序。示例 1:输出: "Let's take LeetCode contest"输入: "s'teL ekat edoCteeL tsetnoc"留神：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额定的空格。起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii

解题思路：要保障单词和空格的初始程序；a)保障单词的先后顺序不能扭转；b)保障单词的反转。

步骤一：先把句子分隔开，宰割开后塞入数组里，数组的先后顺序就是单词的先后顺序。
步骤二：而后把数组的每个单词进行反转。

/** * @param {string} s * @return {string} */var reverseWords = function(s) {    let arr = s.split(' ')    let result = arr.map(item=>{        return item.split('').reverse().join('')    })   return  result.join(' ')};

代码不够简洁，做上面解决。

var reverseWords = function(s) {   return  s.split(' ').map(item => item.split('').reverse().join('')   ).join(' ')};

也能够把空格换成正则去解决，\s示意空格的意思。这里留神把握split的2种用法。

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

还能够这么写。正则/[\w']+/g就是辨认单词的意思，中括号示意可选项，w是字符的意思，[\w']示意可选字符和', 不止一个元素，前面有个+号。
留神：这不是一个比拟好的解法，如果单词中蕴含逗号，圆括号等，正则尾部会匹配到，输入的答案就会不现实。

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

小结：本题波及到的知识点如下所示。

String.prototype.splitString.prototype.matchArray.prototype.mapArray.prototype.reverseArray.prototype.join

计数二进制子串

给定一个字符串 s，计算具备雷同数量0和1的非空(间断)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。  反复呈现的子串要计算它们呈现的次数。示例 1 :输出: "00110011"输入: 6解释: 有6个子串具备雷同数量的间断1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。请留神，一些反复呈现的子串要计算它们呈现的次数。另外，“00110011”不是无效的子串，因为所有的0（和1）没有组合在一起。示例 2 :输出: "10101"输入: 4解释: 有4个子串：“10”，“01”，“10”，“01”，它们具备雷同数量的间断1和0。留神：s.length 在1到50,000之间。s 只蕴含“0”或“1”字符。起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/count-binary-substrings

这种难度大的题目，先找出输入输出的法则，并且实现。
如何找到法则呢？发现输出和输入的关系，寻找突破点。

解法一

步骤一：先把关系图谱展示进去，查找其中的法则。

  • 起始点在一次次的往右移
  • 从0开始查找0011，找到后就进行了，而后从下一位开始查找
  • 找到一个后果向下一位，并且把从下一位到最初一位这个子串作为下一次输出（新的输出，子输出）=》递归
  • 引入新概念：反复找过程。反复找子串的过程：找子串这个行为能够抽出来，作为一个公共的行为。

参考视频：传送门

步骤二：伪代码实现

  • 为啥i<str.length-1，因为如果光标在最初一位i=str.length-1，必定不满足题目的0和1的非空(间断）条件，只剩下1位了
  • r=match(str.slice(i))找符合条件的子串
  • 找到满足条件的子串，就保留后果
for i=0;i<str.length-1;i++    r=match(str.slice(i))    if r        result.push(r)

步骤三：计算子串代码演示
代码思路整顿：

  • 利用for循环，将字符串从第一个开始传入match函数中，在match函数中应用正则表达式获取到字符串结尾的字符（或是多个0或是多个1）
  • 再应用repeat办法，将结尾获取到的多个0或1利用异或运算反转反复雷同次数（举个例子：获取到了‘00’，那么反转之后就是‘11’）
  • 而后再建设一个正则表达式，将获取到的字符和反转后的字符拼接，应用test办法与传入的字符串进行比对，返回第一个比对胜利的字符串，保留到数组result中
  • 以此类推，剃掉原字符串的第一个字符后再调用一次match办法，直到原字符串只剩下1个字符，返回数组result的长度
/** * @param {string} str * @return {number} */var countBinarySubstrings = function(str) {    let resultArr = [];    let match = (str) => {        let beforeStr = str.match(/^(0+|1+)/)[0]        let afterStr = (beforeStr[0]^1).toString().repeat(beforeStr.length)        let reg = new RegExp(`^(${beforeStr}${afterStr})`)        if(reg.test(str)){            return RegExp.$1        } else {            return ''        }    }    for(i=0;len=str.length-1,i<len;i++) {        let subStr = match(str.slice(i));        if(subStr) {            resultArr.push(subStr)        }     }    return resultArr.length};

上述解题办法对于字符串比拟长的场景通不过，只能跑通85个，还有5个测试用例跑不通。
小结：上述做法波及到的知识点如下所示。

String.prototype.sliceString.prototype.matchArray.prototype.repeatArray.prototype.pushRegExp

解法二

代码思路整顿：

  • cur 与 pre别离记录以后数字间断呈现的次数（例如：000或者11）与前一个数字间断呈现的次数，result 后果子串的个数。
  • 判断以后数字是否与后一个数字雷同。雷同，则以后数字呈现的次数cur加1。不同，则以后数字事实上变成了前一个数字，以后数字的次数重置为1。
  • 前一个数字呈现的次数>=后一个数字呈现的次数，则肯定蕴含满足条件的子串。即cur小于等于pre则符合条件。
/** * @param {string} s * @return {number} */var countBinarySubstrings = function(s) {    let pre = 0, cur = 1, count = 0    for (let i = 0, len = s.length - 1; i < len; i++) {        if (s[i] === s[i+1]) {            cur++         } else {            pre = cur            cur = 1        }        if (pre >= cur) {             count++        }    }    return count};

解法三

代码思路整顿：
计算间断的0或者1的长度。例如“0011100001”， 则为 (2,3,4,1), 只需计算相邻的两个元素的最小值，因为要求0和1必须在子串中间断。 即sum(2 min 3, 3 min 4, 4 min 1)

字符串用间断0或1的个数示意子串个数
001100112222min(2, 2) + min(2, 2) + min(2, 2) = 6
001100221min(2, 2) + min(2, 1) = 3
const countBinarySubstrings = function(s) { let count = 0,len=s.length-1,resultArr = []; for (i=0;i<=len;i++) {     count ++ ;     if(s[i]!==s[i+1]) {        resultArr.push(count);        count = 0;     }  }    let sum=0;    for(i=0,len=resultArr.length-1;i<len;i++) {        sum += Math.min(resultArr[i],resultArr[i+1])    }    return sum;}

总结

  • 解法1是一个很间接很暴力的解法，然而对于ES6的基础知识要求比拟高，用到slice、match、repeat等办法以及正则表达式。 然而因为解法1过于简略暴力，在正则表达式与原字符串进行比对时破费了大量的工夫，尤其是原字符串十分长的时候，因而解法1并不是好的算法。
  • 解法2和3更加合乎解题逻辑，同时解法2和3省去了与原字符串比对的过程，因而解法2和3在工夫复杂度下面远比解法1优良，。