这是我参与更文挑战的第 4 天，活动详情查看更文挑战

这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

110. 有效的字母异位词 (valid-anagram)

题目

这里不贴题了，leetcode打开就行，题目大意：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。你可以假设字符串只包含小写字母。

示例 1：

输入: s = "anagram", t = "nagaram"
输出: true
复制代码

示例 2：

输入: s = "rat", t = "car"
输出: false
复制代码

基本思路

其实就是比较两个单词是否用的字母相同，只是顺序不同，那说到顺序，第一想到的是排序。排完了直接比较就行了，代码非常简单，但排序(快排)至少平均时间复杂度要到 O(NLogN)。

有没有更快的解法呢，可以用 hashMap 计数方式，就是用一个 map 来记录字母分别出现次数，然后比较即可。

简单题，直接看代码吧

写法实现

排序

var isAnagram = function(s, t) {
    return s.length == t.length && s.split('').sort().join('') === t.split('').sort().join('')
};

let s = "anagram", t = "nagaram"
console.log(isAnagram(s, t))
复制代码

Map 计数

var isAnagram = function(s, t) {
    // 第一步还是先判断下长度
    if (s.length !== t.length) {
        return false;
    }
    // 由于字符串只包含 26 个小写字母, 因此我们可以维护一个长度为 26 的 hashTable
    // 初始化为 0 代表字母出现过 0次
    const table = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        table[s.codePointAt(i) - 'a'.codePointAt(0)]++;
    }
    // console.log(table)
    //   a ,b, c, d, e, ..., z
    // [ 3, 0, 0, 1, 0, ..., 0 ] 这是 table 的打印 
    // 代表对应的 a 有 3 个, d 有 1个...

    // 然后遍历 t 字符串，用对应位置做减法
    for (let i = 0; i < t.length; i++) {
        // 对应位置的数量减 1
        table[t.codePointAt(i) - 'a'.codePointAt(0)]--;
        // 如果发现有个位置数量小于 0，则说明 t 包含一个不在 s 中的额外字符，返回 false 即可
        if (table[t.codePointAt(i) - 'a'.codePointAt(0)] < 0) {
            return false;
        }
    }

    return true;
}

let s = "anagramd", t = "nagaradm"
console.log(isAnagram(s, t)) // true
复制代码

111. 二叉搜索树的最近公共祖先 (lowest-common-ancestor-of-a-binary-search-tree)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
复制代码

示例 2：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
复制代码

基本思路

之前我们做过一个很类似的题目，叫二叉树的最近公共祖先

当然，二叉搜索树也是二叉树，用上题做法也完全可行，但是我们利用二叉搜索树性质会更简便。

其实就是我们分别判断 p,q 的值和当前 root 的大小情况：

p 和 q 值均小于 root.val，根据BST性质，p，q 都在左子树
p 和 q 值均大于 root.val，根据BST性质，p，q 都在右子树
要么就是一个大于，一个小于，说明分开了，那么 root 就是他们的最近公共祖先，分叉了

写法实现

var lowestCommonAncestor = function(root, p, q) {
  // p 和 q 值`均小于 root.val`，p，q 都在左子树
  if (root.val > p.val && root.val > q.val) {
    // 继续递归左子树
    return lowestCommonAncestor(root.left, p, q)
  }
  if (root.val < p.val && root.val < q.val) {
    return lowestCommonAncestor(root.right, p, q)
  }
  // 说明分叉了，root 就是最近公共祖先，返回
  return root
};
复制代码

顺手写个迭代吧，并不是凑字数，运行速度有提升20%

var lowestCommonAncestor = function(root, p, q) {
  while (root) {
    if (root.val > p.val && root.val > q.val) {
      root = root.left
    } else if (root.val < p.val && root.val < q.val) {
      root = root.right
    } else {
      return root
    }
  }
};
复制代码

另外向大家着重推荐下这个系列的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦点击此处交个朋友
Or 搜索我的微信号infinity_9368，可以聊天说地
加我暗号 “天王盖地虎” 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