当前位置: 首页>后端>正文

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

预习课重要知识点回顾

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,还可以通过建索引来优化。

算法训练营第一周-学习总结,第1张
添加索引优化

算法训练营第一周-学习总结,第2张
时间复杂度分析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)

算法训练营第一周-学习总结,第3张
关键点

双端队列 Deque:

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

作业: 新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权限优先级高,取最大值或最小值

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

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

时间复杂度对比

算法训练营第一周-学习总结,第6张
时间复杂度

参考链接

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

https://www.xamrdz.com/backend/3xc1921577.html

相关文章: