articleList
2025/04/11
posted in
数据结构和算法
简介： 架构大课核心业务数据结构内容安排
目标
课程安排
掌握程度
如何看待刷题算法这个是否重要和怎么提升
会算法的同学忽略这个哈
主要是不会算法的同学怎么快速提升和时间分配
算法题核心面试的公司：字节、微信、华为等
算法题非核心面试的公司：如阿里、美团、京东、腾讯、平安、58 等等
时间分配
23 年下半年我们小滴课堂会有专门针对《LeetCode 刷题算法大课》
说个趣事
简介： 常见基础数据结构案例串讲回顾
程序 = 数据结构 + 算法
数据结构(data structure)
算法（Algorithm）
算法复杂度
对于一个问题的处理一般有多个算法，不同算法消耗的时间一般是不同的；运行过程占用的空间资源也是不同的
根据业务需求情况，会从时间和空间两两方面进行取舍，目标是 “快” 和 “省”
用 时间复杂度 和 空间复杂度 这两方面衡量算法的性能
时间复杂度
是指算法执行所需要的时间复杂度，也就是算法执行所消耗的时间，它反映的是算法的执行效率
它衡量的是算法的运行时间随数据规模的增长而增长的程度
它用大 O 表示法来表示，其中 O(n)表示算法的时间复杂度为线性时间
下表格是 从上至下依次的时间复杂度越来越大，执行的效率越来越低
| 复杂度 | 概述 |
|---|---|
| 常数阶 O(1) | 没有循环等复杂结构，不因某个变量的增长而增长 |
| 对数阶段 O(logN) | 消耗的时间是 logN 增长，性能影响不大 |
| 线性阶 O(n) | 消耗的时间是随着 n 的变化而变化的，常见的是单层循环 |
| 平方阶 O(n²) | 把 O(n) 的代码再嵌套循环一遍，常见的是双层循环 |
| 立方阶 O(n³) | 和平方阶 O(n²)类似，O(n³)相当于三层 n 循环 |
| 指数阶(2^n) | 随着 n 增长，运算时间是指数式增长 |
| 复杂度 | 概述 |
|---|---|
| 常数阶 O(1) | 算法执行所需要的临时空间不随着某个变量 n 的大小而变化 |
| 对数阶段 O(logN) | 消耗的空间是 logN 增长，性能影响不大 |
| 线性阶 O(n) | 消耗的空间是随着 n 的变化而变化的，常见的是单层循环 |
| 平方阶 O(n²) | 把 O(n) 的代码再嵌套循环一遍，常见的是双层循环 |
| 立方阶 O(n³) | 和平方阶 O(n²)类似，O(n³)相当于三层 n 循环 |
| 指数阶(2^n) | 随着 n 增长，运算所需空间是指数式增长 |
例子（学完本大板块中你自然会解决）
建议
空间复杂度相对简单，一般对程序复杂度的分析，重点都会放在时间复杂度
现在存储资源便宜，日常开发中会利用空间来换时间，比如缓存技术，数据库冗余设计
不同的数据结构没有说一定哪个好，哪个不好，各有所长
不同的编程语言实现数据结构和算法都可以，选择自己熟悉的即可，我们这边就选择 java 语言
简介： 基础数据结构编码实现-栈
背景
需求
编码
public class ArrayStack {
private int[] arr;
private int top;
public ArrayStack(int capacity) {
arr = new int[capacity];
top = -1;
}
// 入栈
public void push(int value) {
if (top == arr.length - 1) {
throw new RuntimeException("栈已满，无法入栈");
}
// ++top 会先执行
arr[++top] = value;
}
// 出栈
public int pop() {
if (top == -1) {
throw new RuntimeException("栈为空，无法出栈");
}
// top-- 会后执行
return arr[top--];
}
// 查看栈顶元素
public int peek() {
if (top == -1) {
throw new RuntimeException("栈为空，无法查看栈顶元素");
}
return arr[top];
}
}
应用
简介： 基础数据结构编码实现-队列
需求
编码
public class MyQueue {
/**
* 数组存放数据
*/
public int [] array;
/**
* 数组长度
*/
private int length;
private int head;
private int tail;
/**
* 队列当前元素个数
*/
private int size;
public MyQueue(int length){
array = new int[length];
this.length = length;
head = 0;
tail = -1;
size = 0;
}
/**
* 入队
* @param value
* @return
*/
public boolean enQueue(int value){
//如果队列满，则返回false
if(size == length){
System.err.println("队列满了，入队失败");
return false;
}
//将元素放到队尾
array[++tail] = value;
//元素个数增加1
size++;
return true;
}
/**
* 出队，将队头的元素取出
* @return
*/
public int deQueue(){
//如果队列为空，则返回-1
if(size == 0){
return -1;
}
//取出队头的元素
int value = array[head++];
//元素个数 减1
size--;
return value;
}
/**
* 获取队列长度里面的元素数量
* @return
*/
public int getQueueSize(){
return this.size;
}
}
简介： 基础数据结构编码实现-链表
需求
编码
public class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
// 向链表中添加元素,尾部添加
public void add(int element) {
Node newNode = new Node(element);
if (head == null) {
head = newNode;
return;
}
//临时节点记录头部节点，找到最后一个节点，尾插法
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
// 从链表中删除元素
public void delete(int element) {
if (head == null) {
return;
}
//第一个节点刚好是查找的值，则第二个节点成为头部节点
if (head.val == element) {
head = head.next;
return;
}
//遍历链表查找元素
Node temp = head;
while (temp.next != null && temp.next.val != element) {
temp = temp.next;
}
if (temp.next != null && temp.next.val == element) {
temp.next = temp.next.next;
}
}
// 打印链表中的元素
public void printList() {
Node temp = head;
while (temp != null) {
System.out.println(temp.val);
temp = temp.next;
}
}
}
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}