既然语言都有这些结构和api，为什么还需要手撸练习? 1)算法问题无关语言 2)语言提供的api是有限的，当有新的功能是api不提供的，就需要改写 3)任何软件工具的底层都是最基本的算法和数据结构，这是绕不过去的 4)面试考

链表

单向链表

  1. 节点结构(可以实现成范型)

    1. public class Node {
    2.  public int value; I
    3.  public Node next;
    4.  public Node(int data) {
    5.      value = data;
    6.  }
    7. }

  2. 内存结构

    1. 要么是紧密结构：像数组一样，可以迅速算出偏移量，寻址之后把需要的元素拿出来
    2. 要么是跳转结构：一个数据域也可以往外指七八条节点（类似于图一样的结构），但是单链表除了自己的数据域外，还有一个往外跳转的指针，记录下一个节点的内存地址，通过这个地址往外跳会跳到下一个内存区域上…… ===>调指针不能调乱

image.png

  1. 单链表的链接问题，不能连断掉，也不能连错了
  2. 链表出现主要看coding能力，出现难的不多，但是也会有

双向链表

  1. 节点结构

    1. public class DoubleNode {
    2.  public int value;
    3.  public DoubleNode last; // 向前指的指针
    4.  public DoubleNode next; // 向后指的指针
    5.  public DoubleNode(int data) {
    6.      value = data;
    7.  }
    8. }

    单向链表和双向链表最简单的练习

  2. 链表相关的问题几乎都是coding问题（主要是用的技巧要记住、牢记）

  3. 这里就是熟悉结构。
  4. 链表还有哪些常见面试题，后续有专门一节来系统学习。
  5. null是系统中很干净的一个空区域，所有的null都指向那里
  6. 链表无小事，感觉题目很简单，但是一写就错（链表断了、链接错了）===>要多练、多写、多做题目

    反转

  • 单链表
    • 递归
    • 循环

      用pre和next两个变量进行reverse

  1. package class02;
  3. import java.util.ArrayList;
  5. public class Code01_ReverseList {
  7.     public static class Node {
  8.         public int value;
  9.         public Node next;
  11.         public Node(int data) {
  12.             value = data;
  13.         }
  14.     }
  16.     public static Node reverseLinkedList(Node head) {
  17.         Node pre = null;
  18.         Node next = null;
  19.         while (head != null) {
  20.             next = head.next;
  21.             head.next = pre;
  22.             pre = head;
  23.             head = next;
  24.         }
  25.         return pre;
  26.     }
  29.     // 对数器测试是用的容器（有额外空间）
  30.     // 使用动态数组，对链表遍历，将每个数组元素放到容器中去，然后再从N-1进行遍历，进行重连，最后返回N-1的节点即可
  31.     // 面试时不能用这种方法，可以用这种方式做对数器 
  32.     public static Node testReverseLinkedList(Node head) {
  33.         if (head == null) {
  34.             return null;
  35.         }
  36.         ArrayList<Node> list = new ArrayList<>();
  37.         while (head != null) {
  38.             list.add(head);
  39.             head = head.next;
  40.         }
  41.         list.get(0).next = null;
  42.         int N = list.size();
  43.         for (int i = 1; i < N; i++) {
  44.             list.get(i).next = list.get(i - 1);
  45.         }
  46.         return list.get(N - 1);
  47.     }
  50.     public static Node generateRandomLinkedList(int len, int value) {
  51.         int size = (int) (Math.random() * (len + 1));
  52.         if (size == 0) {
  53.             return null;
  54.         }
  55.         size--;
  56.         Node head = new Node((int) (Math.random() * (value + 1)));
  57.         Node pre = head;
  58.         while (size != 0) {
  59.             Node cur = new Node((int) (Math.random() * (value + 1)));
  60.             pre.next = cur;
  61.             pre = cur;
  62.             size--;
  63.         }
  64.         return head;
  65.     }
  68.     // 要求无环，有环别用这个函数
  69.     public static boolean checkLinkedListEqual(Node head1, Node head2) {
  70.         while (head1 != null && head2 != null) {
  71.             if (head1.value != head2.value) {
  72.                 return false;
  73.             }
  74.             head1 = head1.next;
  75.             head2 = head2.next;
  76.         }
  77.         return head1 == null && head2 == null;
  78.     }
  80.     public static void main(String[] args) {
  81.         int len = 50;
  82.         int value = 100;
  83.         int testTime = 100000;
  84.         for (int i = 0; i < testTime; i++) {
  85.             Node node1 = generateRandomLinkedList(len, value);
  86.             Node reverse1 = reverseLinkedList(node1);
  87.             Node back1 = testReverseLinkedList(reverse1);
  88.             if (!checkLinkedListEqual(node1, back1)) {
  89.                 System.out.println("oops!");
  90.                 break;
  91.             }
  92.         }
  93.         System.out.println("finish!");
  95.     }
  97. }
  • 双链表

    用pre和next两个变量进行reverse，与单链表类似，但是要做的工作更多一些，更复杂一些

  1. package class02;
  3. import java.util.ArrayList;
  5. public class Code01_ReverseList {
  7.     public static class DoubleNode {
  8.         public int value;
  9.         public DoubleNode last;
  10.         public DoubleNode next;
  12.         public DoubleNode(int data) {
  13.             value = data;
  14.         }
  15.     }
  17.     public static DoubleNode reverseDoubleList(DoubleNode head) {
  18.         DoubleNode pre = null;
  19.         DoubleNode next = null;
  20.         while (head != null) {
  21.             next = head.next;
  22.             head.next = pre;
  23.             head.last = next;
  24.             pre = head;
  25.             head = next;
  26.         }
  27.         return pre;
  28.     }
  30.     public static DoubleNode testReverseDoubleList(DoubleNode head) {
  31.         if (head == null) {
  32.             return null;
  33.         }
  34.         ArrayList<DoubleNode> list = new ArrayList<>();
  35.         while (head != null) {
  36.             list.add(head);
  37.             head = head.next;
  38.         }
  39.         list.get(0).next = null;
  40.         DoubleNode pre = list.get(0);
  41.         int N = list.size();
  42.         for (int i = 1; i < N; i++) {
  43.             DoubleNode cur = list.get(i);
  44.             cur.last = null;
  45.             cur.next = pre;
  46.             pre.last = cur;
  47.             pre = cur;
  48.         }
  49.         return list.get(N - 1);
  50.     }
  52.     public static DoubleNode generateRandomDoubleList(int len, int value) {
  53.         int size = (int) (Math.random() * (len + 1));
  54.         if (size == 0) {
  55.             return null;
  56.         }
  57.         size--;
  58.         DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
  59.         DoubleNode pre = head;
  60.         while (size != 0) {
  61.             DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
  62.             pre.next = cur;
  63.             cur.last = pre;
  64.             pre = cur;
  65.             size--;
  66.         }
  67.         return head;
  68.     }
  70.     // 要求无环，有环别用这个函数
  71.     public static boolean checkDoubleListEqual(DoubleNode head1, DoubleNode head2) {
  72.         boolean null1 = head1 == null;
  73.         boolean null2 = head2 == null;
  74.         if (null1 && null2) {
  75.             return true;
  76.         }
  77.         if (null1 ^ null2) {
  78.             return false;
  79.         }
  80.         if (head1.last != null || head2.last != null) {
  81.             return false;
  82.         }
  83.         DoubleNode end1 = null;
  84.         DoubleNode end2 = null;
  85.         while (head1 != null && head2 != null) {
  86.             if (head1.value != head2.value) {
  87.                 return false;
  88.             }
  89.             end1 = head1;
  90.             end2 = head2;
  91.             head1 = head1.next;
  92.             head2 = head2.next;
  93.         }
  94.         if (head1 != null || head2 != null) {
  95.             return false;
  96.         }
  97.         while (end1 != null && end2 != null) {
  98.             if (end1.value != end2.value) {
  99.                 return false;
  100.             }
  101.             end1 = end1.last;
  102.             end2 = end2.last;
  103.         }
  104.         return end1 == null && end2 == null;
  105.     }
  107.     public static void main(String[] args) {
  108.         int len = 50;
  109.         int value = 100;
  110.         int testTime = 100000;
  111.         for (int i = 0; i < testTime; i++) {
  112.             DoubleNode node2 = generateRandomDoubleList(len, value);
  113.             DoubleNode reverse2 = reverseDoubleList(node2);
  114.             DoubleNode back2 = testReverseDoubleList(reverse2);
  115.             if (!checkDoubleListEqual(node2, back2)) {
  116.                 System.out.println("oops!");
  117.                 break;
  118.             }
  119.         }
  120.         System.out.println("finish!");
  122.     }
  124. }

