岛田悠米

心中有梦 不负韶华

算法与数据结构打卡

发表于 更新于 分类于 阅读次数： 评论次数：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

算法与数据结构

算法与数据结构需要日常积累

刷题小技巧：

数据结构 + 算法，以类型去leetcode刷题

推荐github算法教程：代码随想录

一、leetcode刷题

2023.12.15

时间复杂度O(n)指的是最坏的情况

算法的logn，忽略底数

2023.12.16

空间复杂度O(n)，当消耗空间随着输入参数n随线性增长

计算机一般会有内存对齐的策略，提高效率

2023.12.17

二分查找：左闭右闭 注意边界

移除元素：快慢指针

2023.12.19

有序数组的平方：左右指针

长度最小的子数组：滑动窗口，也是两个指针

2023.12.20

2023.12.21

快速判断一个元素是否出现在集合里，使用哈希法

2023.12.24

两个字符char，ASCII值相加减

链表 统一的逻辑 虚拟头节点

链表最后指向null

2023.12.25

设计链表

2023.12.26

设计链表

类里面有成员变量，构造函数

dummy 虚拟的

pre cur temp 变量取名

链表的最后一个节点指向空节点

2023.12.29

虚拟头节点的使用 ListNode dummy = new ListNode(-1);

链表反转使用双指针法

找环的入口：快慢指针相遇点和head的相遇点，就是环的入口

2023.12.31

数组 length

字符串 length()

for循环内还有for，就要用j，按i、j、k顺序使用

首先是对数组循环，然后是对字符串循环

list set 是contains

map是containsKey

2024.1.2

字符串的方法都是加()的，数组的length没有()

2024.1.3

反转字符串(双指针法)

2024.1.4

KMP算法 字符串匹配

2024.1.6

文本串和模式串

KMP 适用于字符串查找

双指针法的复习

l r fast slow

2024.1.7

2024.1.8

双指针 l r slow fast

2024.1.9

栈与队列

队列 先进先出

栈 后进先出

构造函数：初始化类中的成员变量

栈 push 把值压入栈 pop移除栈顶元素并返回 peek返回栈顶元素

2024.1.10

deque 双向队列 Deque deque = new LinkedList(); push() pop()

2024.1.12

2024.1.13

二叉树的遍历 前序 中序 后序

二叉树的递归遍历(简单一些)

二叉树的迭代遍历 用栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

层序遍历，也可以使用递归的方式

翻转二叉树

2024.1.14

二叉树的递归和回溯

2024.1.15

相同的树-递归代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
  public boolean compare(TreeNode tree1, TreeNode tree2) {
     
      if(tree1==null && tree2==null)return true;
      if(tree1==null || tree2==null)return false;
      if(tree1.val!=tree2.val)return false;
      // 此时就是：左右节点都不为空，且数值相同的情况
      // 此时才做递归，做下一层的判断
      boolean compareLeft = compare(tree1.left, tree2.left);       // 左子树：左、 右子树：左
      boolean compareRight = compare(tree1.right, tree2.right);    // 左子树：右、 右子树：右
      boolean isSame = compareLeft && compareRight;                  // 左子树：中、 右子树：中（逻辑处理）
      return isSame;

  }
  boolean isSameTree(TreeNode p, TreeNode q) {
      return compare(p, q);
  }
}

二叉树题目大部分使用递归法可以解决

2024.1.16

二叉树 递归

2024.1.17

二叉搜索树 左边节点比根节点小 右边节点比根节点大

2024.1.18

回溯算法

回溯是递归的副产品，只要有递归就会有回溯

如何理解回溯法？

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）

1
2
3
4
5
6
7
8
9
10
11
12
13
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

模板：for循环横向遍历，递归纵向遍历，回溯不断调整结果集

2024.1.19

回溯集合一般用的是LinkedList removeLast()方法移除集合最后的元素

2024.1.20

image-20240120155920746

2024.1.21

void backTracking(){

​ 横向 for

​ 纵向 递归

}

2024.1.22

