算法笔记 -- 算法思维基础

labuladong的算法小抄读书笔记-第一章语言基础

一、C++中的容器

C++的函数参数默认是传值的，如果使用容器作为参数，一般会加上 & 作为传引用。

1.1 动态数组vector

由标准库封装的数组容器，可自动扩容、缩容，int[]声明数组更加高级。

初始化方法：

int n = 7, m =8;
// 初始化int型空数组
vector<int> nums;
// 初始化大小为n的数组nums,默认值为0、
vector<int> nums(n);
// 初始化一个元素为1，3，5的数组nums
vector<int> nums{1, 3, 5};
// 初始化一个大小为n的数组nums,其值全部为2
vector<int> nums(n, 2);
// 初始化一个二维int数组dp
vector<vector<int>> dp;
// 初始化一个大小为m * n的布尔数组dp
vector<vector<bool>> dp(m, vector<boo>(n, true))；

成员函数

// 返回数组是否为空
bool empty();

// 返回数组的元素个数
size_type size();

// 返回数组最后一个元素的引用
reference back();

// 在数组尾部插入一个元素val
void push_back(const value_type& val);

// 删除数组尾部的那个元素
void pop_back();

1.2 字符串string

初始化方法

// s是一个空字符串“”
string s;
// s是字符串“abc”
string s = "abc";

成员函数

// 返回字符串的长度
size_t size();

// 判断字符串是否为空
bool empty();

// 在字符串尾部插入一个字符c
void push_back(char c);

// 删除字符串尾部的那个字符
void pop_back();

// 返回从索引pos开始，长度为len的子串
string substr(size_t pos, size_t len);

1.3 哈希表unordered_map

初始化方法

// 初始化一个key为int,value为int的哈希表
unordered_map<int, int> mapping;

// 初始化一个key为string，value为int数组的哈希表
unordered_map<string, vector<int>> mapping;

成员函数

// 返回哈希表的键值对个数
size_type size();

// 返回哈希表是否为空
bool empty();

// 返回哈希表中key出现的次数，只可能返回0\1,用于判断是否存在key
size_type count count(const key_type& key);

// 通过key来擦除哈希表中的键值对
size_type erase(const key_type& key);

1.4 哈希集合unordered_set

初始化方法

// 初始化一个存储int的哈希集合
unordered_set<int> visited;

// 初始化一个存储string的哈希集合
unordered_set<string> visited;

成员函数

// 返回哈希集合中的键值对个数
size_type size();

// 返回哈希集合是否为空
bool empty();

// 类似哈希表，如果key存在返回1，否则0
size_type count(const key_type& key);

// 向集合中插入一个元素key
pair<iterator, bool> insert(const key_type& key);

// 删除哈希集合中的元素key,删除成功返回1，key不存在返回0
size_type erase(const key_type& key);

1.5 队列queue

初始化方法

// 初始化一个存储int的队列
queue<int> q;

// 初始化一个存储string的队列
queue<string> q;

成员函数

// 返回队列是否为空
bool empty();

// 返回队列中元素的个数
size_type size();


// 将元素添加到队尾
void push(const value_type& val);

// 返回队头元素的引用
value_type& front();

// 删除队头元素
void pop();

C++中一般pop都是void类型，不会在删除的同时将元素返回

1.6 堆栈stack

初始化方法

// 初始化一个存储int的堆栈
stack<int> stk;

// 初始化一个存储string的堆栈
stack<string> stk;

成员函数

// 返回堆栈是否为空
bool empty();

// 返回堆栈中元素的个数
size_type size();

// 在栈顶添加元素
void push(const value_type& val);

// 返回栈顶元素的引用
value_type& top();

// 删除栈顶元素
void pop();

二、Java中容器

Java此处略过，本人对Java相对熟悉，不再赘述

三、Python3中的容器

列表list可以作为数组，可以作为堆栈，也可以作为队列使用：

# 数组
arr = [1, 2, 3, 4]
# 输出3
print(arr[2])
# 在列表尾部添加元素
arr.append(5)
# -1代表最后一个索引，输出5
print(arr[-1])

# 模拟堆栈
stack = []
# 把列表尾部作为栈顶
# 在堆栈添加元素
stack.append(1)
stack.append(2)
# 删除栈顶元素并返回
e1 = stack.pop()
# 查看栈顶元素
e2 = stack[-1]

元组tuple和字典dict

memo = dict()
# 二位动态规划的dp函数
def dp(i, j):
	# 元组(i, j)作为哈希表的键
    # 用in关键字查询该键是否存在于哈希表中
    if (i, j) in memo:
        # 返回键(i, j)对应的值
        return memo[(i, j)]
   	# 状态转移方程
    memo[(i,j)] = 。。。
    return memo[(i,j)]

四、算法的框架思维

4.1 存储方式

数据结构的底层存储方式只有两种：数组（顺序存储）和链表（链式存储）

4.2 基本操作

对任何数据结构，操作无非遍历+访问，再具体就是增、删、查、改

各种数据结构的访问+遍历无非两种形式：线性和非线性

线性遍历以for/while为代表，非线性以递归为代表。

数据遍历框架，是典型的线性迭代结构：

void traverse(int[] arr) {
	for (int i = 0; i < arr.length: i++) {
		// 迭代访问arr[i]
    }
}

链表遍历框架，兼具迭代和递归结构：

/*基本的单链表节点*/
class ListNode {
    int val;
    ListNode next;
}
void traverse(ListNode head) {
	for (ListNode p = head; p != null; p = p.next) {
        // 迭代遍历p.val
    }
}

void traverse(ListNode head) {
	// 前序遍历head.val
    traverse(head.next);
    // 后序遍历head.val
}

如在前序遍历处打印head.val就是正序打印链表，在后序遍历处打印head.val就是倒序打印链表

二叉树遍历框架，是典型的非递归遍历结构

/*基本的二叉树节点*/
class TreeNode {
  int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
	// 前序遍历
    traverse(root.left);
    // 中序遍历
    traverse(root.right);
    // 后序遍历
}

这里可以进一步扩展到N叉树的遍历过程

/*基本的N叉树节点*/
class TreeNode {
	int val;
	TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children) {
		traverse(child);
    }
}

4.3 刷题指南

从二叉树开始刷起训练框架思维

Leetcode-124(二叉树中的最大路径和)

Leetcode-105(从前序与中序遍历序列构造二叉树)

Leetcode-99(恢复二叉搜索树)