把给定值都删除（把所有与给定值相等的节点删除）

  • 单链表
    • 一定要返回头节点，因为不能保证头节点不被删掉
    • 也可能会删掉多个节点
    • 删除的时候不是真的移除，而是碰到要删除的节点直接跳过，而没有碰到的话，就将节点依次往链表上挂
    • 对数器可以通过容器来实现，在数组里把所有为要删除的值都剃掉，在数组中重新连好然后返回即可
    • 对数器也可以用jdk中的linkedlist来实现
    • 直接用linkedlist可以但是练题还是要自己实现，因为系统提供的结构只是常用的功能封装进去了，工作中或者面试中可能会有个性化的需求 ```java package class02;

public class Code02_DeleteGivenValue {

  1. public static class Node {
  2.     public int value;
  3.     public Node next;
  5.     public Node(int data) {
  6.         this.value = data;
  7.     }
  8. }
  10. // 1)head == null
  11. // 2)head != null
  12. public static Node removeValue(Node head, int num) {
  13.     // head来到第一个不需要删除的位置
  14.     // 链表的边界条件处理
  15.     while (head != null) {
  16.         if (head.value != num) {
  17.             break;
  18.         }
  19.         head = head.next;
  20.     }
  21.     // head来到 第一个不需要删的位置
  22.     Node pre = head;
  23.     Node cur = head;
  24.     // 1)head == null ===> 整个链表都没了
  25.     // 2)head != null
  26.     while (cur != null) {
  27.         // 是要删除的值就跳过
  28.         // 不是要删除的值就往链表上挂===>前一节点的next指向该节点
  29.         if (cur.value == num) {
  30.             pre.next = cur.next;
  31.         } else {
  32.             pre = cur;
  33.         }
  34.         cur = cur.next;
  35.     }
  36.     return head;
  37. }

}

  2. - 双链表
  3. ```java
  4. 与单链表类似……

