算法竞赛实战笔记

封面

版权信息

作者简介

内容简介

前言

第0章 一些不那么常识的常识

0.1 本地编程环境的配置

0.1.1 在Windows系统上安装使用Dev C++

0.1.2 在MacOS系统上安装Xcode

0.2 在线评测系统——洛谷

0.2.1 注册洛谷

0.2.2 提交题目

0.2.3 团队管理

第1章 线性数据结构

1.1 数据结构

1.1.1 数据结构的定义

1.1.2 数据结构的运算

1.1.3 线性数据结构

1.2 栈

1.2.1 栈的定义

1.2.2 栈的作用

1.2.3 栈的固定数组实现

1.2.4 STL中的栈

1.2.5 括号匹配问题

1.2.6 前缀、中缀、后缀表达式

1.2.7 后缀表达式的计算

1.2.8 中缀表达式转换为后缀表达式

1.2.9 中缀表达式的计算

1.3 队列

1.3.1 队列的定义

1.3.2 队列的作用

1.3.3 队列的固定数组实现

1.3.4 STL中的队列

1.3.5 基数排序（Radix Sorting）

1.3.6 结构体的构造函数

1.3.7 队列的应用

1.4 前缀和

1.4.1 前缀和的引入

1.4.2 一维数组前缀和

1.5 动态数组

1.5.1 动态数组vector

1.5.2 STL中的动态数组

1.5.3 vector的缺点

1.5.4 vector与迭代器iterator

1.5.5 vector与C++11

1.5.6 vector的实现原理

1.6 树

1.6.1 树的相关概念

1.6.2 树的性质

1.6.3 特殊的树——二叉树

1.6.4 完全二叉树的性质

1.6.5 树的存储方式

1.6.6 树的遍历

1.6.7 知二求一

1.6.8 树的宽度优先遍历

1.7 本章习题

第2章 基础算法

2.1 贪心算法

2.1.1 贪心算法的概念

2.1.2 基础贪心问题举例

2.1.3 线段覆盖问题

2.2 高精度计算

2.2.1 C++语言中的数据类型

2.2.2 高精度加法

2.2.3 高精度减法

2.2.4 高精度乘法

2.2.5 高精度除法取余数

2.3 归并排序

2.3.1 归并

2.3.2 归并排序的时间复杂度分析

2.3.3 归并排序的应用

2.4 快速排序

2.4.1 快速排序的思想

2.4.2 快速排序的时间复杂度分析

2.5 STL

2.5.1 algorithm头文件中的函数

2.5.2 容器

2.6 本章习题

第3章 搜索算法

3.1 深度优先搜索

3.1.1 迷宫寻路与烤鸡问题

3.1.2 全排列问题与回溯

3.1.3 洪水填充（Flood Fill）算法

3.1.4 八皇后问题与剪枝

3.1.5 数独问题

3.1.6 剪枝

3.2 宽度优先搜索

3.2.1 找眼镜

3.2.2 马的遍历

3.2.3 01迷宫

3.2.4 八数码问题

3.3 本章习题

第4章 动态规划

4.1 动态规划入门

4.1.1 斐波那契数列

4.1.2 数字三角形

4.1.3 递推+填表

4.2 动态规划解题步骤

4.2.1 分解子问题

4.2.2 确定状态