为了确保只有合格的代码才能够提交到仓库。需要配置自动化脚本，确保代码在提交前通过了代码验证工具的检验。

实际上 git 本身就设计了生命周期钩子来完成这个任务。但是设置过程比较复杂。所以通常情况下会使用 husky 来简化配置。

[Husky](https://typicode.github.io/husky/#/)

[Git - githooks](https://git-scm.com/docs/githooks)

```bash
pnpm i husky -D
```

会创建一个 npm script

```
npm set-script prepare "husky install"
```

## githooks

### 在 commit 提交前执行 lint 代码校验

执行下方命令，以添加生命周期钩子：

```sql
npx husky add .husky/pre-commit "pnpm lint"
```

会创建 `.husky/pre-commit` 文件，其内容如下

```bash title='.husky/pre-commit'
#!/usr/bin/env sh
. "$(dirname -- "$0")/_/husky.sh"

pnpm lint
```

在每次提交时，都将会执行 lint 脚本来检查代码。

### 在 push 之前通过单元测试

不过更多的做法都是用 **github action** 配置 CI 在虚拟机上跑测试，而不是本地测试。（故这步可省略）

执行下方命令，以添加生命周期钩子：

```bash
npx husky add .husky/pre-push "pnpm test"
```

### 提交时自动检查 commit 信息是否符合要求

[commitlint - Lint commit messages](https://commitlint.js.org/#/?id=getting-started)

安装

```bash
pnpm i -g @commitlint/cli @commitlint/config-conventional
```

```bash
echo "module.exports = {extends: ['@commitlint/config-conventional']}" > commitlint.config.js
```

:::warning 注意

windows 系统请勿使用上行命令，否则会导致编码不是 UTF-8。建议直接复制文本内容到 `commitlint.config.js`

```javascript title='commitlint.config.js'
module.exports = { extends: ['@commitlint/config-conventional'] }
```

:::

将 commitlint 脚本添加到 githooks 中， 让每次提交前都验证信息是否正常。

```bash
npx husky add .husky/commit-msg "npx --no-install commitlint --edit "$1""
```

其内容如下

```bash title='.husky/commit-msg'
#!/bin/sh
. "$(dirname "$0")/_/husky.sh"

npx --no-install commitlint --edit "$1"
```

测试 commit 提交 `echo 'foo: bar' | commitlint` 将会报错，不符合 commit msg 规范。

```
echo 'foo: bar' | commitlint
⧗   input: foo: bar✖   type must be one of [build, chore, ci, docs, feat, fix, perf, refactor, revert, style, test] [type-enum]

✖   found 1 problems, 0 warnings
ⓘ   Get help: https://github.com/conventional-changelog/commitlint/#what-is-commitlint
```


husky

ESLint 是一种用于识别和报告 ECMAScript/JavaScript 代码中发现的模式的工具，目的是使代码更加一致并避免错误。

[Getting Started with ESLint](https://eslint.org/docs/latest/user-guide/getting-started)

## eslint-config

这里强烈推荐 [antfu/eslint-config](https://github.com/antfu/eslint-config)，以及大佬的文章 [Why I don't use Prettier (antfu.me)](https://antfu.me/posts/why-not-prettier)

这份 eslint 配置对于 ts 与 vue 已经足够完整，如果还有其他需求，可自行添加 rule 或使用[overrides](https://eslint.org/docs/latest/user-guide/configuring/configuration-files#how-do-overrides-work)。

## 在 Vscode 中集成 ESlint 插件

- 在 VScode 插件市场安装 [ESLint 插件](https://marketplace.visualstudio.com/items?itemName=dbaeumer.vscode-eslint)

- 开启代码保存时自动执行 ESLint 修复功能(全局设置)

```json title='.vscode/settings.json' icon='logos:visual-studio-code'
  "editor.codeActionsOnSave": {
    "source.fixAll": false,
    "source.fixAll.eslint": true,
    "source.organizeImports": false
  },
```

- 工作区示例如下

```json title='.vscode/settings.json' icon='logos:eslint'
{
  "prettier.enable": false,
  "editor.formatOnSave": false,
  "editor.codeActionsOnSave": {
    "source.fixAll.eslint": true
  }
}
```

## 在 WebStorm 中集成 ESLint 插件

> 由于 WebStorm 自动集成 ESLint，所以我们无需安装

- 进入 WebStorm 配置 ESLint 自动修复

![image-20220701081021965](https://tva1.sinaimg.cn/large/e6c9d24egy1h3r3vxs790j215p0u00vk.jpg)

## 注意事项

由于 eslint 配置相对繁琐，所以很多时候编辑器的 eslint 可能都没有生效，具体看编辑器下方状态栏或者日志输出查看ESLint状态。如果为警告（黄色感叹号）或者错误（红色），那么ESLint就是没配置好，可能缺少某些依赖文件或是配置文件写错了。

![](https://img.kuizuo.cn/image-20221002163239434.png)


eslint

[Editorconfig](https://editorconfig.org/) 有助于跨各种编辑器和 IDE 为处理同一项目的多个开发人员维护一致的编码样式。

## 使用 ESLint 做代码 lint，那么为什么还要使用 .editorconfig 呢？

- ESLint 确实包含 .editorconfig 中的一些属性，如缩进等，但并不全部包含，如 .editorconfig 中的 insert_final_newline 属性 Eslint 就没有。Eslint 更偏向于对语法的提示，如定义了一个变量但是没有使用时应该给予提醒。而 .editorconfig 更偏向于代码风格，如缩进等。
- ESLint 仅仅支持对 js 文件的校验，而 .editorconfig 不光可以检验 js 文件的代码风格，还可以对 .py（python 文件）、.md（markdown 文件）进行代码风格控制。

> 根据项目需要，Eslint 和 .editorconfig 并不冲突，同时配合使用可以使代码风格更加优雅。

## 安装 EditorConfig

[EditorConfig for VS Code](https://marketplace.visualstudio.com/items?itemName=EditorConfig.EditorConfig)

创建 `.editorconfig`，示例内容如下

```editorconfig title='.editorconfig' icon='logos:editorconfig'
# http://editorconfig.org

root = true

[*]
charset = utf-8
indent_style = space
indent_size = 2
end_of_line = lf
insert_final_newline = true
trim_trailing_whitespace = true
quote_type = single

[*.md]
insert_final_newline = false
trim_trailing_whitespace = false
```


editorconfig

## [快乐数](https://leetcode.cn/problems/happy-number)

> 编写一个算法来判断一个数 `n` 是不是快乐数。
>
> **「快乐数」** 定义为：
>
> - 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
> - 然后重复这个过程直到这个数变为 1，也可能是 **无限循环** 但始终变不到 1。
> - 如果这个过程 **结果为** 1，那么这个数就是快乐数。
>
> 如果 `n` 是 _快乐数_ 就返回 `true` ；不是，则返回 `false` 。
>
> **示例 1：**
>
> ```
> 输入：n = 19
> 输出：true
> 解释：
> 1² + 9² = 82
> 8² + 2² = 68
> 6² + 8² = 100
> 1² + 0² + 02 = 1
> ```

### 我的解法

```js
var isHappy = function (n) {
  let deep = 0
  while (n !== 1 && deep < 10) {
    const digits = n.toString().split('')

    n = 0
    digits.forEach(num => {
      n += Math.pow(num, 2)
    })

    deep++
  }

  return n === 1
}
```

这个解法其实很粗糙，通过肯定是能通过的，但有几个很明显的问题。

1. 首先在**数位分离**我采用 `n.toString().split('')` ，不过这是借用到了 js 的特性，要是换其他语言肯定不行。
2. 重复计算，比如 19 第一次计算 1² + 9² = 82，第二次计算 8² + 2² = 68，第三次计算 6² + 8² = 100 ...，这里的 8² 就可以将其结果存起来，避免重复计算。
3. 因为存在某些数(如 2)会无限循环，所以需要设置一个深度限制 deep，不然会死循环。

### 改进

在数位分离上可以依次使用 `num % 10` 来得到 个十百...位, 通过下方代码则可以得到所有位上的数字。

```js
function getDigist(nums) {
  let digits = []
  while (nums > 0) {
    digits.unshift(nums % 10)
    nums = Math.floor(nums / 10)
  }

  return digits
}

getDigist(1234)
```

而要避免重复运算最简单就是使用哈希集合，将计算过的结果存起来。

```js
const cache = {}

digits.forEach(num => {
  if (!cache[num]) {
    cache[num] = Math.pow(num, 2)
  }

  n += cache[num]
})
```

然而现在还有一个问题，就是如何处理 deep 的问题，由于官方题解中对于这部分给出[分析](https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/)，这里便不赘述了。如果一个数不是快乐数，那么它一定存在一个循环，可以将生成循环链的数字存入哈希集合中来判断是否处于无限循环中。最终代码如下

```js
var isHappy = function (n) {
  function getDigist(nums) {
    let digits = []
    while (nums > 0) {
      digits.unshift(nums % 10)
      nums = Math.floor(nums / 10)
    }
    return digits
  }

  const cache = {}
  const set = new Set()

  while (n !== 1 && !set.has(n)) {
    const digits = getDigist(n)
    set.add(n)

    n = 0
    digits.forEach(num => {
      if (!cache[num]) {
        cache[num] = Math.pow(num, 2)
      }

      n += cache[num]
    })
  }

  return n === 1
}
```

## [最长连续序列](https://leetcode.cn/problems/longest-consecutive-sequence)

> 给定一个未排序的整数数组 `nums` ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
>
> 请你设计并实现时间复杂度为 `O(n)` 的算法解决此问题。
>
> **示例 1：**
>
> ```
> 输入：nums = [100,4,200,1,3,2]
> 输出：4
> 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
> ```
>
> **示例 2：**
>
> ```
> 输入：nums = [0,3,7,2,5,8,4,6,0,1]
> 输出：9
> ```

我的解法

1. 对数组去重并排序
2. 判断 `nums[i]` === `nums[i+1] - 1`，为真则缓存当前最长序列的长度
3. 不符合条件则重新计算当前最长序列的长度，取 maxLen 和 currentLen 最大值作为返回值

```js
var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0

  nums = [...new Set(nums)]
  nums = nums.sort((a, b) => a - b)

  const n = nums.length

  let maxLen = 0
  let currentLen = 0

  for (let i = 0; i < n - 1; i++) {
    if (nums[i] === nums[i + 1] - 1) {
      currentLen++
    } else {
      maxLen = Math.max(maxLen, currentLen)
      currentLen = 0
    }
  }

  maxLen = Math.max(maxLen, currentLen) + 1

  return maxLen
}
```

### 哈希表

```js
var longestConsecutive = function (nums) {
  let numSet = new Set(nums)

  let maxLen = 0

  for (let num of numSet) {
    if (!numSet.has(num - 1)) {
      let currentNum = num
      let currentLen = 1

      while (numSet.has(currentNum + 1)) {
        currentNum++
        currentLen++
      }

      maxLen = Math.max(maxLen, currentLen)
    }
  }

  return maxLen
}
```

解释: 只有当一个数是连续序列的第一个数的情况下才会进入内层循环 `if (!numSet.has(num - 1))`，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。

## [单词规律](https://leetcode.cn/problems/word-pattern)

> 给定一种规律 `pattern` 和一个字符串 `s` ，判断 `s` 是否遵循相同的规律。
>
> 这里的 **遵循** 指完全匹配，例如， `pattern` 里的每个字母和字符串 `s` 中的每个非空单词之间存在着双向连接的对应规律。
>
> **示例1:**
>
> ```
> 输入: pattern = "abba", s = "dog cat cat dog"
> 输出: true
> ```
>
> **示例 2:**
>
> ```
> 输入:pattern = "abba", s = "dog cat cat fish"
> 输出: false
> ```
>
> **示例 3:**
>
> ```
> 输入: pattern = "aaaa", s = "dog cat cat dog"
> 输出: false
> ```

### 我的解法

```js
var wordPattern = function (pattern, s) {
    // 提取 pattern 的索引 { a: [0,3], b:[1,2] }
    const rules = {}
    pattern.split('').forEach((p, i) => {
        rules[p] ||= []
        rules[p].push(i)
    })

    const words = s.match(/[a-z]+\b/g)

    for (let value of Object.values(rules)) {
        const group = new Set()

        for (let v of value) {
            if (group.size === 0) {
                group.add(words[v])
            }

            if (!group.has(words[v])) {
                return false
            }

            group.add(words[v])
        }
    }
    return true
};
```

而对于下列数据会返回 true，显然是不符合条件的。

> pattern = "abba"
>
> s = "dog dog dog dog"

原因就在于 ab 要不同，因此就需要改进验证组 group。

于是就想到既然提取 pattern 的索引，不如也提取 words 索引，然后判断两者值

```js
var wordPattern = function (pattern, s) {
    function convertArray(arr) {
        const result = [];
        let charMap = {};

        for (let i = 0; i < arr.length; i++) {
            const char = arr[i];
            if (charMap[char] === undefined) {
                charMap[char] = [i];
            } else {
                charMap[char].push(i);
            }
        }

        for (const char in charMap) {
            result.push(charMap[char]);
        }

        return result;
    }

  	// "abba" => [[0, 3], [1, 2]]
    const patternValues = convertArray(pattern)
    // "dog cat cat dog" => [[0, 3], [1, 2]]
    const wordValues = convertArray(s.match(/[a-z]+\b/g))

    for (let i in patternValues) {
        if (JSON.stringify(patternValues[i]) !== JSON.stringify(wordValues[i])) {
            return false
        }
    }

    return true
};
```

然而我没想到，但有字母为 **constructor** 时，`wordsRules[w]`  就会变成 `wordsRules[constructor]` 相当于下图所示。

![image-20230921010005890](https://img.kuizuo.cn/202309210100004.png)

不过也好解决，因为这里的 key `a,b,dog,cat` 事实上我们都没用到。只需要把`{ a: [0,3], b: [1,2] }` 转成 `[[0,3], [1,2]]` 即可。

然而我发现 将 `"abba"` 转成 `[[0,3], [1,2]]` 在不借助 `Object.values()` 情况下是一件很困难的事情。于是既然 `{}[constructor]` 不行，那么我就用 `Map.get()` 来解决便可。贴上 `convertArray` 函数代码

```js
function convertArray(arr) {
        const result = [];
        const charMap = new Map();

        for (let i = 0; i < arr.length; i++) {
            const char = arr[i];
            if (charMap.has(char)) {
                charMap.get(char).push(i);
            } else {
                charMap.set(char, [i]);
            }
        }

        charMap.forEach((indices) => result.push(indices));

        return result;
    }
```

很显然，上述的解法缺陷很多，这里就不一一列举了，直接来看正确答案。

### 正确答案

```js
var wordPattern = function (pattern, s) {
    const word2ch = new Map();
    const ch2word = new Map();
    const words = s.split(' ');
    if (pattern.length !== words.length) {
        return false;
    }

    for (const [i, word] of words.entries()) {
        const ch = pattern[i];
        if (word2ch.has(word) && word2ch.get(word) != ch || ch2word.has(ch) && ch2word.get(ch) !== word) {
            return false;
        }
        word2ch.set(word, ch);
        ch2word.set(ch, word);
    }
    return true;
};Ï
```

要判断一个集合与另一个集合是否相同的关系叫「双射」，利用 两个哈希集合的 key 与 value 来判断便可。

 ### [同构字符串](https://leetcode.cn/problems/isomorphic-strings)

有了上题解题思路，这题就容易许多了。

```js
var isIsomorphic = function(s, t) {
    const s2t = {};
    const t2s = {};
  
    for (let i = 0; i < s.length; ++i) {
        const x = s[i], y = t[i];
        if ((s2t[x] && s2t[x] !== y) || (t2s[y] && t2s[y] !== x)) {
            return false;
        }
        s2t[x] = y;
        t2s[y] = x;
    }
    return true;
};
```







哈希表

以下是有关双指针相关算法的题目与题解。

## [移除元素](https://leetcode.cn/problems/remove-element)

> 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
>
> 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
>
> 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

### 我的解法

```js
var removeElement = function (nums, val) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === val) {
      nums.splice(i, 1)
      i--
    }
  }

  return nums.length
}
```

然而 splice 操作时间复杂度为 O(n)，并且**每次删除一个元素都会导致数组的重新排序**。因此在算法解题中应尽量避免使用数组自带方法操作

### 方法: 双指针

```js
var removeElement = function (nums, val) {
  let left = 0,
    right = nums.length
  while (left < right) {
    if (nums[left] === val) {
      nums[left] = nums[right - 1]
      right--
    } else {
      left++
    }
  }
  return left
}
```

如果题目有要求排序的话，不如将符合条件(`nums[i] !== val`)的元素移到数组头部，这样就不需要排序了。

```js
var removeElement = function (nums, val) {
  const n = nums.length
  let left = 0

  for (let right = 0; right < n; right++) {
    if (nums[right] !== val) {
      nums[left] = nums[right]
      left++
    }
  }

  return left
}
```

## [删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array)

> 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
>
> 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
>
> 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。

### 我的解法

```js
var removeDuplicates = function (nums) {
  const counter = {}
  let count = 0
  for (let i = 0; i < nums.length; i++) {
    counter[nums[i]] = (counter[nums[i]] || 0) + 1

    if (counter[nums[i]] > 2) {
      continue
    } else {
      nums[count] = nums[i]
      count++
    }
  }

  return count
}
```

思路很清晰，就是用一个计数对象来计数，然后遍历数组，如果计数大于 1，就跳过，否则就赋值。不过我这里引入了 counter 对象，因此空间复杂度为 O(k)，其中 k 表示不同元素的数量。

如果以我这个思路去解决 [删除有序数组中的重复项 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii) 解决题目就会特别容易，只需要将 > 1 换成 1 即可。不过题目要求 不使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

并且通常哈希计数针对无序而言，而题目所给定的数据又有序，因此想要解得好就需要采用其他方案。

### 方法: 双指针

由于题目声明输入 **升序排列** 的数组，因此采用快慢双指针来判断后一个元素是否等于前一个，如果不相等则说明是不同的元素，慢指针(不同数字次数)加一，快指针继续遍历。

```js
var removeDuplicates = function (nums) {
  const n = nums.length

  let fast = 1,
    slow = 1
  while (fast < n) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast]
      ++slow
    }
    ++fast
  }
  return slow
}
```

## [判断子序列](https://leetcode.cn/problems/is-subsequence)

### 我的解法(失败)

既然判断子序列，那我就把无关元素删除，然后判断最后元素是否包含即可。

```js
var isSubsequence = function (s, t) {
  t = t.replace(new RegExp(`[^${s}]`, 'g'), '')
  return t.includes(s)
}
```

然而假设输入数据为

```
s = "leetcode"
t = "yyyyyleeeytcode"
```

处理后数据为

```
s = "leetcode"
t = "leeetcode"
```

很显然这里 includes 无法判断子序列，因此这种思路不可行。

### 方法: 双指针

```js
var isSubsequence = function (s, t) {
  let i = 0,
    j = 0
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) {
      i++
    }
    j++
  }

  return i === s.length
}
```

## [两数之和 II - 输入有序数组](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted)

### 方法: 双指针

```js
function twoSum(nums, target) {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) {
      return [left, right]
    }

    if (sum > target) {
      right--
    } else if (sum < target) {
      left++
    }
  }
}
```
