超超不会飞

二叉树

二叉树是一种特殊的数据结构，有一个根节点，根节点下面有一左一右两个子节点，每个子节点又有各自的子节点，层层深入成树状。

二叉树的遍历

关于二叉树的遍历我只学习了递归遍历，非递归遍历比较复杂还是很理解。

递归遍历分为先序，中序和后序。用三个字母表示递归遍历可以很好理解：

D: 访问根节点，L： 遍历根节点的左子树，R：遍历根节点的右子树。

先序遍历：DLR

中序遍历：LDR

后序遍历：LRD

《Algorithms Unlocked》是 《算法导论》的合著者之一 Thomas H. Cormen 写的一本算法基础，算是啃CLRS前的开胃菜和辅助教材。如果CLRS的厚度让人望而生畏，这本200多页的小读本刚好合适带你入门。

书中没有涉及编程语言，直接用文字描述算法，我用 JavaScript 对书中的算法进行描述。

超越下界

之前的四个排序算法——选择排序、插入排序、归并排序、快速排序都是依赖于对排序关键字进行的比较。他们的决策依据都是“如果这个元素的排序关键字比另一个元素的排序关键字小，那么就进行相应操作，否则，进行其他操作或者什么也不做。”假如我们还是依赖这一规则，无论是简单或复杂的算法或者还没被发现的算法都无法突破这一下界（最坏情况下所需要的最小时间）。所以我们需要更改游戏规则，不让算法利用比较来进行排序。

计数排序

假设我们有一个数组，该数组内的元素都是 0~m-1 范围内的整数。例如 let array = [4, 1, 5, 0, 1, 6, 5, 1, 5, 3] 。如果我们可以知道排序关键字为 5 的元素有三个，并且刚好有 6 个元素的排序关键字小于 5，那么三个 5 应该位于位置6、7、8上。

首先我们要计算出有多少个元素的排序关键字等于某个值。比如有 3 个元素的排序关键字等于 5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// m:定义了数组array中元素的取值范围 0~m-1
function countKeysEqual(array, m) {
  // 创建一个空数组，长度为m，给每个元素赋值0
  // 为什么要有这一步，万一哪个值array里没有就会变成NaN
  let equal = [];
  for (let i = 0; i < m; i++) {
    equal[i] = 0;
  };

  for (let j = 0; j < array.length; j++) {
    // 把array中的元素作为equal数组的索引值
    // 该索引值在equal中对应的值为该元素在array中出现的次数
    let key = array[j];
    equal[key] += 1;
  }

  return equal;
}

《Algorithms Unlocked》是 《算法导论》的合著者之一 Thomas H. Cormen 写的一本算法基础，算是啃CLRS前的开胃菜和辅助教材。如果CLRS的厚度让人望而生畏，这本200多页的小读本刚好合适带你入门。

书中没有涉及编程语言，直接用文字描述算法，我用 JavaScript 对书中的算法进行描述。

二分查找

在排好序的数组中查找目标值x。在p到r区间中，总是取索引为q的中间值与x进行比较，如果array[q]大于x，则比较p到q-1区间，否则比较q+1到r区间，直到array[q]等于x或p>r。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 利用二分法在已经排好序的数组中查找值x
function binarySearch(array, x) {
  let p = 1;
  let r = array.length - 1;

  while (p <= r) {
    let q = Math.round((p + r) / 2);  //四舍五入取整

    if (array[q] === x) {
      return q;
    } else {
      if (array[q] > x) {
        // 如果q没有减一，遇到找不到x的情况，
        // 就会陷入while循环中出不来，因为p会一直等于r
        r = q - 1; 
      } else {
        p = q + 1;
      }
    }
  }

  return 'NOT-FOUND';
}

《Algorithms Unlocked》是 《算法导论》的合著者之一 Thomas H. Cormen 写的一本算法基础。

书中没有涉及编程语言，直接用文字描述算法，我用 JavaScript 对书中的算法进行描述。

循环和查找

首先是三个简单的查找。目的是从数组中查找一个特定的值。

array: 一个数组

x: 要查找的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 简单的线性查找
function linearSearch(array, x) {
  let answer = 'NOT-FOUND';

  for (let i = 0; i < array.length; i++) {
    if (array[i] === x) {
      // 虽然找到了i, 但没有返回继续查找，直到 for 结束
      answer = i;
    }
  }

  console.log(answer);
  return;
}

虽然找到了目标值，但for循环依然继续遍历直到结束，下面是优化

一直在使用Git，仅限于简单的使用，但还是记不住几个简单。在这边总结一下，加深印象，也方便查找。

安装Git

平常主要在windows和ubuntu上工作，就以windows为例，Linux和Mac平台应该也差不多，反而是windows上坑比较多。

在windows上首先要下载Git，谷歌上搜一下，傻瓜式下载安装。Linux上不同发行版会有点小差异，不过你可以输入git，系统会提示你如何进行安装。

我们可以简单的把Git看成三个部分：本地、暂存区、远程仓库。下面我们来简单介绍各部分的作用。

存入暂存区

apply,call,bine 这三兄弟经常让初学者感到疑惑。前两天准备面试时特地做了个比较，其实理解起来也不会太难。