leetcode刷题记录 js算法与数据结构 基础篇（上）

立志做一个情感博主的程序员

---

WechatIMG30.jpeg

1 #### 反转字符串中的单词
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"

export default str => {
  // 1 将字符串切割成数组
  let arr = str.split(/\s+/g);
  // 2 然后再讲数据的每一项再切成数组[[abc], [bcd], [efg]]  从而利用数组的  reverse进行反转
  let result = arr.map(item => {
      return item.split('').reverse().join('')
  })
  return result.join(' ')
}
// 不懂split reverse join 和map方法的请自行百度

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”字符。

规律图

image.png

位运算符链接 不懂自己吸纳哦 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

var countBinarySubstrings = function(s) {
    let matchFn = (str) => {
        // 找出一边相同的数字
        let startNum = str.match(/^(1+|0+)/)[0];
        // ^ 不懂看官方解释    对于每一个比特位，当两个操作数相应的比特位有且只有一个1时，结果为1，否则为0。
        let endNum = (startNum[0] ^ 1).toString().repeat(startNum.length);
        // startNum[0] 这里说一下 为什么要取[0]， 因为 ^ 操作符比较的事 比特位
        // 比特(位):英文bit,是计算机晶体管的一种状态(通电与断电).就是0与1,真与假,是计算机最基本的传输单位.
        // 所以只取一位
        let target = `${startNum}${endNum}`
        // 注意 只能从字符串的最开始匹配  。
        // 或者用正则完成 let regs = new RegExp(`^(${startNum}${endNum})`); return regs.test(str) ? `${startNum}${endNum}` : ''; 但是如果数字（比特位太多 动态生成的正则会爆）
          if (str.slice(0, target.length) === target) {
            return `${startNum}${endNum}`;
        }
        return '';
    };

    let arr = [];
    for(i = 0; i < s.length - 1; i++) {
        let match = matchFn(s.slice(i));
        if (match) {
            arr.push(match);
        }
    }
    return arr.length;
};
countBinarySubstrings('00110011');

3#### 电话号码的字母组合
示例：
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

1562230212545.jpg

var letterCombinations = function (digits) {
    // 存放数字对应的字母 
    let arr = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    let newDigits = digits.split('');
    // 输入数字 所对应的字母  比如输入'23' => ['abc', 'def']
    let proveArr = newDigits.map(index => {
        return arr[index];
    });

    // 如果输入为'', 则返回[]
    if (!digits) {
        return [];
    }
    // 如果输入的是个位数 则直接返回
    else if (digits.length === 1) {
        return proveArr[0].toString().split('');   
    }
    else {
        let fn = proveArr => {
            let endResult = [];
            // 第三步 需要便利proveArr， 让每一个字母进行组合
            for (let i = 0; i < proveArr[0].length; i++) {
                for (let j = 0; j < proveArr[1].length; j++) {
                    endResult.push(`${proveArr[0][i]}${proveArr[1][j]}`);
                }
            }
            // 这一步很关键， 每次合并数组的前两组字母， 然后再递归  直到数组长度只剩下1
            proveArr.splice(0, 2, endResult);
            if (proveArr.length > 1) {
                fn(proveArr);
            }
            else {
                return endResult;
            }
            return proveArr[0];
        };
        return fn(proveArr);
    }  
};