第一周

对于每组数据,我们有两种解法:

  1. 读取 t 后,每次处理一个数 t–;对于每个数 k,记 ans = 0;从0开始判断当前数字是否符合要求,如果符合要求,k–且ans++;直到k为0时,输出ans即是答案,此时时间复杂度为O(mn)。
  2. 因为数据有范围,我们可以先通过预处理的方法,将1-1000的数据处理好后,再读取t以及每次的k,对于k,直接返回ans[k]即可,具体方法为:新建ans[],从ans[1]开始,判断ans[i-1]+1的值是否符合要求,如果符合直接赋值,如果不符合继续+1并判断,预处理完成后,读取t,然后读取t次k,每次只需要输出ans[k]即可;此时时间复杂度为O(n)。
    具体到工程中,对于前端来说,如果用户进入到一个页面,每一步的操作需要计算很多次,我们可以在用户刚进入的时候预处理好,用户每一次的操作在o(1)的情况下即可完成。

第二周

这里我们只讲递归,因为下一周的题目和递归有关。
我们已知第0天为0,第一天为1,输出的n为当前天数的前一天的量 + 前二天的量,而前一天的量由 前二天的量 + 前三天的量,以此类推到第0天和第一天进行相加求和即可,那么我们便可以通过递归实现:
如果当前为第0天,返回0,如果为第一天,返回1,否则返回(将该数 - 1再调用函数得到的返回值) + (该数 - 2再调用函数得到的返回值)

如果你想了解更多解法,请点击

第三周

这里默认同学已经了解二叉树的基本概念,如果同学还是不太理解,请点击

前序遍历

我们需要按照访问根节点——左子树——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

定义一个节点表示当前遍历到 root 节点,按照定义,我们只要首先将 root 节点的值加入答案,然后递归调用 preorder(root.left) 来遍历 root 节点的左子树,最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。

因此我们可以写出代码:

var preorderTraversal = function(root) {
  const ans = []
  const dfs = function (root) {
    if(root === null) return
    ans.push(root.val)
    dfs(root.left)
    dfs(root.right)
  }
  dfs(root)
  return ans
};

中序遍历

我们需要按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

定义一个节点表示当前遍历到 root 节点,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树,然后将 root 节点的值加入答案,再递归调用inorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。

如果你足够细心,你会发现该题解和前序遍历近似一样,因此如果你之前没写出来,你可以按照上边的代码自己尝试写一下中序遍历。

后序遍历

我们需要按照访问左子树——右子树——根节点的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

定义一个节点表示当前遍历到 root 节点,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树,然后递归调用inorder(root.right) 来遍历 root 节点的右子树,再将 root 节点的值加入答案即可,递归终止的条件为碰到空节点。

那么请你再自己尝试一下~

第四周

排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题之一。要想成为合格的程序员,就必须理解和掌握各种排序算法。

目前,最常见的排序算法大概有七八种,其中”快速排序”(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934–)于1960时提出来的。

快速排序的思想很简单,整个排序过程只需要三步:

  1. 在数据集之中,选择一个元素作为”基准”(pivot)。
  2. 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。
  3. 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

举例来说,现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50},怎么对其排序呢?

第一步,选择中间的元素45作为”基准”。(基准值可以任意选择,但是选择中间的值比较容易理解。

第二步,按照顺序,将每个元素与”基准”进行比较,形成两个子集,一个”小于45”,另一个”大于等于45”。

第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

let quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

第五周

如果我们知道了左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为

max(l,r) + 1

而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在 O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    return root === null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1
};

第六周

这是一道很经典的二叉树问题。显然,我们从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转。如果当前遍历到的节点 \textit{root}root 的左右两棵子树都已经翻转,那么我们只需要交换两棵子树的位置,即可完成以 \textit{root}root 为根节点的整棵子树的翻转。

