算法训练营第一周-学习总结

预习课重要知识点回顾

1.刷题方法： 五毒神掌+切题四件套
2.如何找解题思路？暴力法+找最小最近重复子问题
3.Leetcode解题思路？国内站的讨论区+国际站投票数高的讨论区
4.算法最终优化中心思想：升维，也就是以空间换时间

第一周学习总结

【1】数组、链表、跳表

1.1 数组 Array

1.1.1 java:常用写法

// 初始化空数组
int[] a = new int[];

// 初始化值
int[] b = new int[]{1,2,3};

// 初始化固定长度的数组
int[] c = new int[5];

1.1.2 数组的插入、删除、查找的原理及源码分析

数组的插入、删除 都会意味着数组的大小要重新扩容
插入，会将后面的元素往后进行重新移动
删除，会将后面的元素往前移动，并删除最后的元素

源码分析

/**
 330:    * Appends the supplied element to the end of this list.
 331:    * The element, e, can be an object of any type or null.
 332:    *
 333:    * @param e the element to be appended to this list
 334:    * @return true, the add will always succeed
 335:    */
 336:   public boolean add(E e)
 337:   {
 338:     modCount++;
 339:     if (size == data.length)
 340:       ensureCapacity(size + 1);
 341:     data[size++] = e;
 342:     return true;
 343:   }

ensureCapacity(size + 1)是数组扩容函数。

1.1.3 时间复杂度分析

prepend O(1)
append O(1)
lookup O(1)
insert  O(n)
delete O(n)

1.2 链表 LinkedList

1.2.1 java:常用写法

List linkedList = new LinkedList<T>();

java自身实现的LinkedList 是一个双向链表，里面包含往前的first节点，往后的last节点.

1.2.2 链表LinkedList的插入、删除、查找的原理及源码分析

Java LinkedList源码

插入和删除 不会影响到其他节点的群移操作，也不涉及复制元素。

查找的话，需要一个一个节点的去找，时间复杂度是线性时间复杂O(n)

1.2.3 时间复杂度分析

prepend O(1)
append O(1)
lookup O(n)
insert  O(1)
delete O(1)

1.3 跳表 SkipList

是基于链表 进行优化的一种数据结构。其中redis中有运用skipList。

那主要优化什么地方？从链表的时间复杂度可以看到，只有lookup 随机访问查找的时间复杂度是O(n)，其余都是O(1)。那么想到查找，我们就联想到数据库的查找，数据库查找慢，我们可以优化sql，还可以通过建索引来优化。

添加索引优化
时间复杂度分析O(log(n))

缺点：索引难以维护

1.4 工程中的应用

LinkedList的应用：

LeetCode: LRU缓存 最近最少使用

skipList的应用

Redis - Skip List：跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？

1.5 常用算法解题思路及算法思想

解题思路：

1.想所有可能得解法，并记录下来, 比较得出最好的解法思路。
2.五遍刷题，反馈，看国内和国际讨论区
3.懵逼的时候？1.能不能暴力求解 2. 枚举基本情况 3. 找最近最小的重复子问题

算法思想：

1. 双指针（左右下标）移动法（同向，反向）：前提是 数组有序

【2】栈、队列、优先队列、双端队列

基本特性

栈 stack： 先入后出；添加、删除皆为O(1), 查询 O(n)
队列 queue： 先入先出; 添加、删除皆为O(1), 查询 O(n)

关键点

双端队列 Deque:

作业： 新API改写Deque

package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class DueueDemo {

    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addFirst("a");
        deque.addFirst("b");
        deque.addFirst("c");
        deque.addLast("d");
        System.out.println(deque); // [c, b, a, d]

        String str = deque.peekFirst();
        System.out.println(str); // c
        System.out.println(deque); // [c, b, a, d]

        str = deque.peekLast();
        System.out.println(str); // d
        System.out.println(deque); // [c, b, a, d]

        str = deque.pollFirst();
        System.out.println(str); // c
        System.out.println(deque); // [b, a, d]

        str = deque.pollFirst();
        System.out.println(str); // d
        System.out.println(deque); // [b, a]

        while (deque.size() > 0) {
            System.out.println(deque.pollFirst());
        }
        System.out.println(deque);
    }
}

优先队列 Priority Deque:
优点：取数，不再是先入先出或先入后出，而是按照元素的优先级取出。

场景： VIP权限优先级高，取最大值或最小值

image.png

Heap堆：实现有多种，不一定是二叉树实现的堆，也可以是斐波那契heap,或红黑树heap, treap

时间复杂度对比

时间复杂度

参考链接

• Java 的 PriorityQueue 文档
• Java 的 Stack 源码
• Java 的 Queue 源码
• Python 的 heapq
• 高性能的 container 库