程序与技术分享：Acwing算法笔记
1.基础算法 —— 代码模板链接 常用代码模板1——基础算法排序二分高精度前缀和与差分双指//代码效果参考：http://www.jhylw.com.cn/442920807.html针算法位运算离散化区间合并2.数据结构 —— 代码模板链接 常用代码模板2——数据结构链表与邻接表：树与图的存储栈与队列：单调队列、单调栈kmpTrie并查集堆Hash表C...
【AcWing算法基础课】第五章 动态规划（未完待续）(3)
四、记忆化搜索题目链接：901. 滑雪4.1题目描述给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。下面给出一个矩阵作为例子：1 2 3 4 5 1...
【AcWing算法基础课】第五章 动态规划（未完待续）（2）
二、线性DP线性DP：递推方式为线性的递推式。1、数字三角形题目链接： 898. 数字三角形1.1题目描述给定一个如下图所示的数字三角形，从 顶部 出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点， 一直走到底层 ，要求找出一条路径，使 路径上的数字的和最大。7 3 8 8 1 0 2 7 4 4 4 5 2 6 ...
【AcWing算法基础课】第五章 动态规划（未完待续）（1）
课前温习初识DPdp问题的优化：在基本形式dp上作等价变形。dp问题的解题方法：1）状态表示集合属性：最大值/最小值/数量。2）状态计算集合划分（不重不漏）一、 背包问题1、0-1背包问题题目链接： 2. 01背包问题 - AcWing题库1.1题目描述有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的....
【AcWing算法基础课】第四章 数学知识（未完待续）（3）
五、求组合数核心模板根据下面公式来预处理出等式右边的组合数的值，那么等式左边就可以用等式右边已经算过的值来进行计算（有点像dp）。//c[a][b]表示从a个苹果中选b个的方案数 for(int i=0;i<N;i++){ for(int j=0;j<=i;j++){ if(!j) c[i][j]=1; else c[i][j]=(c[i-1]...
【AcWing算法基础课】第四章 数学知识（未完待续）（2）
二、筛素数1.朴素筛法求素数从2到n枚举每个数，删掉其所有的倍数，枚举完之后，没有被删掉的数为质数。核心模板int primes[N],cnt; //primes[]存储所有素数 bool st[N]; //st[x]存储x是否被筛掉 void get_primes(int n){ st[0]=st[1]=true; //0和1均不是质数 for(i...
【AcWing算法基础课】第四章 数学知识（未完待续）（1）
课前温习番外：秦九韶算法利用秦九韶算法来实现其他进制转十进制的结果求解下图内容来源：百度百科，侵删。核心模板int nToTen(string s,int n){ int ans=0; for(int i=0;i<s.size();i++){ ans=ans*n+s[i]-'0'; } return ans; }主要代码#include...
【AcWing算法基础课】第三章 搜索与图论（3）
十一、Flood Fill算法既可以宽搜实现，也可以深搜实现，宽搜具有最短性，深搜方便写，但容易爆栈。宽搜思路：每次将周围的点放入队列，然后一圈一圈地往外扩展。深搜思路：每次按四个方向分别进行扩展，直到一个方向无法进行扩展时，回溯。题目链接：1113. 红与黑11.1题目描述有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑....
【AcWing算法基础课】第三章 搜索与图论（2）
六、Dijkstra算法源点即起点，汇点即终点。n表示点数，m表示边数稠密图：m和n2一个级别稀疏图：m和n一个级别核心模板稠密图用邻接矩阵存储，稀疏图用邻接表存储。朴素dijkstra算法时间复杂度是O(n2+m)，n表示点数，m表示边数int g[N][N]; //存储每条边 int dist[N][N]; //存储1号点到每个点的最短距离 bool st[N]; //存储每个点的最短路是.....
【AcWing算法基础课】第三章 搜索与图论（1）
前言本专栏文章为本人AcWing算法基础课的学习笔记，课程地址在这。如有侵权，立即删除。课前温习一、深度优先搜索（DFS）特点：尽可能先向纵深方向搜索。使用stack实现。所需空间O(h)（h为深度）。不具有“最短性”。1、排列数字题目链接：842. 排列数字1.1题目描述给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照 字典序 将所有的排列方法输出。输入格式共一....
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
智能引擎技术
AI Online Serving，阿里巴巴集团搜推广算法与工程技术的大本营，大数据深度学习时代的创新主场。
+关注