写点什么

JavaScript 刷 LeetCode- 字符串类解题技巧

作者:Geek_07a724
  • 2022-10-26
    浙江
  • 本文字数:3061 字

    阅读完需:约 10 分钟

序章

我们把字符串数组正则排序递归归为简单算法。接下来系列里,将系列文章里将为大家逐一介绍。

字符串

翻转字符串中的单词

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例 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)



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 优秀,。


用户头像

Geek_07a724

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
JavaScript刷LeetCode-字符串类解题技巧_JavaScript_Geek_07a724_InfoQ写作社区