1️⃣ - 数据结构与算法

• 数据结构与算法
  1. 数组、链表、堆、栈、队列等
  2. 树：前中后缀、二叉树、平衡树、排序树、红黑树、AVL树等
  3. 图：邻接矩阵、邻接表
  4. 散列表：
  5. 常见排序：冒泡、选择、插入、希尔、快排、堆排、计数、桶排、基数

知乎 https://www.zhihu.com/question/24964987

1. 线性表

• 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
• 常见的线性表结构：数组、链表、队列、栈。

1.1 数组

• 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

  1.2 链表

• 单链表

• 循环链表

1. 经典问题：约瑟夫斯问题
2. aa

• 双向链表

1.3 栈

• 定义：栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

  // 基于数组实现的顺序栈
  public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小
  // 初始化数组，申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }
  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回false，入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置，并且count加一
    items[count] = item;
    ++count;
    return true;
  }
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素，并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
  }

• 运用场景：算数表达式 （如果有括号，遇到左括号不管，遇到右括号开始运算，运算到左括号结束运算继续push）

• leetcode上关于栈的题目 20,155,232,844,224,682,496.

  1.4 队列

  

• 先进者先出，这就是典型的“队列”。 ```java

// 用数组实现的队列 public class ArrayQueue { // 数组：items，数组大小：n private String[] items; private int n = 0; // head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0;

// 申请一个大小为capacity的数组 public ArrayQueue(int capacity) { items = new String[capacity]; n = capacity; }

// 入队 public boolean enqueue(String item) { // 如果tail == n 表示队列已经满了 if (tail == n) return false; items[tail] = item; ++tail; return true; }

// 出队 public String dequeue() { // 如果head == tail 表示队列为空 if (head == tail) return null; // 为了让其他语言的同学看的更加明确，把—操作放到单独一行来写了 String ret = items[head]; ++head; return ret; } } ```

• 链表实现队列

• 循环队列

• 无锁并发队列

可以使用 cas + 数组的方式实现。

• 队列的其他应用

分布式消息队列，如 kafka 也是一种队列。

1.5 字符串

safdsaf

1.6 面试相关

• 链表题：

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点

2. 树

2.1 二叉树

2.2 aa

3. 图

3.1 邻接矩阵

aaa

3.2 邻接表

aaaa

4. 散列表

4.1 aaa

aaaa

5. 排序算法

5.1 排

6. 基础技巧

6.1 二分

分治、倍增、二分、贪心

7. 动态规划

7.1 aa

背包问题、最长子序列、计数问题