【js】-【字符串-应用】- 学习笔记

声明：本笔记是根据掘金小册总结的，如果要学习更多细节，请移步https://juejin.cn/book/6844733800300150797

1 基本算法技能

1. 反转字符串

直接调相关 API

const str = 'juejin'  
// 定义反转后的字符串
const res = str.split('').reverse().join('')

console.log(res) // nijeuj

2. 判断一个字符串是否是回文字符串

function isPalindrome(str) {
    
    // 先反转字符串
    const reversedStr = str.split('').reverse().join('')
    // 判断反转前后是否相等
    return reversedStr === str
}

对称特征

function isPalindrome(str) {
    
    // 缓存字符串的长度
    const len = str.length
    // 遍历前半部分，判断和后半部分是否对称
    for(let i=0;i<len/2;i++) {
    
        if(str[i]!==str[len-i-1]) {
    
            return false
        }
    }
    return true
}

2.1 回文字符串的衍生问题

描述：
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
输入: “aba”
输出: True
示例 2:
输入: “abca”
输出: True

思路：

1. 定义一个function判断字符串是否回文
2. 分别定义左右指针，i和j
3. 对称时，左右两边一起走
4. 遇到不对称的，左边删一个，判断跳过左指针元素后字符串是否回文；右边删一个，判断跳过右指针元素后字符串是否回文；
5. 若是，则整个字符串是回文
   

const validPalindrome = function(s) {
    

    const len = s.length

    // i、j分别为左右指针
    let i=0, j=len-1
    
    // 当左右指针均满足对称时，一起向中间前进
    while(i<j&&s[i]===s[j]) {
    
        i++ 
        j--
    }
    
    // 尝试判断跳过左指针元素后字符串是否回文
    if(isPalindrome(i+1,j)) {
    
      return true
    }
    // 尝试判断跳过右指针元素后字符串是否回文
    if(isPalindrome(i,j-1)) {
    
        return true
    }
    
    // 工具方法，用于判断字符串是否回文
    function isPalindrome(st, ed) {
    
        while(st<ed) {
    
            if(s[st] !== s[ed]) {
    
                return false
            }
            st++
            ed--
        } 
        return true
    }
    
    // 默认返回 false
    return false 
};

3 字符串匹配问题(正则表达式)

描述：
设计一个支持以下两种操作的数据结构：void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z
（. 可以表示任何一个字母）

思路：

search 它既可以搜索文字，又可以搜索正则表达式。
若包含.则是正则表达式
若是普通字符串，则直接去 Map 中查找是否有这个 key；
若是正则表达式，则创建一个正则表达式对象，判断 Map 中相同长度的字符串里，是否存在一个能够与这个正则相匹配。

补充：

使用 RegExp 对象
在 JavaScript 中，RegExp 对象是一个预定义了属性和方法的正则表达式对象
使用 test():
test() 方法用于检测一个字符串是否匹配某个模式，如果字符串中含有匹配的文本，则返回 true，否则返回 false。

例如：
以下实例用于搜索字符串中的字符 “e”：

var patt = /e/;
patt.test("The best things in life are free!");

字符串中含有 “e”，所以该实例输出为：true

具体实现：

1. 构造函数

const WordDictionary = function () {
    
   # 初始化一个对象字面量，承担 Map 的角色
  this.words = {
    }
};

2. 加字符串的方法

WordDictionary.prototype.addWord = function (word) {
    
  # 若该字符串对应长度的数组已经存在，则只做添加
  
  if (this.words[word.length]) {
    
    this.words[word.length].push(word)
  } else {
    
  
    # 若该字符串对应长度的数组还不存在，则先创建
    this.words[word.length] = [word]
  }
};

3. 搜索方法

