声明：本笔记是根据掘金小册总结的，如果要学习更多细节，请移步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}// 默认返回 falsereturn 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 只要数组中有一个匹配正则表达式的字符串，就返回truereturn 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)) {// 不能进行有效的转换时，请返回 0targetNum = 0}}#2. 卡口判断if(targetNum > max) {return max} else if( targetNum < min) {return min}// 返回转换结果return targetNum
};

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

5 BM84 最长公共前缀

输入：
["abca","abc","abca","abc","abcc"]
返回值：
"abc"

function longestCommonPrefix( strs ) {if(!strs.length) return "";let res=strs[0];for(let str of strs){for(let i=0;i<res.length;i++){if(str[i]!=res[i]){res=res.slice(0,i);}}}return res;
}

for(let str of strs)
直接遍历数组
abca
abc
abca
abc
abcc

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

6 找出第 N 个二进制字符串中的第 K 位

1545. 找出第 N 个二进制字符串中的第 K 位

给你两个正整数 n 和 k，二进制字符串  Sn 的形成规则如下：S1 = "0"
当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。例如，符合上述描述的序列的前 4 个字符串依次是：S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
请你返回  Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

var findKthBit = function(n, k) {let s="0";while(n--){s = s + '1' + s.split('').map((i) => i ^ 1).reverse().join('');}return s[k-1]};

注：0和1互换 i^1