¶树结构

¶概念解释：

• 树的结构和现实中的树是类似的：具备根，枝干，叶子等，只不过在树结构中，这些被对应转换成了根节点，节点之间的边以及子节点这些概念，用图来展示会比较直观:

  • 

• 图中这种由一个根节点向下延申出来子节点，然后子节点继续向下延申直到没有节点，且每个节点的同一层节点没有直接联系，这种结构就是树

  1. 数结构有三个比较重要的属性:

     1. 高度：树结构的每个节点都具备高度属性，节点的高度等于节点到叶子节点的最长路径(边数)

     2. 深度：根节点到这个节点的边数

     3. 层数：节点的深度+1

     4. 树的高度 = 根节点的高度

¶散列表

¶概念:

• 我们知道数组中的数据存放在指定下标位置，预先知道下标，可以直接访问到该数据。而散列表也是基于数组的随机访问特性，根据需要存储的数据的键(key)，使用特定的散列函数(hash(key))计算出该键值对应存储的下标位置

• 散列函数可以联想一下HashMap的hash函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

//hash函数
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//put方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//内部的putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //调用hash函数的结果值和length-1进行与操作
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

• 在HashMap中存放元素时，需要先通过hash函数确定元素的key映射出来的下标位置，JDK1.8中HashMap的hash函数是通过 key 的hashCode 和自身右移16位之后的值进行异或 ， 得出一个新的hashCode作为key对应的下标位置

• 将 key.hashCode()的值和自身右移16位进行异或，也就是将自身的高位和低位进行异或运算(相同为1，不同为0)，加大低位的随机性

¶二分查找

¶概念解释：

• 二分查找也叫做折半查找，是一种在有序数据序列中进行指定数据位置查找的算法，方式是每次取数据序列的中间值和将要查找的值进行对比，因为数据有序，所以要么这个中间值大于目标值，可以继续以同样的方法向右查找；小于目标值则同理向左查找，直到找到目标值的位置或者数据不存在。

• 光从思路来看有分治法的影子：对于每一段数据范围的查找思路都是相同的，取中间值判断，然后决定下一次搜索的数据范围，再以同样的方法判断。

• 从效率的角度上来说，对于一个 n 长的数组，要查找指定值的位置，可以顺序从头至尾遍历，这样操作的时间复杂度就是O(n)；而二分查找则每次都将查找范围缩小一半，从 n 到 n/2 ，n/4,n/8…n/2^k ，效率提升十分明显

¶暂停-思考(二)

¶前言:

• 继上一次的反省总结刚好一周，想从这一次的反省中确认几件事情:

  1. 是否有解决上次的问题？
  2. 是否有修正自己的行动和思维上的缺点？
  3. 这次又有什么新的问题？该如何解决？
  4. 计划是否需要调整？

• 这种提问的方式可以比较好地引导后续的思考过程

¶暂停–思考

不要只管低着头走，一定要记得抬头看看方向

¶起因:

• 分析:
  1. 前天在学习王峥老师的《数据结构与算法之美》中递归这一章节的时候，里面很清楚地提示了，递归问题的解题思路和我们平时思维方式不一样，人的思维方式更接近于平铺直叙，而递归的方式更加抽象，适合计算机去理解，所以在求解递归问题时，最忌讳尝试直接去展开所有递归场景，这样只会把自己绕进去
  2. 虽然事先有了这样的提示，但是在尝试实际考虑求解递归问题的时候，还是无脑地按照思维惯性去思考了，明明知道正确的策略不应该是这样。结果也显而易见，浪费了时间没有任何收获
  3. 这件事让我觉得，自己的学习态度可能并不端正，因此试着反省一下，修正一下

¶过程:

¶为什么没有遵循逻辑思维？

• 分析

  1. 就这点仔细地想了一下 : 有时候在知道正确方式的情况下，还选择了错误那个，明知故犯要么出于感性，要么出于懒惰了—思维上的懒惰—不愿意认真，慢慢地动脑去思考，这是病，不能惯着

  2. 这里得套用陈皓老师的一段观点

  3. 学习是一件“逆人性”的事，就像锻炼身体一样，需要人持续付出，会让人感到痛苦，并随时想找理由放弃《左耳听风》

  4. 得承认，打游戏的我笑得很开心，但那只是虚拟游戏，而不是人生这个现实游戏

  5. 急于求成 : 因为之前在王峥老师课程的学习都是尽量维持着一天一学，学完就总结并配合实践这样的顺序来的，而前面的东西因为并没有深入学习，所以也没有多少难度，可以按照计划进行；学到递归的时候发现光看完不去理解，脑子也是一团浆糊，稍微难一点，就不行了

¶排序算法(二)

¶概述:

• 前面看到的冒泡，插入，选择排序是比较基础也比较常见的排序算法，适用于数据量不大的场景进行排序的需求，它们的时间复杂度的都是O(n^2)。接下来要了解的是复杂度为O(nlogn)两种排序算法:归并排序,快速排序；它们都用到了分治思想；
• 先抛出一个待解决的问题：如何在数组中查找到第K大的元素？

¶归并排序

• 概念：

  1. 将待排序数组从中间分成两部分

  2. 对前后部分分别进行排序

  3. 合并排序后的数组

  4. 说实话，光看这几句话，对前后排序再合并，合并数组的依据是什么?合并的数组如果前后部分如果刚好倒序，还得进行一次排序才能产生最终有序的数组，那之前的分开排序意义有多大？

¶Balanced Binary Tree

¶Problem Describe:

• Given a binary tree, determine if it is height-balanced.For this problem, a height-balanced binary tree is defined as:

• a binary tree in which the left and right subtrees of every node differ in height by no more than 1

• the input : [ 3,9,20,null.null,15,7 ]

  1 2 3 4 5

  3 / \ 9 20 / \ 15 7

• return true

¶常见排序算法

¶冒泡排序

1. 概念:

   1. 冒泡排序每次操作都会对相邻的两个元素进行比较，看看是否满足大小关系要求；
   2. 不满足则进行位置交换
   3. 一次冒泡确保有一个元素会被移动到正确的位置

2. 实现:

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

      public static void bubbleSearch(int[] nums) { int n = nums.length; //控制排序次数 for (int j = 0; j < nums.length; j++) { for (int i = 0; i < n; i++) { if (nums[i] > nums[i + 1]) { int temp = nums[i + 1]; nums[i + 1] = nums[i]; nums[i] = temp; } } } }

¶递归

¶概念:

• 直接从递归算法的特点来说，递归是对不同数据规模的同等类型问题的求解方式，通过将问题分解为子问题，求解子问题以达到解开父级问题的目的

• 这么说比较绕，引用王峥老师的《数据结构与算法之美》中的递归场景：

  当你带着你女朋友(也不知道你有没有)去电影院看电影,坐在中间某一排的时候，因为太暗了看不清，你女友问你现在坐在第几排，你也不知道，只能问前面的人他们是第几排，然后参照得出你所在的位置；

  如果你前面的人也不知道自己是第几排的话，他们就需要继续往前一排问；

  直到有人可以明确地回答自己所在的排数，最后你就间接得出了自己所在的位置。

• 这个场景中提到的求解你所在的排数的问题，涉及到几个数据：

  • 你前一排的人的排数
  • 可以明确知道自己所在排数的人
  • 前者等同于你询问自己的排数，后者决定了哪里会得到答案

¶递归的适用场景

• 从上面的例子总结一下递归算法的应用场景，当问题满足以下三个条件的时候，可以考虑使用递归
  • 一个问题可以分解为几个子问题的解
    • 上面的例子里，你前一排的人的位置，就是你所在位置的子问题
  • 这个问题与分解后的子问题，除了数据不同，求解思路完全一样
    • 你需要询问你前一排的人得到自己所在的排数，你前一排的人也需要同样询问确定他所在的位置
  • 存在递归终止条件
    • 当有人可以明确地回答你他所在的排数，你也就可以得到自己所在的排数了；

¶如何编写递归代码

• 将问题转化成代码需要先对问题进行抽象，得出问题的概念模型，王峥老师推荐的方法是：写出递推公式，找到终止条件，剩下的就是将递推公式转换成代码

• 求解 n 个台阶走法:

  • 存在 n 个台阶，你一次可以跨1步或者2步

  • 求解n个台阶会有几种走法

  • 可能第一反应是脑子里演练这个过程，它的一次次调用是怎样的，最终停止条件又是什么…这样很难得出问题的解法，递归的实现思路和我们思考问题的思路差别挺大，我们无法非常直观地自己展示出这个过程

¶队列

¶概述：

• 队列也是基于最基础的数组或者链表实现的一种数据结构，它类比生活中的例子就是排队结账的场景：排在前面的人先结账离开，需要结账的人在最后面排队，是一种先进先出，头出尾入的数据结构，和栈一样属于一种操作受限的结构
• 从头出尾入这个特点，可能很容易联想到生产-消费者模型：
  1. 生产者产生实例从尾部入队
  2. 消费者从队列头部依次获取实例进行消费
• 再考虑一下阻塞队列的概念：基于1，2的基础之上
  1. 当实例队列已满，生产者停止生产，直到接收到生产队列非满的通知，才继续进行生产入队
  2. 当实例队列为空，消费者停止获取实例的动作，直到接收到队列非空的通知，再继续获取实例消费

¶队列实现：

• 和栈比较类似，基于数组实现的队列叫顺序队列，是一种有界队列；

• 而基于链表实现的队列叫链式队列，默认实现是无界队列；

• 前者在资源控制上应用比较广泛，例如构造线程池的ArrayBlockingQueue(有界阻塞队列)