队列和栈

  1. 只是一种逻辑上的数据结构
  2. 逻辑概念
    1. 栈:数据先进后出，犹如弹匣
    2. 队列:数据先进先出，好似排队
  3. 用什么来实现数据和栈？===>数组和链表都能实现队列和栈

队列

双链表实现（也可以实现双端队列）

  1. 加入队列，一般从后面加
  2. 弹出队列，一般从前面弹
  3. 精髓为头尾指针的指向（移动）===>尾指针可以往回退，因为有向前指的last指针
  1. package class02;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Stack;
  7. public class Code03_DoubleEndsQueueToStackAndQueue {
  9.     public static class Node<T> {
  10.         public T value;
  11.         public Node<T> last;
  12.         public Node<T> next;
  14.         public Node(T data) {
  15.             value = data;
  16.         }
  17.     }
  19.     public static class DoubleEndsQueue<T> {
  20.         public Node<T> head;
  21.         public Node<T> tail;
  23.         public void addFromHead(T value) {
  24.             Node<T> cur = new Node<T>(value);
  25.             if (head == null) {
  26.                 head = cur;
  27.                 tail = cur;
  28.             } else {
  29.                 cur.next = head;
  30.                 head.last = cur;
  31.                 head = cur;
  32.             }
  33.         }
  35.         public void addFromBottom(T value) {
  36.             Node<T> cur = new Node<T>(value);
  37.             if (head == null) {
  38.                 head = cur;
  39.                 tail = cur;
  40.             } else {
  41.                 cur.last = tail;
  42.                 tail.next = cur;
  43.                 tail = cur;
  44.             }
  45.         }
  47.         public T popFromHead() {
  48.             if (head == null) {
  49.                 return null;
  50.             }
  51.             Node<T> cur = head;
  52.             if (head == tail) {
  53.                 head = null;
  54.                 tail = null;
  55.             } else {
  56.                 head = head.next;
  57.                 cur.next = null;
  58.                 head.last = null;
  59.             }
  60.             return cur.value;
  61.         }
  63.         public T popFromBottom() {
  64.             if (head == null) {
  65.                 return null;
  66.             }
  67.             Node<T> cur = tail;
  68.             if (head == tail) {
  69.                 head = null;
  70.                 tail = null;
  71.             } else {
  72.                 tail = tail.last;
  73.                 tail.next = null;
  74.                 cur.last = null;
  75.             }
  76.             return cur.value;
  77.         }
  79.         public boolean isEmpty() {
  80.             return head == null;
  81.         }
  83.     }
  85.     public static class MyQueue<T> {
  86.         private DoubleEndsQueue<T> queue;
  88.         public MyQueue() {
  89.             queue = new DoubleEndsQueue<T>();
  90.         }
  92.         public void push(T value) {
  93.             queue.addFromHead(value);
  94.         }
  96.         public T poll() {
  97.             return queue.popFromBottom();
  98.         }
  100.         public boolean isEmpty() {
  101.             return queue.isEmpty();
  102.         }
  104.     }
  106.     public static boolean isEqual(Integer o1, Integer o2) {
  107.         if (o1 == null && o2 != null) {
  108.             return false;
  109.         }
  110.         if (o1 != null && o2 == null) {
  111.             return false;
  112.         }
  113.         if (o1 == null && o2 == null) {
  114.             return true;
  115.         }
  116.         return o1.equals(o2);
  117.     }
  119.     public static void main(String[] args) {
  120.         int oneTestDataNum = 100;
  121.         int value = 10000;
  122.         int testTimes = 100000;
  123.         for (int i = 0; i < testTimes; i++) {
  124.             MyQueue<Integer> myQueue = new MyQueue<>();
  125.             Queue<Integer> queue = new LinkedList<>();
  126.             for (int j = 0; j < oneTestDataNum; j++) {
  127.                 int numq = (int) (Math.random() * value);
  128.                 if (queue.isEmpty()) {
  129.                     myQueue.push(numq);
  130.                     queue.offer(numq);
  131.                 } else {
  132.                     if (Math.random() < 0.5) {
  133.                         myQueue.push(numq);
  134.                         queue.offer(numq);
  135.                     } else {
  136.                         if (!isEqual(myQueue.poll(), queue.poll())) {
  137.                             System.out.println("oops!");
  138.                         }
  139.                     }
  140.                 }
  141.             }
  142.         }
  143.         System.out.println("finish!");
  144.     }
  146. }

