乐趣区

关于算法:数据结构与算法入门指南

对于

博客次要记录对于算法方面的常识(可能偏比赛方面),代码均应用 C ++ 编写,不蕴含根底的语法介绍。

听从宁繁勿简、深入浅出的准则,每篇文章都会配上例题,尽量给出代码,不便学习。

初学者入门数据结构与算法时,面对那么多的平台和题库,可能无从下手,找不到一个零碎学习的办法,兴许这系列的文章能帮你零碎的学到常识,无效的进步思维与代码程度????。

举荐的 OJ(在线评测零碎)

  • 洛谷 比拟并重比赛,有官网月赛和用户举办的较量,题目较多。
  • LeetCode 找工作用,难度偏低,有周赛。
  • 牛客比赛 工作 & 比赛,举办的较量较多。

目录(陆续更新)

根底算法

  • 排序

  • 二分

  • 高精度

  • 前缀和与差分

  • 双指针

  • 位运算

  • 离散化

数据结构

  • 链表

  • 队列

  • 字符串

  • 并查集

  • 哈希表

  • 线段树

  • 均衡树

搜寻

  • 广度优先搜寻(BFS)

    • Flood Fill
    • 最短路
    • 多源 BFS
    • 双向广搜
    • A*
  • 深度优先搜寻(DFS)

    • 全排列
    • 连通性模型
    • 剪枝与优化
    • 迭代加深
    • IDA*

图论

  • 最短路

    • 拓扑排序
    • Dijkstra
    • bellman-ford
    • spfa
    • Floyd
    • 分层图
  • 最小生成树

    • Prim
    • Kruskal
  • 二分图

动静布局

  • 背包

  • 最长回升子序列

  • 状态压缩 DP

  • 区间 DP

  • 树形 DP

  • 数位 DP

  • 枯燥队列优化 DP

  • 斜率 DP

数学

  • 筛质数

  • 合成质因数

  • 疾速幂

  • 欧拉函数

  • 组合计数

  • 高斯消元

  • 容斥原理

  • 概率与数学冀望

  • 博弈论

万能头 与 Visual Studio

如果你应用 Visual Studio,并且没有导入万能头,能够持续往下看

万能头文件涵盖了做题中须要的大部分头文件(在做题中我就没遇到须要额定导入其余头文件的题????)。其蕴含的头文件较多,所以编译的工夫也会比拟多,但不会影响运行工夫。

万能头文件应用: #include <bits/stdc++.h>

但在 Visual Studio 中无奈间接援用万能头,须要本人手动增加。

stdc++.h 源码:


 // C++ includes used for precompiling -*- C++ -*-
 ​
 // Copyright (C) 2003-2014 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
 // terms of the GNU General Public License as published by the
 // Free Software Foundation; either version 3, or (at your option)
 // any later version.
 ​
 // This library is distributed in the hope that it will be useful,
 // but WITHOUT ANY WARRANTY; without even the implied warranty of
 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 // GNU General Public License for more details.
 ​
 // Under Section 7 of GPL version 3, you are granted additional
 // permissions described in the GCC Runtime Library Exception, version
 // 3.1, as published by the Free Software Foundation.
 ​
 // You should have received a copy of the GNU General Public License and
 // a copy of the GCC Runtime Library Exception along with this program;
 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
 // <http://www.gnu.org/licenses/>.
 ​
 /** @file stdc++.h
  *  This is an implementation file for a precompiled header.
  */
 ​
 // 17.4.1.2 Headers
 ​
 #define _CRT_SECURE_NO_WARNINGS
 ​
 // C
 #ifndef _GLIBCXX_NO_ASSERT
 #include <cassert>
 #endif
 #include <cctype>
 #include <cerrno>
 #include <cfloat>
 #include <ciso646>
 #include <climits>
 #include <clocale>
 #include <cmath>
 #include <csetjmp>
 #include <csignal>
 #include <cstdarg>
 #include <cstddef>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <ctime>
 ​
 #if __cplusplus >= 201103L
 #include <ccomplex>
 #include <cfenv>
 #include <cinttypes>
 #include <cstdalign>
 #include <cstdbool>
 #include <cstdint>
 #include <ctgmath>
 #include <cwchar>
 #include <cwctype>
 #endif
 ​
 // C++
 #include <algorithm>
 #include <bitset>
 #include <complex>
 #include <deque>
 #include <exception>
 #include <fstream>
 #include <functional>
 #include <iomanip>
 #include <ios>
 #include <iosfwd>
 #include <iostream>
 #include <istream>
 #include <iterator>
 #include <limits>
 #include <list>
 #include <locale>
 #include <map>
 #include <memory>
 #include <new>
 #include <numeric>
 #include <ostream>
 #include <queue>
 #include <set>
 #include <sstream>
 #include <stack>
 #include <stdexcept>
 #include <streambuf>
 #include <string>
 #include <typeinfo>
 #include <utility>
 #include <valarray>
 #include <vector>
 ​
 #if __cplusplus >= 201103L
 #include <array>
 #include <atomic>
 #include <chrono>
 #include <condition_variable>
 #include <forward_list>
 #include <future>
 #include <initializer_list>
 #include <mutex>
 #include <random>
 #include <ratio>
 #include <regex>
 #include <scoped_allocator>
 #include <system_error>
 #include <thread>
 #include <tuple>
 #include <typeindex>
 #include <type_traits>
 #include <unordered_map>
 #include <unordered_set>
 #endif

在 Visual Studio 中应用 scanf 之类的 C 语言内置函数会报错,因为 Visual Studio 认为这些函数不平安,应应用 scanf_s 之类的函数,但在代码中退出 #define _CRT_SECURE_NO_WARNINGS即可屏蔽这类的平安提醒,毕竟咱们是写算法的嘛。我曾经把屏蔽平安提醒的语句增加至下面的代码中了,间接复制应用即可。

疾速增加至 Visual Studio 的办法:

  1. 先轻易援用一个零碎头文件,对其右键抉择转到文档。

  2. 对新关上的文件(留神在右上角)右键,抉择关上所在文件夹。

  3. 新建一个 bits 文件夹,把 stdc++.h 文件拖入
  4. 间接在 Visual Studio 中应用 #include <bits/stdc++.h> 即可
退出移动版