var invertTree = function(root) {
    if (root === null) {
        return null;
    }
    const left = invertTree(root.left);
    const right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

第七周

  • 我们从根节点开始遍历;
  • 如果当前节点的值大于 pp 和 qq 的值,说明 pp 和 qq 应该在当前节点的左子树,因此将当前节点移动到它的左子节点;
  • 如果当前节点的值小于 pp 和 qq 的值,说明 pp 和 qq 应该在当前节点的右子树,因此将当前节点移动到它的右子节点;
  • 如果当前节点的值不满足上述两条要求,那么说明当前节点就是「分岔点」。此时,pp 和 qq 要么在当前节点的不同的子树中,要么其中一个就是当前节点。
const lowestCommonAncestor = (root, p, q) => {
  while (root) {
    if (p.val < root.val && q.val < root.val) {
      root = root.left;
    } else if (p.val > root.val && q.val > root.val) {
      root = root.right;
    } else {
      break;
    }
  }
  return root;
}

第八周

要解决这道题首先我们要了解二叉搜索树有什么性质可以给我们利用,由题目给出的信息我们可以知道:如果该二叉树的左子树不为空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;它的左右子树也为二叉搜索树。

这启示我们设计一个递归函数 helper(root, lower, upper) 来递归判断,函数表示考虑以 root 为根的子树,判断子树中所有节点的值是否都在 (l,r) 的范围内(注意是开区间)。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回,否则我们要继续递归调用检查它的左右子树是否满足,如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质,在递归调用左子树时,我们需要把上界 upper 改为 root.val,即调用 helper(root.left, lower, root.val),因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时,我们需要把下界 lower 改为 root.val,即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf), inf 表示一个无穷大的值。

const helper = (root, lower, upper) => {
    if (root === null) {
        return true;
    }
    if (root.val <= lower || root.val >= upper) {
        return false;
    }
    return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity);
};

第九周

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

因此,该问题可以转化为:两个树在什么情况下互为镜像?

如果同时满足下面的条件,两个树互为镜像:

  • 它们的两个根结点具有相同的值
  • 每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数,通过「同步移动」两个指针的方法来遍历这棵树,pp 指针和 qq 指针一开始都指向这棵树的根,随后 pp 右移时,qq 左移,pp 左移时,qq 右移。每次检查当前 pp 和 qq 节点的值是否相等,如果相等再判断左右子树是否对称。

var isSymmetric = function(root) {
  const dfs = function (l, r) {
    if(l === null && r === null) return true
    if(l === null || r === null || l.val !== r.val) return false
    return dfs(l.left,r.right) && dfs(l.right,r.left)
  }
  if (root === null) return true
  return dfs(root.left,root.right)
};

第十周

这个题主要和我之前讲过的有点像,类似于一题多解

方法一:排序
将数组排序之后,即可根据数组中每个下标处的元素是否和下标相等,得到丢失的数字。

由于数组的长度是 n,因此下标范围是 [0, n-1]。假设缺失的数字是 k,分别考虑以下两种情况:

  • 当 0 <= k < n 时,对任意 0 <= i < k,都有 nums[i] = i,由于 k 缺失,因此 nums[k] = k+1,k 是第一个满足下标和元素不相等的下标;
  • 当 k = n 时,0 到 n−1 都没有缺失,因此对任意 0 <= i < n,都有 nums[i] = i。

根据上述两种情况,可以得到如下方法得到丢失的数字:

  1. 从左到右遍历数组 nums,如果存在 0 <= i < n 使得 nums[i] !== i,则缺失的数字是满足 nums[i] !==i 的最小的 i;
  2. 如果对任意 0 <= i < n,都有 nums[i] = i,则缺失的数字是 n

方法二:哈希集合
使用哈希集合,可以将时间复杂度降低到 O(n)。

首先遍历数组 nums,将数组中的每个元素加入哈希集合,然后依次检查从 0 到 n 的每个整数是否在哈希集合中,不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 O(1),因此总时间复杂度是 O(n)。

方法三:位运算
数组 nums 中有 n 个数,在这 n 个数的后面添加从 0 到 n 的每个整数,则添加了 n+1 个整数,共有 2n+1 个整数。

在 2n+1 个整数中,丢失的数字只在后面 n+1 个整数中出现一次,其余的数字在前面 n 个整数中(即数组中)和后面 n+1 个整数中各出现一次,即其余的数字都出现了两次。

根据出现的次数的奇偶性,可以使用按位异或运算得到丢失的数字。按位异或运算 ⊕ 满足交换律和结合律,且对任意整数 x 都满足 x ⊕ x = 0 和 x ⊕ 0 = x。

由于上述 2n+1 个整数中,丢失的数字出现了一次,其余的数字都出现了两次,因此对上述 2n+1 个整数进行按位异或运算,结果即为丢失的数字。

方法四:数学
将从 0 到 n 的全部整数之和记为 total,根据高斯求和公式,有:

total = n(n+1)/2

将数组 nums 的元素之和记为 arrSum,则 arrSum 比 total 少了丢失的一个数字,因此丢失的数字即为 total 与 arrSum 之差。