数组实现（常见面试题，容易错）

  1. 谷歌常考笔试题：循环数组实现一个队列（ring array）
    1. 用户从end往后加，从begin开始往后拿
    2. end追赶begin，begin追赶end

image.png

  1. end与begin之间留了一个空间===>该空间就为空闲空间（追赶的感觉）
  2. 虽然是追赶的感觉，但是这种实现方式辣鸡，脑子搅到追赶的想法中去就完蛋了，面试或笔试中用追赶写就完蛋了（写不出来或者时间长）
  3. 正确思路：不去扯begin和end，而是加一个size，作为容量大小标记；不看追没追上，size只要没到最大容量就能加，加到end位置上；size只要不为0就能拿值，拿begin位置上的数===>将begin和end彻底解耦掉了
  1. package class02;
  3. public class Code04_RingArray {
  5.     public static class MyQueue {
  6.         private int[] arr;
  7.         private int pushi;    // 进来的数放哪
  8.         private int polli;    // 弹出的数从哪拿
  9.         private int size;    // 总容量
  10.         private final int limit;
  12.         public MyQueue(int limit) {
  13.             arr = new int[limit];
  14.             pushi = 0;
  15.             polli = 0;
  16.             size = 0;
  17.             this.limit = limit;    // 把limit记住
  18.         }
  20.         public void push(int value) {
  21.             if (size == limit) {
  22.                 throw new RuntimeException("队列满了，不能再加了");
  23.             }
  24.             size++;
  25.             arr[pushi] = value;
  26.             // 不要管追没追上，只要size管着，只要size没到limit必然可以加东西
  27.             pushi = nextIndex(pushi);
  28.         }
  30.         public int pop() {
  31.             if (size == 0) {
  32.                 // 运行时异常
  33.                 throw new RuntimeException("队列空了，不能再拿了");
  34.             }
  35.             size--;
  36.             int ans = arr[polli];
  37.             // 都用nextIndex，因为都是向上移动===>队列
  38.             polli = nextIndex(polli);
  39.             return ans;
  40.         }
  42.         public boolean isEmpty() {
  43.             return size == 0;
  44.         }
  46.         // 如果现在的下标是i，返回下一个位置
  47.         // 没到顶加1，到了顶就回到0===>循环
  48.         private int nextIndex(int i) {
  49.             return i < limit - 1 ? i + 1 : 0;
  50.         }
  52.     }
  54. }

栈

