Taylor

1. Arrays.asList1.1. 基本类型数组在如下代码中，我们初始化三个数字的 int[]数组，然后使用 Arrays.asList 把数组转换为 List： 12345int[] arr = {1, 2, 3};List list = Arrays.asList(arr);log.info("list:{} size:{} class:{}", list, list.size(), list.get(0).getClass()); 但，这样初始化的 List 并不是我们期望的包含 3 个数字的 List。通过日志可以发现，这个 List 包含的其实是一个 int 数组，整个 List 的元素个数是 1，元素类型是整数数组。 其原因是，只能是把 int 装箱为 Integer，不可能把 int 数组装箱为 Integer 数组。我们知道，Arrays.asList 方法传入的是一个泛型 T 类型可变参数，最终 int 数组整体作为了一个对象成为了泛型类型 T： 123publi ...

1. 递归1.1. 时空复杂度时间复杂度：O(N) N：节点个数空间复杂度：O(h) h：树的高度 1.2. 递归序 1-2-2-2-1-3-3-3-1 1.3. 前中后序就是对递归序的加工 12345678910111213public static void process(Node root) { if (root == null) { return; } // 1 前序 System.out.print(root.value + " "); process(root.left); // 2 中序 //System.out.print(root.value + " "); process(root.right); // 3 后序 //System.out.print(root.value + " "); } 1.4. 层序遍历宽度优先遍历 1234567891011121314publi ...

1. 动态数据结构所谓动态查找就是查找的过程中存在元素的删除和插入，这样就对实现查找的数据结构有一定的挑战，因为在每次删除和插入时都要调整数据结构，来保持秩序。 可以作为查找数据结构的包括： 线性结构：数组、链表 非线性结构：平衡树 链表虽然通过增加指针域提升了自由度，但是却导致数据的查询效率恶化。特别是当链表长度很长的时候，对数据的查询还得从头依次查询，这样的效率会更低。跳表的产生就是为了解决链表过长的问题，通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。 2. 什么是跳表跳跃表(简称跳表)由美国计算机科学家William Pugh发明于1989年。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。 跳表(SkipList，全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构，跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来 ...

1. 算法分类 内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。 2. 算法比较 3. 冒泡排序(bubble sort)3.1. 算法思想从左到右，两两比较，每轮确定一个数，共N-1轮，每一轮比较和交换次数都是N-1到1的递减数列 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 3.2. 代码实现123456789101112131415161718192021public static void bubbleSort(int[] arr) { int temp = 0; boolean flag = f ...

1. 什么是链表链表(Linked list)，相较于数组，除了数据域，还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问，使得链表的自由度更高。 这表现在对节点进行增加和删除时，只需要对上一节点的指针地址进行修改，而无需变动其它的节点。不过事物皆有两极，指针带来高自由度的同时，自然会牺牲数据查找的效率和多余空间的使用。 2. 内存模型数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。 而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。 3. 链表的分类链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个 ...

1. 迭代方法1.1. 代码实现1234567891011public static ListNode iterate(ListNode head) { ListNode prev = null, curr, next; curr = head; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } 1.2. 理解要点1.2.1. 初始化变量 1.2.2. 移动指针处理下一个节点：prev移动到curr位置：prev = currcurr移动到下一个节点位置：curr = next然后继续，暂存指针next = curr.next，改变指针curr.next = prev 2. 递归方法2.1. 代码实现123456789public static ListNode rec ...

1. 什么是数组数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 1.1. 线性表顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。另外，在计算机内存中以 数组 的形式保存的线性表，称为顺序表。 而与它相对立的概念是 非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。 1.2. 连续 - 相同连续的内存空间和相同类型的数据 1.3. 数组的使用 2. 随机访问我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10] 来举例。在我画的这个图中，计算机给数组 a[10]，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址： ...

1. 队列队列：是一个 有序列表，可以用 数组 或 链表 实现。特点：遵循 先入先出 原则。队尾入队，队头出队。即：先存入的数据，先取出。 2. 假溢出系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为”假溢出”。因为队列遵从从队尾存入数据，从队头取数据，所以红框部分的空间就不能继续存入新的数据，此时队列有多余的空间，却不能存入值，这种现象就叫做假溢出现象。数组中元素已出队位置需要循环利用。 3. 如何循环 rear 指向队列尾的实际位置的后一个位置。并且rear和front的初始值均为0而且默认希望空出一个空间不能存放数据，是因为如果不空闲空间，那么队列满和队列为空的条件会发生表意冲突(如上图中图a和图d1，rear和front在初始和队满时都会同时处在一个位置)，为了区分，rear指向最后一个元素的后一个位置，利用取模巧妙表达队满时的位置状态。因此队列满的条件应该如下：队列满： (rear + 1) % maxSize == front队列空： rear == front队列中有效数据的个数是：( rear + maxSize - front ) % maxSi ...

1. BF(Brute-Force)1.1. 算法思想BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。从名字可以看出，这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高。　 作为最简单、最暴力的字符串匹配算法，BF 算法的思想可以用一句话来概括，那就是，我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。我举一个例子给你看看，你应该可以理解得更清楚。 1.2. 代码实现 i-j+2可以理解为i-(j-1)+1，(j-1)表示失配前主串移动了几步，主串要回溯这一部分，然后再加1步。比如上图主串从i=3开始，子串从j=1开始，走到了j=5的时候发生了失配，主串要回溯(j-1)即(5-1)步之后，再从后面1步开始比对。而子串回溯到开头。 1.3. 时间复杂度从上面的算法思想和例子，我们可以看出，在极端情况下，比如主串是“aaaaa…aaaaaa”（省略号表示有很多重复的字符 a），模式串是“aaaaab”。我们每次都比 ...