常用算法模板——搜索与图论
本文作者：yxc
来源: AcWing
原文地址：https://www.acwing.com/blog/content/405/
常用算法模板——搜索与图论
树与图的存储
12345678910111213141516// (1) 邻接矩阵：// 存储边 a->bg [a][b]// (2) 邻接表：// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点int h[N], e[N], ne[N], idx;// 添加一条边a->bvoid add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++;}// 初始化idx = 0;memset(h, -1, sizeof h);
树与图的遍历
(1) 深度优先遍历
12345678910int n, G[1000][1000];bool vis[1000] = {false};void dfs(int u) { vis[u] = true; // vis[u] 表示 ...
C++ STL简介
C++ STL 简介
前言
STL，英文全称 standard template library，中文可译为 标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入 / 输出、数学计算等功能。
vector
vector 容器是 STL 中最常用的容器之一，vector 实现的是一个动态数组，即可以进行元素的插入和删除。
vector 常被称为 向量容器，在尾部插入或删除元素，时间复杂度为 O(1)；而在容器头部或者中部插入或删除元素，时间复杂度为 O(n)。
12345vector<int> nums; # 空 vectornums.resize(20); # 指定大小vector<int> nums(20); # 创建时指定大小，默认初始值都为 0vector<int> nums(20,1); # 创建时指定大小，初始值为 1vector<int> nums {1, 2, 3, 4, 5};
12 ...
常用算法模板——数据结构
本文作者：yxc
来源: AcWing
原文地址：https://www.acwing.com/blog/content/404/
常用算法模板——数据结构
单链表
123456789101112131415161718// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点int head, e[N], ne[N], idx;// 初始化void init() { head = -1; idx = 0;}// 在链表头插入一个数avoid insert(int a) { e[idx] = a, ne[idx] = head, head = idx++;}// 将头结点删除，需要保证头结点存在void remove() { head = ne[head];}
双链表
12345678910111213141516171819202122// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点int e[N] ...
常用算法模板——常见算法
本文作者：yxc
来源: AcWing
原文地址：https://www.acwing.com/blog/content/277/
常用算法模板——常见算法
快速排序算法模板
1234567891011121314151617181920212223242526272829303132// 最常规的快速排序模板void QuickSort(int nums[], int l, int r) { if (l < r) { int pos = partition(nums, l, r); QuickSort(nums, l, pos - 1); QuickSort(nums, pos + 1, r); }}int partition(int nums[], int left, int right) { int pivot = nums[left]; // 第一个数作为基准值 int low = left, high = right; while (low &l ...
由数据范围反推算法复杂度以及算法内容
本文作者：yxc
来源: AcWing
原文地址：https://www.acwing.com/blog/content/32/
由数据范围反推算法复杂度以及算法内容
一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。
在这种情况下，C++ 代码中的操作次数控制在 107∼10810^7∼10^8107∼108 为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
n≤30→O(n3)n \leq 30 \to O(n^3)n≤30→O(n3)
指数级别，DFS + 剪枝，状态压缩 dp
n≤100→O(n3)n \leq 100 \to O(n^3)n≤100→O(n3)
Floyd，dp，高斯消元
n≤1000→O(n2),O(n2logn)n \leq 1000 \to O(n^2),O(n^2 \log n)n≤1000→O(n2),O(n2logn)
dp，二分，朴素版 Dijkstra，朴素版 Prim，Bellman-Ford
n≤10000→O(nn)n \leq 10000 \to O(n \sqrt n)n≤10000→O ...
二分查找学习笔记
二分查找学习笔记
前言
二分查找也称折半查找，它是一种效率较高的查找方法。二分查找，思路很简单，细节是魔鬼。
本文主要探究几个最常用的二分查找场景：寻找一个数、寻找左侧、右侧边界。到底要给 mid 加一还是减一，while 里到底用 <= 还是 <，并给出二分模板。
寻找一个数
寻找一个数的问题是最简单最熟悉的，下面的代码相信你也很熟悉：
123456789101112131415int binarySearch(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length - 1; // 注意 while (left <= right) { // 注意 int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if ( ...
Hexo 常用插件推荐
Hexo 常用插件推荐
Hexo 本身提供了一个框架，通过丰富的拓展插件，能够进一步优化使用体验，你可以在 Hexo 插件 中寻找适合你的拓展。
生成永久链接
hexo 文章链接默认的生成规则是：:year/:month/:day/:title，即按照年、月、日、标题的顺序
当文件名为中文时，会导致 url 链接中也出现中文
1https://emoryhuang.github.io/blog/2021/05/09/Hexo %E5%B8%B8%E7%94%A8%E6%8F%92%E4%BB%B6%E6%8E%A8%E8%8D%90
这样的链接非常不利于阅读，也不美观
hexo-abbrlink 插件通过算法为文章生成永久链接，相对来说更加简洁方便。
安装 hexo-abbrlink 插件
1npm install hexo-abbrlink --save
修改 config.yml 文件中的永久链接：
1234permalink: blog/:abbrlink.html # 也可以直接写 :abbrlink/abbrlink: alg: crc32 #算法： crc16(d ...
传统图像边缘检测方法
传统图像边缘检测方法
引言
图像轮廓边缘指的是图像中目标对象和背景之间的区分明显的交界线。对于数字图像来说，图像边缘是数字图像中灰度变化比较大的点，它是物体最基本的特征之一。基于图像边缘灰度剧烈变化的特征，传统的边缘检测方法往往根据灰度变化的情况进行边缘提取。
本文主要介绍传统边缘检测方法的基本思路以及实现方法，主要对 Sobel 边缘检测方法，Canny 边缘检测方法进行具体分析，讨论了其优缺点，最后指出了对传统边缘检测方法的一些改进措施。
传统边缘检测方法的基本思路
由于物体边缘处的灰度变化剧烈，因此传统的边缘检测方法大多利用这个特点，通过计算像素的梯度判断当前像素点是否为边缘像素点。首先通过滤波器进行平滑处理，以减小噪声对边缘检测产生的影响；其次计算梯度，寻找梯度变化最大的像素点，得到边缘像素点；最后进行阈值处理，通过设定合适的阈值确定真正的边缘，排除非边缘点。Sobel 算子与 Canny 算子边缘检测结果如下图所示：
Sobel 边缘检测算法
Sobel 算子是由美国计算机科学家 Irwin Sobel 和 Gary Feldman 于 1968 年首次提出的，他充分利用一 ...
使用 LaTeX 写数学公式
使用 LaTeX 写数学公式
LaTeX 是一种高质量的排版格式，可以生成复杂的表格与数学公式，是当前电子与数学出版行业的事实标准，相信很多人都应该或多或少听说过 LaTeX。LaTeX 简单来说就是一种文字处理软件 / 计算机标记语言，可以通过简单的语法写出优雅的数学公式。
LaTeX 公式手册
→\rightarrow→ LaTeX 公式手册
LaTeX 简单入门
行内公式与行间公式
LaTeX 有行内公式和行间公式两种形式，简单来说:
行内公式: 公式嵌入在行内
行间公式: 公式独占一行
1这是一个行内公式：$f(x) = x + 2$
效果如下所示：
这是一个行内公式：f(x)=x+2f(x) = x + 2f(x)=x+2
1234这是一个行间公式, 它需要独立成行$$f(x) = x + 2$$
效果如下所示：
这是一个行间公式, 它需要独立成行
f(x)=x+2f(x) = x + 2
f(x)=x+2
基本运算符
拉丁字母、阿拉伯数字和 +,-,*,/,= 运算符均可以直接输入获得
1$a + b - c * d / e = x + 1$
效果如下所示：
...
快速幂算法详解
快速幂算法详解
前言
首先考虑这么一个问题
给定三个正整数 a, b, m（a < 10910^9109，b < 10910^9109，1 < m < 10910^9109），求 aba^bab % m。
对于这个问题，只要写一个简单的循环就能够搞定
12345678// 普通求幂long long QuickPow(long long a, long long b, long long m) { long long ans = 1; for (int i = 0; i < b; i++) { ans = ans * a % m; } return ans;}
然而，当 a, b 到达一定值时，最终的结果会非常大，对于这个问题，O(b)的时间复杂度很难进行。
快速幂算法
快速幂，就是用效率更高（时间复杂度更低）的方法求幂，可以将时间复杂度优化至 O(logn)
递归快速幂
快速幂算法的关键在于对指数 b 的处理，我们很容易得到如下事实：
若 b 为奇数，则ab=a×ab−1a^ ...
最新文章
