算法和数据结构入门

算法和数据结构入门

数据结构树状图

学好算法和数据结构对培养编程内力很重要

3Points：

1. Chunk it up
2. Deliberate practicing
3. Feedback

知识总览

Data Structure	Algorithm
Array	Greedy
Stack/Queue	Recursion/Backtrace
PriorityQueue（heap）	Traversal
LinkedList（single/double）	Breadth-first/Depth-first search
Tree/Binary Tree	Divide and Conquer
Disjoint Set	Dynamic Programming
Trie	Binary Search
BloomFilter	Graph
LRU Cache
Binary Search Tree
Hash Table

Big O notation

注意：只看最高复杂度的运算

详见：http://bigocheatsheet.com/

时间复杂度

数组 Array

线性表的两种结构

1. 数组是地址连续的
2. Memory Controller 访问任何一个位置的数组下标的时间复杂度 O(1)
3. 插入和删除数组的时间复杂度 O(n)

链表可以改善插入和删除数组的时间复杂度

链表 Linked List

链式存储结构适用场景：

1. 长度未知
2. 频繁进行插入和删除操作

常见操作：

1. 插入 O(1)
   • 找到插入位置
   • 新的节点插入到元素前
   • 把前一个节点的next指针指向新节点
2. 删除 O(1)
   • 前面的节点next指针挪到后一个
   • 把跨越过的节点从内存中删除
3. 查询 O(n)

链表的查询的时间复杂度为O(n)，差于数组等顺序存储结构，所以往往需要根据实际情况来博弈（动态平衡）的选择数据结构，即结合解决问题本身的特点，具体问题具体分析。

习题：数组和链表

1. Leetcode206.反转链表
2. Leetcode24.反转链表相邻节点
3. Leetcode141.判断链表是否有环

排序 Sorting

• 快速排序
• 选择排序
• 希尔排序
• 冒泡排序

栈和队列 Stack&Queue

Stack	Queue
FILO	FIFO
Array or Linked List	Array or Doubly Linked Lisk

常用队列：消息队列

栈和队列

习题：栈和队列

1. Leetcode20.判断括号性是否合法
2. Leetcode232.225.只用堆栈实现队列/只用队列实现堆栈

优先队列 PriorityQueue

1. 队列
2. 正常进、按优先级出

实现机制：

1. Heap（Binary，Binomial，Fibonacci）
2. Binary Search Tree（红黑树）

堆 Heap

1. 小顶堆（根<左孩子<右孩子）
2. 大顶堆（根>左孩子>右孩子）

详见：https://www.wikiwand.com/en/Heap_(data_structure)

严格的Fibonacci堆相对来说效率最好

习题：堆

1. Leetcode703.判断数据流中第K大元素

   解法：维护一个Min Heap

2. Leetcode239.滑动窗口最大值

   解法：

   1. 维护一个Max Heap
   2. (推荐)双端队列deque 时间复杂度O(n)

映射和集合 Map&Set

哈希表和哈希函数 HashTable&HashFunction

例：30个学生名字放到表里面去，便于查找某一个人，时间复杂度O(1)

不同的英文字符对应不同的下标，一般可以用ASCII码，计算函数为哈希函数

有哈希碰撞的问题

解决：建立一个链表 - 拉链法

List vs Map vs Set

List：数组和链表

Map：建立映射关系（key：value）

Set：不允许有重复的元素

Set可以理解成Map的key或者List去重。

两种映射和集合的实现对比

• HashMap vs TreeMap
• HashSet vs TreeSet
• HashTable vs binary-search-tree

时间复杂度：

Hash：O(1)

Tree：O(log(n))

总结：

1. 对时间复杂度要求高使用哈希表
2. 希望以相对有序的方式储存使用二叉搜索树

习题：映射和集合

1. Leetcode242.有效的字母异位词

   解法：

   1. sort O(nlog(n))
   2. Map计数

2. Leetcode1.两数之和

   解法：

   1. 暴力拆解 O(n^2)
   2. Set x+y=10 O(n)

3. Leetcode15.三数之和

   解法：

   1. 暴力解法
   2. Set
   3. Sort -> Find

4. Leetcode18.四数之和

树 Tree

链表和树没有严格的区别

链表是特殊化的树

二叉树

• 每个节点最多只有两个孩子

• Root在level 0

• 完全二叉树

• 实现TreeNode

二叉搜索树

也称为有序二叉树，排序二叉树，可以是一棵空树。（左<中<右）

• 左子树上所有节点的值均小于它的根节点的值
• 右子树上所有节点的值均大于它的根节点的值
• 以此类推，左右子树均满足条件

代码实现

• 遍历

  • 前序遍历

    作用：复制已有二叉树，比重新构造二叉树实现效率要高很多，只需访问所有节点。

  • 中序遍历（默认升序）

  • 后序遍历

    作用：操作系统和文件系统的遍历

• 查找：

  • 查找给定值：根比较，递归

  作用：判断命中

• 删除：

  • 叶子节点
  • 中间节点
    • 只有一个子树
    • 有两个子树
      1. 在被删除的节点右子树中找到最小子节点
      2. 把被删除的值替换成最小子节点
      3. 把最小子节点原位删除

代码实现：

/**
 * 二叉树类
 * @Author   杰
 * @DateTime 2018-11-10T01:47:21+0800
 * @param    {number | string | array}    arr 如果是 array  初始化一个排序二叉树
 *                                            如果是 number 会生成一个树叶 key 为arr
 *                                            如果是 string 尝试转换为 number 
 *                                                 失败 返回一个 bTree 对象
 *                                                 但是 key 没有值，不会影响生成逻辑，生成逻辑判断key没有值会优先赋值
 * @return   {[object]}                     [bTree 对象]
 */
