恋上数据解构与算法.md
•
阅读 617
第一季
1. 复杂度
1.1 什么是算法？
算法是用于解决特定问题的一系列的执行步骤
//比如计算a和b的和，就是计算a+b的算法
public static int plus(int a,int b){
return a+b;
}
不同算法效率差别很大
比如求斐波那契数(fibonacci number)
==定义：起点是0、1都行，第0项为0，第1项为1，重点是需要满足f(n)=f(n-1)+f(n-2)==
0，1，1，2，3，5，8，13，21，34，55，89
f(0)=0
f(1)=1
f(n)=f(n-1)+f(n-2) n>=2时
算法1：
public int fib(int n){
if(n <= 1){return n;}
return fib(n-1)+fib(n-2);
}
算法2：
public int fib(int n){
if(n <= 1){return n;}
int first = 0;
int second = 1;
// 第n个数，需要前面的数加上n-1次
for(int i=0 ; i< n-1; i++){
int sum =first + second;
first = second;
second = sum;
}
return second;
}
1.2 怎么评判一个算法的好坏
时间复杂度(time complexity)：估算程序指令的执行次数（假设每个指令的执行时间一样，那么比较**==算法的指令执行次数==**即可判断一个算法的好坏）
大O表示法
一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度
- 忽略常数、系数、低阶
- 对数阶忽略底数
注：一台1Ghz的计算机，运算速度每秒10^9次
1.3 什么是数据结构
数据结构是计算机存储、组织数据的方式
线性结构
- 数组
- 链表
- 栈
- 队列
- 哈希表
树形结构
- 二叉树
- AVL树
- 红黑树
- B树
- 堆
- Trie
- 哈夫曼树
- 并查集
图形结构
- 邻接矩阵
- 邻接表
2. 线性表
线性表是具有n个相同类型元素的有限序列（n>=0）
- a1是首节点（首元素），an是尾节点（尾元素）
- a1是a2的前驱，a2是a1的后继
2.1 数组
数组是一种顺序存储的线性表，所有元素的内存地址都是连续的
- 无法动态修改数组容量
2.1.1 动态数组接口设计
public class MyArrayList implements List{
private int size();
private E[] elements;
public static final int DEFAULT_CAPACITY = 10;
...
}
public interface List<E>{
// 元素的数量
int size(){
return 0;
}
//是否为空
boolean isEmpty(){
}
//是否包含某个元素
boolean contains(E element){
}
//添加元素到最后
void add(E element){
}
void add(int index,E element){
}
//返回index位置的元素
E get(int index){
}
//设置index位置的元素
E set(int index,E element){
}
//往index位置添加元素
void add(int index, E elemnt){z
}
//返回index位置对应的元素
E remove(int index){
}
//查看元素的位置
int indexOf(E element){
}
//清除所有元素
void clear(){
}
void rangeCheck(){
}
void rangeCheckForAdd(){
}
void ensureCapacity(int capacity){
}
}
2.1.2 临时记录
- Java把变量声明成static类型，可以保证这个变量在内存种只有一份
- 数组越界，throw new IndexOutOfBoundexception()
- ArrayList调用clear方法，其实就是把size设置为0，因为别的方法访问
前都会先判断是否>=size - size的作用就是规定能访问的范围
- ArrayList插入元素的条件判断略有不同
public void add(int index,int element){
if(index<0||index>size){
throw new IndexOutofBoundsException('...');
}
for(int i = size-1;i >= index;i--){
elements[i+1]=elemets[i];
}
elements[i+1]=element;
size++;
}
- 一个类重写finalize()函数，相当于留个遗言，这个类在销毁时会执行这个函数
- ArrayList\
- 扩容时机和缩容时机相乘不要等于1，否则容易出现
2.2 链表
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。哈希表使用的就是单链表，而不是双向链表
2.2.1 链表反转
- 链表结点定义
// 单向链表的结点元素
public static class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
// 双向链表的结点元素
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
- 反转单向链表
// 非递归
// 核心思想就是利用临时指针获取相应节点，然后再操作指针反转
public static Node reverLinkedList1(Node head){
Node pre = null;
Node cur = head;
while(cur != null){
next = cur.next;
cur.next = pre; // 这一步完成指针反转
pre = cur;
cur = next;
}
head = pre;
return head;
}
// 递归
public static Node reverLinkedList2(Node head){
//要检查链表是否是空或只有一个结点
if(head == null | head.next == null){
return head;
}
Node tmp = reverLinkedList2(head.next);
head.next.next = head;
head.next = null;
return tmp;
}
- 翻转双向链表
public static DoubleNode reverseDouble(DoubleNode head) {
DoubleNode pre = null;
DoubleNode cur = head;
DoubleNode next = null;
while (cur != null) {
next = cur.next;
cur.next = pre;
cur.last = next;
pre = cur;
cur = next;
}
head = pre;
return head;
}
2.2.2 把链表中的某个定值都删除
（1）找到第一个值不为给定值的节点，这个就是返回的头部节点
（2）用pre和cur两个指针来操作
public static Node removeValue(Node head,int num){
// 如果要删除的值正好等于head的值，就需要把head删掉，因此需要首先从头开始，找到第一个值不为num的结 // 点，这个结点就是要返回的链表的头节点
while(head != null){
if(head.value != num){
break;
}
head = head.next;
}
// cur用于遍历链表，pre用于跳过要删除的结点
Node pre = head;
Node cur = head;
while(cur != null){
if(cur.value == num){
// 如果cur的值是num，说明应该被删除，那么让pre的next指向cur的next即可
pre.next = cur.next;
}else{
// 如果的cur的值不是num，该结点就不该被删，把pre和cur都指向当前结点
pre = cur;
}
// 将cur指向下一个结点
cur = cur.next;
}
return head;
}
2.2.3 判断一个链表是否有环
用快慢指针，慢指针一次走一格，快指针一次走两格，如果有环的话，快指针肯定会与慢指针相遇，当fast==slow时，就说明链表有环。不要设置快指针一次走三步，因为有可能一下子fast指针超过了slow指针，那样需要再绕好几圈才能满足fast与slow相等这个条件
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
2.2.4 作业
- 移除链表元素（https://leetcode-cn.com/problems/remove-linked-list-elements/）
- 删除排序链表中的重复元素（https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/）
- 链表的中间结点（https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/）
2.3 栈
2.4 队列
3. 二叉树
3.1 二叉树性质
-
一棵树可以没有任何节点，称为空树
-
节点的度(degree): 子树的个数（其实也就是子节点的个数）
-
树的度：所有节点度中的最大值
-
叶子节点：度为0的节点
-
非叶子节点；度不为0的节点
-
层数(level):根节点在第1层，根节点的子节点都在第2层
-
节点的深度(depth):从根节点到当前节点的唯一路径上的节点总个数
-
节点的高度(height)：从当前节点到最远叶子节点的路径上的节点总个数
-
树的深度:所有节点深度的最大值
-
树的高度：所有节点高度的最大值
-
树的高度等于树的深度
-
有序树：树中任意节点的子节点从左到右有序
-
无序树：................没有顺序关系
-
二叉树：每个节点的度最大为2
-
二叉树形态：
- 空树
- 只有根节点
- 只有左子树
- 只有右子树
-
二叉树的性质：
- 非空二叉树的第i层，最多有pow(2,i-1)个节点，i>=1
- 高度为h的二叉树最多有pow(2,h)-1个节点，h>=1
- 对于任何一棵非空二叉树，如果叶子节点的个数为n0，度为2的节点个数为n2，则有：n0=n2+1，其实就是叶子节点个数=非叶子节点个数+1
- 二叉树的边树：T=n1=2*n2，由观察发现，每个节点上面都有一条边，除了根节点头上没有边，所以二叉树的边数T=总结点数n-1
-
真二叉树：所有节点的度要么为0，要么为2
-
满二叉树：所有节点的度要么为0，要么为2。且所有的叶子节点都在最后一层。
- 完全二叉树：可以用数组实现的二叉树
结论：如果完全二叉树总结点数量为n，则叶子节点数量为==(n+1)/2==，那么非叶子节点数量就为==n/2==
3.2 二叉搜索树（BST）
3.2.1 性质
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称BST，具有如下性质：
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- 它的左右子树也是一颗二叉搜索树
3.2.2 二叉搜索树接口
- 二叉搜索树必须具有可比较性，因为要满足BST的性质
- 二叉搜索树没有下标这个概念，因为二叉搜索树不适合用数组实现，新添加的元素位置不一定，下标无意义
int size() //元素的数量
boolean isEmpty() // 是否为空
void clear() // 清空所有元素
void add(E element) // 添加元素
void remove(E element) // 删除元素
boolean contains(E element) // 是否包含某元素