关于leetcode:JavaScript刷LeetCode字符串类解题技巧

52次阅读

共计 3892 个字符,预计需要花费 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.split
String.prototype.match
Array.prototype.map
Array.prototype.reverse
Array.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.slice
String.prototype.match
Array.prototype.repeat
Array.prototype.push
RegExp

解法二

代码思路整顿:

  • 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 的个数示意 子串个数
00110011 2222 min(2, 2) + min(2, 2) + min(2, 2) = 6
001100 221 min(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 优良,。

正文完
 0