function bTree(arr) {
    if (Array.isArray(arr)) {
        this.arr = arr;
        this._init();
        return this;
    }
    if (!Number.isInteger(arr)) {
        arr = parseFloat(arr);
        if (isNaN(arr)) {
            return false;
        }
    }
    this.key = arr;
}

bTree.prototype = {
    constructor: bTree,
    /**
     * 如果传入是一个 数组 会调用这个执行生成 二叉树逻辑
     * @Author   杰
     * @DateTime 2018-11-10T01:52:54+0800
     * @return   {[void]}
     */
    _init() {
        if (this.key || !Array.isArray(this.arr)) {
            return false;
        }
        this.arr.forEach(function (v, k) {
            this._each(v);
        }.bind(this));
        delete this.arr;
    },
    /**
     * 二叉树生成核心逻辑
     * @Author   杰
     * @DateTime 2018-11-10T01:53:43+0800
     * @param    {number}                 value 传入的数值，用于生成二叉树
     * @return   {object}                       this
     */
    _each(value) {
        if (!this.key) {
            this.key = value;
            return this;
        }
        if (this.key > value) {
            if (!this.left) {
                return this._setKey('left', value);
            }
            return this.left._each(value);
        } else if (this.key < value) {
            if (!this.right) {
                return this._setKey('right', value);
            }
            return this.right._each(value);
        }
        if (!this.left) {
            return this._setKey('left', value);
        }
        if (!this.right) {
            return this._setKey('right', value);
        }
        var l = this.left;
        this._setKey('left', value);
        this.left.left = l;
        return this;
    },
    /**
     * 构造一个含有 value 值的 对象 放在 name 属性上
     * @Author   杰
     * @DateTime 2018-11-10T01:55:12+0800
     * @param    {string}                 name  属性名
     * @param    {number}                 value 二叉树对象的 key 值
     */
    _setKey(name, value) {
        this[name] = new this.constructor(value);
        return this;
    },
    /**
     * 升序遍历二叉树
     * @Author   杰
     * @DateTime 2018-11-10T01:56:41+0800
     * @return   {[array]}                 [升序排序的数组]
     */
    up(ret) {
        ret = ret || [];
        if (this.left) {
            this.left.up(ret);
        }
        // console.log(this.key);
        ret.push(this.key);
        if (this.right) {
            this.right.up(ret);
        }
        return ret;
    },
    /**
     * 降序遍历二叉树
     * @Author   杰
     * @DateTime 2018-11-10T01:57:00+0800
     * @return   {[array]}                 [降序排序的数组]
     */
    down(ret) {
        ret = ret || [];
        if (this.right) {
            this.right.down(ret);
        }
        // console.log(this.key);
        ret.push(this.key);
        if (this.left) {
            this.left.down(ret);
        }
        return ret;
    },
    /**
     * 安全获取 升序 排序 二叉树 通过这个函数 不会报错 但是 没有值是 undefined
     * @Author   杰
     * 参数 灵活传入 可以传入一个参数用 “.” 隔开 或多个 参数 用点隔开 
     * 如 getUp('left.right.left') 或者 getUp('left.right', 'left', 'right.left')
     * @DateTime 2018-11-10T03:05:38+0800
     * @return   {[type]}                 [description]
     */
    getUp() {
        var arr = this._parseArg.apply(this, arguments);
        var ret = this._parseObj(arr);
        if (!ret) {
            return ret;
        }
        return ret.up();
    },
    /**
     * 安全获取 降序 排序 二叉树 通过这个函数 不会报错 但是 没有值是 undefined
     * @Author   杰
     * 参数 灵活传入 可以传入一个参数用 “.” 隔开 或多个 参数 用点隔开
     * 如 getDown('left.right.left') 或者 getDown('left.right', 'left', 'right.left')
     * @DateTime 2018-11-10T03:07:18+0800
     * @return   {[array | undefined]}
     */
    getDown() {
        var arr = this._parseArg.apply(this, arguments);
        var ret = this._parseObj(arr);
        if (!ret) {
            return ret;
        }
        return ret.down();
    },
    /**
     * 格式化参数
     * @Author   杰
     * @DateTime 2018-11-10T03:10:38+0800
     * @return   {[array]}
     */
    _parseArg() {
        var arg = Array.prototype.join.call(arguments, '.');
        var r = /([^\.]+)+/gi;
        var arr = arg.match(r);
        return arr;
    },
    /**
     * 通过参数数组获取二叉树对象
     * @Author   杰
     * @DateTime 2018-11-10T03:11:19+0800
     * @param    {[array]}                 arr [description]
     * @return   {[object | undefined]}
     */
    _parseObj(arr) {
        if (!Array.isArray(arr)) {
            return undefined;
        }
        arr.forEach(function (v, k) {
            if (v !== 'left' && v !== 'right') {
                return true;
            }
            if (!ret[v]) {
                ret = undefined;
                return false;
            }
            ret = ret[v];
        });
        return ret;
    }
};

var arr = [3, 10, 1, 6, 4, 7, 13, 14, 3, 8, 9];

var b = new bTree(arr);

最小生成树 spanning tree

图 Graph

树就是特殊化的图，可双向

与生活中很多东西相关

递归 Recursion

• 正常是指数级的，并不是有效的算法
• 递归优化
• 递归推断时间复杂度

未完待续ING