二叉树的基本算法
二叉树基本算法 二叉树的遍历 二叉树节点定义public static class Node { public int value; // 二叉树的左孩子指针 public Node left; // 二叉树的右孩子指针 public Node right; public Node(int v) { value = v; } } 递归实现先序中序后序遍历 先序：头 左 右 中序：左 头 右 后序：左 右 头 递归序: 结论：对于树的递归，每个节点实质上会到达三次， 例如上文的树结构，对于f函数，我们传入头结点，再调用左树再调用右树。 实质上经过的路径为1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3...
链表相关面试题
链表问题面试时链表解题的方法论 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法 链表面试常用数据结构和技巧 使用容器（哈希表，数组等） 快慢指针 快慢指针问题1. 输入链表头结点，奇数长度返回**中点**，偶数长度返回**上中点** `1 3 5 2 7 返回 5；1 3 2 7 返回 3` 2. 输入链表头结点，奇数长度返回**中点**，偶数长度返回**下中点** `1 3 5 2 7 返回 5；1 3 2 7 返回 2` 3. 输入链表头结点，奇数长度返回**中点前一个**，偶数长度返回**上中点前一个** `1 3 5 2 7 返回 3；1 3 2 7 返回 1` 4. 输入链表头结点，奇数长度返回**中点前一个**，偶数长度返回**下中点前一个** `1 3 5 2 7 返回 3；1 3 2 7 返回...
trie、桶排序、排序总结
上一节中从上往下(heapinsert方法)调整和从下往上(heapify)调整为什么时间复杂度不一样呢？ 从上到下的方法，时间复杂度为O(N*logN)；从下到上的方法，时间复杂度为O(N)； 从上往下：上面结点数量少，代价少；下面结点数量多，代价大； 从下往上：上面结点数量少，代价多；下面结点数量多，代价小； Trie结构...
比较器与堆
堆 满二叉树、完全二叉树、平衡二叉树、最优二叉树的基本概念和区别 堆结构就是用数组实现的完全二叉树结构 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆 堆结构的heapInsert与heapify操作 堆结构的增大和减少 优先级队列结构，就是堆结构 用数组来保存完全二叉树，如果从0下标开始存，那么推断： 这个节点的左孩子为：2*i+1 这个节点的右孩子为：2*i+2 这个节点的父亲为：(i-1)/2 但是有的会把数组的0位置弃而不用（因为计算左孩子比较多的情况，可以直接利用位运算，这样速度最快），这个公式是什么样子呢？ 这个节点的左孩子为：2*i（i<<1） 这个节点的右孩子为：2*i+1（i<<1 | 1） 这个节点的父亲为：i/2（i>>1） 有N个数,想象的树,的高度,是logN级别的 收到一个数字,调整到合适的未知,只需要探父节点,也就是logN的代价 public static class MyMaxHeap { ...
归并排序与随机排序
递归定义干什么事,大问题通过范围缩小,并且同等定义的子问题搞定,当把子问题搞定后,...
链表结构、栈、队列、递归行为、哈希表
链表结构 单向链表的定义 public class Node{ public int value; public Node next; public Node(int data){ value = data; } } 双向链表的定义 public class DoubleNode{ public int value; public Node last; public Node next; public DoubleNode(int data){ value = data; } } 单向链表和双向链表最简单的练习:链表相关的题基本上都是coding的题 单链表和双链表的逆序问题 public static Node reverseLinkedList(Node head) { Node pre = null; Node next = null; ...
归并排序和快速排序
归并排序 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法， 该算法采用经典的分治（divide-and-conquer）策略 分治法将问题分(divide)成一些小的问题然后递归求解， 而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。 图解排序算法(四)之归并排序 快速排序 荷兰国旗1.0 给定一个数组arr，和一个数num。把<=num的数放在数组的左边, >num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(1)。 思路：单指针记录<=num的范围 (start from -1)。 若arr[i] <= num，则arr[i]和<=区域的下一个数字作交换，<=区右扩，i++。 若arr[i]>num，则直接i++。 荷兰国旗2.0 给定一个数组arr，和一个数num。把<num的数放在数组的左边,...
网课LeetCode摘录
23. 合并多个有序链表 题目：https://leetcode.com/problems/merge-k-sorted-lists 核心：小根堆 输入值：一堆头节点组成的链表 过程： 链表放入后，会把头节点按从小到大的顺序排序（小根堆）。 弹出时，把头节点指向的下一个数当成头节点，放入，新的头节点会和其他头节点进行比较，自动排序（小根堆）。 代码： // 比较器： public static class ListNodeComparator implements Comparator<ListNode> { @Override public int compare(ListNode o1, ListNode o2) { // o1.val < o2.val , 则返回负数，也就是第一个参数在前面，小根堆。 return o1.val - o2.val; } } // 主函数 public static ListNode...
比较器、优先级队列、二叉树
比较器 应用在系统排序方法中 应用在与排序有关的结构中:TreeSet\TreeMap\优先级队列（堆）\有序表 优先级队列PriorityQueue+MyComparator 二叉树 先序：头 左 右 中序：左 头 右 后序：左 右 头 递归遍历 // 先序中序后序都是递归序加工而来 // 先序打印所有节点 头 左 右 public static void pre(Node head) { if (head == null) { return; } System.out.println(head.value); pre(head.left); pre(head.right); } // 先序打印所有节点 public static void in(Node head) { if (head == null) { return; } in(head.left); ...
