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

2022-10-26 15:56:43 浏览数 (1)

序章

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

字符串

翻转字符串中的单词

代码语言：lua复制
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 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)保证单词的反转。

步骤一：先把句子分隔开，分割开后塞入数组里，数组的先后顺序就是单词的先后顺序。

步骤二：然后把数组的每个单词进行反转。

代码语言：javascript复制
/** * @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(' ')
};

代码不够简洁，做下面处理。

代码语言：javascript复制
var reverseWords = function(s) {
   return  s.split(' ').map(item => item.split('').reverse().join('')
   ).join(' ')
};

也可以把空格换成正则去处理，s表示空格的意思。这里注意掌握split的2种用法。

代码语言：javascript复制
var reverseWords = function(s) {
   return  s.split(/s/g).map(item => item.split('').reverse().join('')
   ).join(' ')
};

还可以这么写。正则/w' /g就是识别单词的意思，中括号表示可选项，w是字符的意思，w'表示可选字符和', 不止一个元素，后面有个 号。

注意：这不是一个比较好的解法，如果单词中包含逗号，圆括号等，正则尾部会匹配到，输出的答案就会不理想。

代码语言：javascript复制
var reverseWords = function(s) {
   return  s.match(/[w'] /g).map(item => item.split('').reverse().join('')
   ).join(' ')
};
在这里插入图片描述在这里插入图片描述

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

代码语言：javascript复制
String.prototype.split
String.prototype.match
Array.prototype.map
Array.prototype.reverse
Array.prototype.join

计数二进制子串

代码语言：text复制
给定一个字符串 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))找符合条件的子串
  • 找到满足条件的子串，就保存结果
  • 参考视频：传送门
代码语言：javascript复制
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的长度
代码语言：javascript复制
/** * @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个测试用例跑不通。

小结：上述做法涉及到的知识点如下所示。

代码语言：javascript复制
String.prototype.slice
String.prototype.match
Array.prototype.repeat
Array.prototype.push
RegExp

解法二

代码思路整理：

  • cur 与 pre分别记录当前数字连续出现的次数（例如：000或者11）与前一个数字连续出现的次数，result 结果子串的个数。
  • 判断当前数字是否与后一个数字相同。相同，则当前数字出现的次数cur加1。不同，则当前数字事实上变成了前一个数字，当前数字的次数重置为1。
  • 前一个数字出现的次数>=后一个数字出现的次数，则一定包含满足条件的子串。即cur小于等于pre则符合条件。
代码语言：javascript复制
/**
 * @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的个数表示

子串个数

00110011

2222

min(2, 2) min(2, 2) min(2, 2) = 6

001100

221

min(2, 2) min(2, 1) = 3

代码语言：javascript复制
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优秀，。
match min repeat slice splitleetcode javascript

0 人点赞