1. 基础概念

1. 算法类型

   • 计算
   • 查找
   • 排序
   • 最优决策

2. 数据结构

   • 线性结构

     数组，链表，栈，队列，哈希表

   • 树

     二叉树，多插树

   • 图

     有向图，无向图，环

3. 复杂度

   • 时间复杂度

     1. 运行时间是常数量级，则用常数 1 表示
     2. 只保留时间函数中的最高阶项
     3. 如果最高阶项存在，省去最高阶项的系数

     $T(n) = O(f(n))$，其中 $f(n)$ 是算法所消耗的时间函数

     $T(n) = 2 $ => $ O(1)$

     $ T(n) = 5logn $ => $ O(logn)$

     $ T(n) = 3n $ => $O(n)$

     $T(n) = 0.5n^2 + 0.5n $ => $O(n^2)$

     $ O(1)<O(logn)< O(n)<O(n^2) $

     其他: $O(nlogn)$ $O(n^3)$ $O(mn)$ $O(2^n) $ $O(n!)$

   • 空间复杂度

     $S(n) = O(f(n))$，其中 $f(n)$是算法所消耗的存储空间函数

2. 数组和链表基础

数组

1. 物理连续

2. 基本操作

   • 查询更新

     int[] array = new int[]{1,2,3,4};
     System.out.println(array[1]);// 查
     array[0] = 0;// 改
     

   • 删除

     int[] array = new int[]{1,2,3,4};
     
     int deletePosition = 2;
     if(deletePosition >= array.length){
     	throw new Exception("删除数字超过数组长度！");
     }
     for(int i = deletePosition;i<array.size-1;i++){
     	array[i]  = array[i+1];
     }
     
     

   • 增加

     int s = 3;
     final static int capacity = 5
     int[] array;
     int size;
     
     public MyArray(){
     	array = new Array[capacity];
       size = array.length;
     }
     
     
     public void insert(int index,int value) {
       if (index >= size) {
         int[] newArray = new int[2 * capacity]{};
         System.copyArray(array,newArray);
         array = newArray;
         size = array.length;
         insert(index,value);// 递归调用，可以自动扩容多次
       } else {
         for(int i = size-1;i>index:i--){
           array[i] = array[i-1];
         }
         array[index] = value;
       }
     }
     
     // array = new Array{1,2,3,4,5}
     // insert(2,20)
       [1,2,3,4,5] 
     	-> [1,2,3,4,5,null,null,null,null,null]
       -> [1,2,3,4,5,5,null,null,null,null]
       -> [1,2,3,4,4,5,null,null,null,null]
       -> [1,2,3,3,4,5,null,null,null,null]
       -> [1,2,2,3,4,5,null,null,null,null]
       ->
       -> [1,2,20,3,4,5,null,null,null,null]
       
     

链表

1. 非物理连续，逻辑连续

2. 基本操作

   • 查找/更新

     int targetIndex = 10;
     int targetValue = 233;
     int i = 0;
     Node curNode;
     // 查找
     while(!curNode.next
          	&& i < targetIndex) {
       curNode = curNode.next
     	i = i + 1;
     }
     // 更新
     curNode.value = targetValue;
     

   • 增加/删除

     int targetIndex = 10;
     int size = 20;
     Node insertNode;
     Node head,tail;
     
     
     // 增加
     if (size == 0) {
       head = insertNode;
       tail = insertNode;
       size = size + 1;
     } else if (targetIndex  == 0) {
       insertNode.next = head;
       head = insertNode;
       size = size + 1;
     } else if (targetIndex == size) {
       tail.next = insetNode;
     	tail = insertNode;
       size = size + 1;
     } else if (targetIndex > 0 && targetIndex < size ){
       Node preNode = get(targetIndex -1);
       Node nextNode = preNode.next;
       preNode.next =  insertNode;
       insertNode.next = nextNode;
       size = size + 1;
     } else {
       throw new Exception("超过链表长度");  
     }
     
     // 删除
     
     if (size == 0) {
       throw new Exception("链表为空");
     } else if (targetIndex  == 0) {
       Node newHead = head;
       head = head.next;
       newHead.next = null;
       size = size - 1;
     } else if (targetIndex == size) {
       tail = get(size -1);
       tail.next = null;
       size = size - 1;
     } else if (targetIndex > 0 && targetIndex < size ){
       Node preNode = get(targetIndex -1);
       Node curNode = preNode.next;
       preNode.next = curNode.next;
       curNode.next = null;
       size = size - 1;
     } else {
       throw new Exception("超过链表长度");  
     }