双链表实现

  1. 压栈，一般从头节点加
  2. 弹栈，一般也从头节点弹
  3. 精髓为头尾指针的指向（移动）===>头指针可以向后移，因为有向后指的next指针
  1. package class02;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Stack;
  7. public class Code03_DoubleEndsQueueToStackAndQueue {
  9.     public static class Node<T> {
  10.         public T value;
  11.         public Node<T> last;
  12.         public Node<T> next;
  14.         public Node(T data) {
  15.             value = data;
  16.         }
  17.     }
  19.     public static class MyStack<T> {
  20.         private DoubleEndsQueue<T> queue;
  22.         public MyStack() {
  23.             queue = new DoubleEndsQueue<T>();
  24.         }
  26.         public void push(T value) {
  27.             queue.addFromHead(value);
  28.         }
  30.         public T pop() {
  31.             return queue.popFromHead();
  32.         }
  34.         public boolean isEmpty() {
  35.             return queue.isEmpty();
  36.         }
  38.     }
  41.     public static boolean isEqual(Integer o1, Integer o2) {
  42.         if (o1 == null && o2 != null) {
  43.             return false;
  44.         }
  45.         if (o1 != null && o2 == null) {
  46.             return false;
  47.         }
  48.         if (o1 == null && o2 == null) {
  49.             return true;
  50.         }
  51.         return o1.equals(o2);
  52.     }
  54.     public static void main(String[] args) {
  55.         int oneTestDataNum = 100;
  56.         int value = 10000;
  57.         int testTimes = 100000;
  58.         for (int i = 0; i < testTimes; i++) {
  59.             MyStack<Integer> myStack = new MyStack<>();
  60.             Stack<Integer> stack = new Stack<>();
  61.             for (int j = 0; j < oneTestDataNum; j++) {
  62.                 int nums = (int) (Math.random() * value);
  63.                 if (stack.isEmpty()) {
  64.                     myStack.push(nums);
  65.                     stack.push(nums);
  66.                 } else {
  67.                     if (Math.random() < 0.5) {
  68.                         myStack.push(nums);
  69.                         stack.push(nums);
  70.                     } else {
  71.                         if (!isEqual(myStack.pop(), stack.pop())) {
  72.                             System.out.println("oops!");
  73.                         }
  74.                     }
  75.                 }
  76.             }
  77.         }
  78.         System.out.println("finish!");
  79.     }
  81. }

数组实现（常见面试题，容易错）

  1. index表示新进来的数放什么位置（index++）
  2. 弹出index-1那个数同时index—，因为原来位置放的值已经不用了，下一个要放的位置向前一个（之后放入的数会将之前的值盖掉，不需要将之前的值清理掉）
  3. index下标越界，就给用户报错，告诉用户栈满了，不能再加了

栈和队列的常见面试题

  1. 怎么用数组实现不超过固定大小的队列和栈?
    1. 栈:正常使用、用一个指针，加的时候往上涨，弹的时候往下降===>这是两个不同的方向，因此不需要使用循环数组
    2. 队列:环形数组、循环数组
  2. 实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能。

1) pop、push、getMin操作的时间复杂度都是0(1)。===>不能遍历栈，使用双栈结构 2)设计的栈类型可以使用现成的栈结构。.

递归

master公式

哈希表

  1. 哈希表中基础类型和自定义类型的区别
  2. 哈希表中非基础类型占用的空间很少，只存放内存地址（引用传递）（一般为8byte，jvm中可以压缩内存地址4byte）
  3. String及基础类型及其包装类型，有多大hash表就开多大内存装这个数据（值传递）
  4. Integer等包装类型也按值传递（比的是值，不是地址）（其他地方按引用来用，hash表里按值来用）
  5. HashSet和HashMap除了没有Value其他都一样
  6. 复杂度：O(1)

有序表

  1. TreeMap有序表：接口名
  2. 红黑树、avl树、sb树（sides balance）、跳表可以实现有序表
  3. 增删改查：O(logN)
  4. ❓java中原生的（基本类型的意思？还是原生有序表）有序表按值传递，？？？有序表不会存同样的值的东西，按大小组织
  5. 有序表比哈希表多的内容：最小的值，最大的值（firstKey、lastKey）
  6. 小于等于4离4最近的Key，大于等于4离4最近的Key
  7. 有序表比hash表强大，但是复杂度高O(logN)===>有序表是通过树实现的，而哈希表是通过散列表实现的
  8. 对于基础类型，有序表知道怎么排序，原生类型有序表天生知道怎么排序（String类型、整型）知道key怎么排序
  9. 对于非基础类型，必须自己写出比较规则，否则有序表会出错！（要提供比较器，不提供会报错）===>可以实现Comparable接口，也可以自己定义Comparator
  10. 一定要实现比较器，而不是equal方法，那个一样无法得到大小
  11. 有序表中，非基本类型（非内置结构）的空间占用很小，记内存地址