登录
原创

JS基础算法(字符串篇)

专栏JS算法基础篇
发布于 2020-12-10 阅读 2258
  • JavaScript
  • 面试
  • 算法
原创

算法考点

  • 见多识广(每个类型都要能说出一二三来,具体细节不要纠结)
  • 反应迅速(快速用js实现出来栈,队列等)
  • 就算立马写不出来,至少快速说出思路

基础算法-字符串

1.反转字符串中的单词 III

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例 1:
输入: “Let’s take LeetCode contest” 输出: “s’teL ekat edoCteeL tsetnoc” 注意:在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。

  • 注意点
    让代码更加优雅(不要产生多余的变量)
var reverseWords = function(s) {
    return s.split(' ').map(item=>{
        return item.split('').reverse().join('');
    }).join(' ');
};
var reverseWords = function(s) {
    // 体现出split两种用法都清楚
    return s.split(/\s/g).map(item=>{
        return item.split('').reverse().join('');
    }).join(' ');
};
var reverseWords = function(s) {
    // 使用match来做(大于一个单词或者'的集合的数组)
    return s.match(/[\w']+/g).map(item=>{
        return item.split('').reverse().join('');
    }).join(' ');
};
var reverseWords = function(s) {
    // 重写以上
    if (str.length < 1) return ''
    return str.match(/[\S]+/g).map(item => {
        return item.split('').reverse().join('')
    }).join(' ')
};

2. 计数二进制子串

/* 给定一个字符串 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”字符。*/

/*
写出所有情况,然后找出规律
00110011--->0011
0110011 --->01
110011 --->1100
10011 --->10
0011 --->0011
011 --->01
11 --->
1 --->
*/
var countBinarySubstrings=function(str){
    // 建立数据结构,堆栈,保存数据
    let r = []
    // 给一个字符串返回第一个符合条件的子串
    let match = (str) => {
      let j = str.match(/^(0+|1+)/)[0]
      // 与运算1变0,0变1
      let o = (j[0] ^ 1).toString().repeat(j.length)
      // 正则对象中可以使用模板字符串来用变量
      let reg = new RegExp(`^(${j}${o})`)
      if (reg.test(str)) {
          // 返回匹配到的第一个结果
          return RegExp.$1
      } else {
          return ''
      }
    }
    // 依次把最前面的数字去掉
    for (let i = 0, len = str.length - 1; i < len; i++) {
        let sub = match(str.slice(i))
        if (sub) {
            r.push(sub)
        }
    }
    return r
}
countBinarySubstrings('00101')

知识点 slice、match、repeat、push、RegExp

评论区

timing
4粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

0

0

0

举报