贪心算法：局部最优推出全局最优 大部分使用for循环比较最优解

2024.1.23

2024.1.24

贪心算法：寻找最优解

2024.1.25

2024.1.26

2024.1.27

动态规划从上一个状态推导而来，贪心局部直接选最优的

2024.1.28

动态规划：

第三层楼梯的状态可以由第二层和第一层楼梯推导出来，可以想到动态规划

动态规划数组为dp

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

2024.1.29

背包问题：01背包和完全背包

2024.1.30

2024.1.31

背包问题：两层for循环

2024.2.1

背包问题：两个for循环

2024.2.3

动态规划：dp数组

当前状态和前面状态会有一种依赖关系，那么这种依赖关系都是动规的递推公式

2024.2.4

股票系列

2024.2.5

股票系列

2024.2.7

子序列系列

2024.2.8

2024.2.9

动规5部曲

2024.2.10

单调栈

2024.2.11

深度优先搜索理论基础 广度优先搜索理论基础

深度优先搜索dfs 广度优先搜索bfs

广搜（bfs）是一圈一圈的搜索过程，和深搜（dfs）是一条路跑到黑然后再回溯

并查集理论基础

并查集常用来解决连通性问题。大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

十大排序

快速排序

总结：

数据量规模较小，考虑插入或选择。当元素分布有序时插入将大大减少比较和移动记录的次数，如果不要求稳定性，可以使用选择，效率略高于插入；
数据量规模中等，使用希尔排序；
数据量规模较大，考虑堆排序（元素分布接近正序或逆序）、快速排序（元素分布随机）和归并排序（稳定性）；
一般来说不使用冒泡。

二、内功修炼：图解数据结构(小傅哥)

第一章 链表

链表、双向链表、循环链表

prev next

LinkedList 底层是双向链表 查询慢增删快

第二章 数组

内存地址连续

ArrayList 底层是数组 初始值是10，每次1.5倍扩容

扩容完成后，将旧的空间数组迁移到新的空间数组

第三章 队列

单端队列queue 双端队列deque

队列没有特定的容量，deque双端队列可以是LinkedList

PriorityQueue 优先队列

单端队列的实现类：

  • PriorityQueue：非阻塞、非线程安全、无边界，支持优先级队列实现类。
  • ConcurrentLinkedQueue：非阻塞、线程安全、无边界，基于链接节点的队列实现类。
  • ArrayBlockingQueue：阻塞、线程安全、有边界，创建的时候指定大小，一旦创建容量不可改变实现类，默认是不保证线程的公平性，不允许向队列中插入null元素。
  • LinkedBlockingQueue：阻塞、线程安全、可选有边界，一个由链表结构组成的可选有界阻塞队列实现类，如果未指定容量，那么容量将等于Integer.MAX_VALUE。
  • PriorityBlockingQueue：阻塞、线程安全、无边界，支持优先级排序的无边界阻塞队列实现类。
  • DelayQueue：阻塞、线程安全、无边界，使用优先级队列实现的无界阻塞队列实现类，只有在延迟期满时才能从中提取元素。
  • SynchronousQueue：阻塞、线程安全、无数据队列，不存储元素、没有内部容量的阻塞队列实现类。

第四章 栈

栈 push添加 pop弹出

后进先出

栈使用 ArrayDeque

第五章 哈希表

哈希散列 即HashMap

第六章 堆

小堆（根节点最小） 大堆（根节点最大）

MaxHeap heap = new MaxHeap() 堆

第七章 字典树

字典树的核心功能：把所有以ba开头的单词全部检索出来了

第八章 二分搜索树

二叉搜索树：右边的值比根节点大，左边的值比根节点小

第九章 平衡二叉树 AVL Tree

左旋、右旋、左旋+右旋、右旋+左旋

第十章 2-3树

2-3树靠旋转调整树高

第十一章 红黑树

红黑树是一种自平衡二叉查找树

红黑树和2-3树的关系：

第十二章 并查集 Disjoint-Set

什么是并查集？

第十三章 图

第十四章 布隆过滤器