V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzzzzzggggggg
V2EX  ›  程序员

[第 2 期] 前端算法精选-字符串系列

  •  
  •   zzzzzzggggggg · 2020-02-27 21:31:08 +08:00 · 769 次点击
    这是一个创建于 420 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天精选的题目是关于字符串操作的,涉及到的技巧有字符串的滑动窗口思路、大数相乘。

    字符串的排列

    LeetCode.567 ,难度中等

    题目

    给定两个字符串s1s2,写一个函数来判断s2是否包含s1的排列。

    换句话说,第一个字符串的排列之一是第二个字符串的子串。

    示例 1:

    输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").

    示例 2:

    输入: s1= "ab" s2 = "eidboaoo" 输出: False

    注意:

    1. 输入的字符串只包含小写字母
    2. 两个字符串的长度都在 [1, 10,000] 之间

    解法

    理解一下题意,要求 s1 的字符串排列之一是第二个字符串的子串,比如 ab 是 eidbaooo 的子串,ba 也是 eidbaooo 的子串,同样的 baoo 也是 eidbaooo 的子串,所以这个规则可以抽象一下,如果 eidbaooo 里面存在一个子串,该子串的字符和 s1 的字符相同,且该子串字符出现的次数和 s1 中的字符出现次数相同,因此,可以考虑滑动窗口的思路。

    首先维护一个 map1 来保存 s1 的字符以及每个字符出现的次数,再维护一个 map2 来保存当前窗口中的每个字符以及每个字符出现的次数,如果 map1 和 map2 相同,则说明滑动窗口中的字符子串和 s1 的排列之一相同,否则继续往右滑动。

    1. 初始化,以 s1 长度为准,来构造两个 map,map1 = { a: 1, b: 1 },map2 = { e: 1, i: 1 }。此时滑动窗口中的字符串是'ei'
    2. 从 s2 的第 3 个(前两个已经被初始化过)字符'd'开始遍历,map1 和 map2 不同。此时窗口字符串是'ei',删掉左边的'e',更新 map2= { i: 1 };加入第 3 个字符'd',更新 map2 = { i: 1, d: 1 }
    3. 此时遍历到第 4 个字符'b',map1 和 map2 不同。此时窗口字符串是'id',删掉左边的'i',更新 map2={ d: 1 };加入第 4 个字符串'b',更新 map2={ d: 1, b: 1 }
    4. 此时遍历到第 5 个字符'a',map1 和 map2 不同。此时窗口的字符串是'db',删掉左边的'd',更新 map2={ b: 1 };加入第 5 个字符串'a',更新 map2={ b: 1, a: 1 }
    5. 此时遍历到滴 6 个字符'o',map1 和 map2 相同,返回 true

    代码如下:

    /\*\*
     \* @param {string} s1
     \* @param {string} s2
     \* @return {boolean}
     \*/
    let checkMapEqual = function(m1, m2) { 
        let keys1 = Object.keys(m1), keys2 = Object.keys(m2);
        
        if(keys1.length !== keys2.length)
            return false;
        
        for(let i = 0;i < keys1.length;i++) {
            const curKey = keys1\[i\];
            if(m1\[curKey\] !== m2\[curKey\])
                return false;
        }
        
        return true;
    }
    let checkInclusion = function(s1, s2) {
        if(s1.length > s2.length)
          return false;
        
        let map1 = {}, map2 = {};
        const len1 = s1.length, len2 = s2.length;
        // 初始化 map
        for(let i = 0;i < len1;i++) {
            if(map1\[s1\[i\]\]) {
                map1\[s1\[i\]\]++
            } else {
                map1\[s1\[i\]\] = 1;
            }
            if(map2\[s2\[i\]\]) {
                map2\[s2\[i\]\]++
            } else {
                map2\[s2\[i\]\] = 1;
            }
        }
        for(let i = len1;i < len2;i++) {
            if(checkMapEqual(map1, map2)) {
                return true;
            }
            
            // 将窗口最左边的字符删去
            const leftChar = s2\[i-len1\];
            if(map2\[leftChar\] === 1) {
                delete map2\[leftChar\];
            } else {
                map2\[leftChar\]--;
            }
            // 在窗口右边加入一个字符
            const rightChar = s2\[i\];
            if(map2\[rightChar\]) {
                map2\[rightChar\]++;
            } else {
                map2\[rightChar\] = 1;
            }
        }
        return checkMapEqual(map1, map2);
    };
    

    字符串相乘

    LeetCode.43 ,难度中等

    题目

    给定两个以字符串形式表示的非负整数num1num2,返回num1num2的乘积,它们的乘积也表示为字符串形式。

    示例 1:

    输入: num1 = "2", num2 = "3" 输出: "6"

    示例 2:

    输入: num1 = "123", num2 = "456" 输出: "56088"

    说明:

    1. num1num2的长度小于 110。
    2. num1num2只包含数字0-9
    3. num1num2均不以零开头,除非是数字 0 本身。
    4. 不能使用任何标准库的大数类型(比如 BigInteger )或直接将输入转换为整数来处理。

    解法

    先分析一下题目字符串相乘,要想模拟两个数字相乘,需要解决逐位相乘、再逐个相加的问题,过程中需要注意正确进位,比如'123'和'456'相乘:

    1. 3 和 456 相乘,得到 1368 ;

    2. 2 和 456 相乘,得到 912,因为 2 是十位,所以得到 9120 ;

    3. 1 和 456 相乘,得到 456,因为 1 是百位,所以得到 45600 ;

    4. 把 3 次乘积相加,加的过程中也要注意逐位相加,别忘了进位

    代码如下:

    /\*\*
     \* @param {string} num1
     \* @param {string} num2
     \* @return {string}
     \*/
    const multiplyStep = (num1, pos, num2) => {
      let res = '';
      let carry = 0;
      for(let i = num2.length-1;i >= 0;i--) {
        const cur = num2\[i\];
        let product = parseInt(cur)\*num1;
        if(carry) {
          product += carry;
          carry = 0;
        }
        if(product >= 10) {
          carry = parseInt(product/10);
          product = product%10
        }
        res = product + res;
      }
      if(carry) {
        res = carry + res;
      }
      
      while(pos) {
        res += 0;
        pos--;
      }
      return res;
    }
    const addStep = (num1, num2) => {
      let len1 = num1.length;
      let len2 = num2.length;
      let num1Reversed = num1.split('').reverse().join('');
      let num2Reversed = num2.split('').reverse().join('');
      
      let index = 0;
      let res = '';
      let carry = false;
      while(index < len1 && index < len2) {
        const char1 = num1Reversed\[index\];
        const char2 = num2Reversed\[index\];
        
        let sum = parseInt(char1) + parseInt(char2);
        if(carry) {
          sum += 1;
          carry = false;
        }
        if(sum >= 10) {
          carry = true;
          sum = sum%10;
        }
        res += sum;
        index++;
      }
      while(index < len1) {
        let cur = num1Reversed\[index\];
        if(carry) {
          carry = false
          cur =  parseInt(cur)+1;
        }
        if(cur >= 10) {
          cur = cur%10;
          carry = true;
        }
        res += cur;
        index++;
      }
      while(index < len2) {
        let cur = num2Reversed\[index\];
        if(carry) {
          carry = false
          cur =  parseInt(cur)+1;
        }
        if(cur >= 10) {
          cur = cur%10;
          carry = true;
        }
        res += cur;
        index++;
      }
      if(carry) {
        res += 1;
        carry = false;
      }
      
      return res.split('').reverse().join('');
    }
    var multiply = function(num1, num2) {
      if(num1 === '0' || num2 === '0')
        return '0';
      
      let strArr = \[\];
      let res = '0';
      for(let i = num1.length-1;i >= 0;i--) {
        strArr.push(
          multiplyStep(num1\[i\], num1.length-1-i, num2)
        )
      }
        console.log(strArr);
      for(let i = 0;i < strArr.length;i++)  {
        res = addStep(res, strArr\[i\]);
      }
      
      return res;
    };
    

    感兴趣的可以关注我的微信公众号,前端亚古兽

    目前尚无回复
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   996 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 18ms · UTC 21:34 · PVG 05:34 · LAX 14:34 · JFK 17:34
    ♥ Do have faith in what you're doing.