HoleLin's Blog

参考文献 数据结构与算法之美 递归 去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示 递归需要满足的三个条件 一个问题的解可以分解为几个子问题的解 子问题就是数据规模更小的问题。 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 存在递归终止条件 把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。 递归代码编写 写递归代码最关键的是写出递推公式，找到终止条件. 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码 编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤 拆任务，找递推，定边界 如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问 ...

参考文献 并查集 处理连通性问题 12345678910111213141516171819202122232425262728293031package com.holelin.unionfind;/** * 并查集接口 */public interface UnionFind { /** * p,q是否属于同一集合 * * @param p p表示的元素 * @param q q表示的元素 * @return 是返回tue;反之返回false; */ boolean isConnected(int p, int q); /** * 合并两个元素所属的集合 * * @param p p表示的元素 * @param q q表示的元素 */ void unionElements(int p, int q); /** * 返回并查集中元素的个数 * * @return 并查集中元素的个数 */ int getSize();} QuickFind 1234567891011121314151617181920212223242526272 ...

参考文献 数据结构与算法之美 跳表 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142package com.holelin.skiptable;/** * @Description: 极客时间<< 数据结构与算法之美>> * 跳表实现 * 跳表中存储的是正整数，并且存储的是不重复的。 * @Author: HoleLin * @CreateDate: 2020/7/16 16:22 ...

参考文献 Set 12345678910111213141516171819202122232425262728293031323334353637383940package com.holelin.set;public interface Set<E> { /** * 添加元素e * * @param e 元素e */ void add(E e); /** * 删除元素e * * @param e 元素e */ void remove(E e); /** * 查询集合中是否包含元素e * * @param e 元素e * @return 包含则返回true, 反之返回false */ boolean contains(E e); /** * 返回集合元素的个数 * * @return 集合元素的个数 */ int getSize(); /** * 判断集合是否为空 * * @return 为空返回true, 反之返回false; */ boolean isEmpty();} LinkedListSet 1234 ...

参考文献 Map 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263package com.holelin.map;/** * Map接口 * @param <K> 键 * @param <V> 值 */public interface Map<K, V> { /** * 添加元素 * * @param key 键 * @param value 值 */ void add(K key, V value); /** * 根据key移除元素 * * @param key 键 * @return 删除的元素 */ V remove(K key); /** * 判断Map中是否包含key * * @param key 键 * @return 包含返回true, 反之返回false */ boolean contains(K key); ...

参考文献 二叉树理论基础篇 理论 二叉树的高度 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始),而根节点的高度就是二叉树的最大深度 1234567 1 / \ 2 3 / \ / \ 4 5 6 7 /8 二叉树的深度 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始） 1234567 1 / \ 2 3 / \ / \ 4 5 6 7 /8 满二叉树 满二叉树是一种特殊的二叉树,除了叶子节点,每个节点都有左右两个子节点,并且所有叶子节点都在同一层上.也就是说,满二叉树的深度为h,它的节点数为2h−12^{ h - 1}2h−1. 完全二叉树 完全二叉树是一种特殊的二叉树,除了最后一层之外,其他层的节点数都是满的,并且最后一层的节点都集中在左侧.也就是说,如果最后一层的节点数为m,那么前面的所有层都是满的,并且节点数为2h−12^{h-1}2h−1, ...

参考文献 栈 先进后出(FILO) 1234567891011121314151617181920212223242526272829303132333435363738package com.holelin.stack;/** * 栈 * @param <E> 元素类型 */public interface Stack<E> { /** * 入栈 -- 将元素放入栈顶 * @param e 入栈的元素 */ void push(E e); /** * 出栈 -- 将栈顶元素出栈 * @return 栈顶元素的值 */ E pop(); /** * 获取栈顶元素,但不出栈 * @return 栈顶元素的值 */ E peek(); /** * 获取栈中元素的个数 * @return 栈中元素的个数 */ int getSize(); /** * 判断栈是否为空 * @return 栈为 ...

参考文献 堆 大顶堆 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183package com.holelin.heap;import com.holelin.arra ...

参考文献 队列 先进先出(FIFO) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647package com.holelin.queue;/** * ClassName: Queue * * @author HoleLin * @version 1.0 * @date 2019/1/21 */public interface Queue<E> { /** * 将元素添加至队尾 * * @param e 需入队的元素 */ void enqueue(E e); /** * 将队头元素出队 * * @return 队头元素的值 */ E dequeue(); /** * 获得队头元素 * * @return 队头元素 */ E getFront(); /** * 获得队中元素的个数 * ...

参考文献 指针 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量. p->next=q: p结点中的next指针存储了q结点的内存地址. 链表 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161 ...