概述

• 数据结构(data-structure)是一门研究组织数据方式的学科，
• 程序 = 数据结构 + 算法

数据结构的分类

• 线性结构：数据元素之间存在一对一的线性关系：如数组、队列、链表和栈.
• 非线性结构：二维数组，多维数组，广义表，树，图

数据结构的存储方式

• 顺序存储：存储元素是连续的，如数组
• 链式存储：存储元素不一定是连续的。元素节点中存放数据元素以及相邻元素的地址信息，如链表

数据结构特点

• 数组：顺序存储，可以随机访问，通过索引查找对应元素，速度快，对于有序数组，还可使用二分查找提高检索速度。而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

• 链表：链式存储，靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问，查找慢；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

• 「队列(先进先出)」、「栈(先进先出)」这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。

• 「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。

• 「散列表」通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。

• 「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作简单；用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上衍生出二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题

算法的时间复杂度

• 度量一个程序(算法)执行时间方法
  • 事后统计：同一台计算机的相同状态（硬件、软件）下运行并计算使用的时间
  • 事前估算：分析算法时间复杂度
• 时间频度
  • 一个算法花费的时间与算法中语句的执行次数成正比例
  • 一个算法中的语句执行次数称为语句频度或时间频度记为T(n)。
• 时间复杂度:算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) )  为算法的渐进时间复杂度，简称时间复杂度。T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)
• 计算时间复杂度的方法：
  • 常数1代替运行时间中的所有加法常数  T(n)=n²+7n+6 => T(n)=n²+7n+1
  • 修改后的运行次数函数中，只保留最高阶项  T(n)=n²+7n+1 => T(n) = n²
  • 去除最高阶项的系数 T(n) = 4n² => T(n) = n² => O(n²)
• 平均时间复杂度：所有可能的输入实例均以等概率出现的情况下算法的运行时间。
• 最坏时间复杂度：最坏情况下的时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度

常见的时间复杂度

• 常数阶O(1):无论代码执行了多少行，只要是没有循环等复杂结构，代码的时间复杂度就都是O(1)while i<11 do i = i+1
• 对数阶O(log2n) int i = 1 ; while(i<n){ i = i*2 } 二分查找
• 线性阶O(n) for(int i=0;i<n;i++){System.out.print(i)}
• 线性对数阶O(nlog2n) for(int m=0;m<n;m++){ int 1 = 1 ; while(i<n){ i = i*2 } }
• 平方阶O(n^2) for(int i=0;i<n;i++){for(int j=0;j<n;j++){System.out.print(j)}}
• 立方阶O(n^3)
• k次方阶O(n^k)
• 指数阶O(2^n)集合里面找子集合
• O(n!)找字符串所有排列
• 归并排序O(nlog(n))
• O(nm)遍历二维数组
• 常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(nk)＜Ο(2n),尽可能避免使用指数阶的算法

算法的空间复杂度

• 算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，也是问题规模n的函数。是对一个算法在运行过程中临时占用存储空间大小的量度
• 有的算法需要占用的临时工作单元数与与解决问题的规模n成正比，例如快速排序和归并排序算法
• 算法分析主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。缓存(redis, memcache)和算法(基数排序)本质就是用空间换时间.

数据结构的基本操作框架(遍历+访问=>树=>二叉树=>前中后序遍历)

数组遍历框架，典型的线性迭代结构
void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

链表遍历框架，兼具迭代和递归结构
/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next);
}

二叉树遍历框架，典型的非线性递归遍历结构
/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

二叉树框架可以扩展为 N 叉树的遍历框架
/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

大部分算法技巧，本质上都是树的遍历问题
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

//动态规划模板
public class Solution {
    public int solve(int target, int[] items) {
        int[] dp = new int[target + 1];
        // 初始化dp数组，假设所有值都未能被正确计算过
        Arrays.fill(dp, target+1);//一般是target+1或者1
        
        // 初始状态
        dp[0] = 0;  // dp[0] = 0，因为0不需要任何数来组成

        // 遍历目标值，从1到target
        for (int i = 1; i <= target; i++) {
            // 遍历每个物品（如硬币或平方数）
            for (int j = 0; j < items.length; j++) {
                if (items[j] <= i) {//不能大于物品总值
                    dp[i] = Math.min(dp[i], dp[i - items[j]] + 1);
                }
            }
        }
        
        return dp[target] > target ? -1 : dp[target];
    }
}

算法总结

• 顺数第$k$个索引是$k-1$，倒数第$k$个索引是$len-k$，顺数第len-k+1个
• 已知大索引right，小索引left，个数right-left+1
• 数组topN问题，第几大小，第几高频，思路先去重，再堆排序，条件改为题目的条件，用hashMap构建数据与topn条件的关系
• 二叉平衡树topN问题，使用中序遍历得到数组是有序的
• 求连续总和问题，都可以用到前缀和的思想
• 记录字母出现次数或者字母最后一次出现的位置int[] arr = new int[26];arr[s.charAt(i) - 'a'] = i;
• 切割个十百千位

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }

队列和栈区别？

队列：先进先出（FIFO, First-In-First-Out）的数据结构。第一个加入队列的元素会是第一个被移除的。用于处理按顺序的任务
栈：后进先出（LIFO, Last-In-First-Out）的数据结构。最后一个加入栈的元素会是第一个被移除的。用于需要访问最新添加的数据元素