WordDictionary.prototype.search = function (word) {
    
  const len = word.length
  # 1 若该字符串长度在 Map 中对应的数组根本不存在，则可判断该字符串不存在
  if (!this.words[len]) {
    
    return false
  }
  
  # 2 如果字符串中不包含‘.’，那么一定是普通字符串
  if (!word.includes('.')) {
    
    // 定位到和目标字符串长度一致的字符串数组，在其中查找是否存在该字符串
    return this.words[len].includes(word)

  }

  # 3 否则是正则表达式，要先创建正则表达式对象
  const reg = new RegExp(word)

  # 4 只要数组中有一个匹配正则表达式的字符串，就返回true
  return this.words[len].some((item) => {
    
    return reg.test(item)
  })
};

4 字符串与数字之间的转换问题（正则表达式）

描述：
请你来实现一个 atoi 函数，使其能将字符串转换成整数。

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31)

首先，该函数会根据需要丢弃无用的开头空格字符。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来；
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。

输入
“words and 987”
输出:
0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。 因此无法执行有效的转换。

输入:
“-91283472332”
输出:
-2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。因此返回 INT_MIN (−2^31)

思路：

1. 用正则匹配，有的画匹配出合法的数字串，否则返回null
2. 用卡口判断范围
3. 返回转换结果

1. 计算范围（最小-最大）

// 计算最大值
const max = Math.pow(2,31) - 1
// 计算最小值
const min = -max - 1

2. 摘除空格
   第一种：trim()方法

let str = ' +10086'
str.trim() // '+10086'

第二种：正则\s*
\s 意味着空字符，*跟在其它符号后面，意味着“前面这个符号可以出现0次或多次。
合法：可能存在的空格+正负号+数字字符串+其它字符内容，对应的正则/\s*([-\+]?[0-9]*).*/

解释：
() 圈住的内容，就是要额外存储的东西
[]中的匹配符之间是“或”的关系 ?零个或一个
\+之所以加了一个斜杠符，是因为+本身是一个有特殊作用的正则匹配符，这里我们要让它回归+字符的本义，所以要用一个\来完成转义。
[0-9]*,是 0-9 之间的整数，匹配0个或多个就算匹配成功。
最后的 .这个是任意字符的意思，.*用于字符串尾部匹配非数字的任意字符。我们看到.*是被排除捕获组之外的，所以说这个东西其实也不会被额外存储，它被“摘除”了。

3. 获取捕获结果

const reg = /\s*([-\+]?[0-9]*).*/
const groups = str.match(reg)

test()方法返回的是一个布尔值，单纯判断“是否匹配”。要想获取匹配的结果，我们需要调度match()方法，会返回第一个完整匹配（作为数组的第0项），捕获组（作为数组的第1及第1+项）。
这里我们只定义了一个捕获组，因此可以从 groups[1] 里拿到我们捕获的结果

完整代码

// 入参是一个字符串
const myAtoi = function(str) {
    
    // 编写正则表达式
    const reg = /\s*([-\+]?[0-9]*).*/
    
    #1. 得到捕获组
    const groups = str.match(reg)
    
    #2. 计算最大值
    const max = Math.pow(2,31) - 1
    // 计算最小值
    const min = -max - 1
    #3. targetNum 用于存储转化出来的数字
    let targetNum = 0
    // 如果匹配成功
    if(groups) {
    
        // 尝试转化捕获到的结构
        targetNum = +groups[1]
        // 注意，即便成功，也可能出现非数字的情况，比如单一个'+'
        if(isNaN(targetNum)) {
    
            // 不能进行有效的转换时，请返回 0
            targetNum = 0
        }
    }
    #2. 卡口判断
    if(targetNum > max) {
    
        return max
    } else if( targetNum < min) {
    
        return min
    }
    // 返回转换结果
    return targetNum
};

注意：
=+
=是赋值
+代表后面的数字为正数
=-代表后面的数字为负数
告诉编译器，不要把数字当作字符串去拼接

今天学到这咯https://juejin.cn/book/6844733800300150797/section/6844733800350482445