首页
学习
活动
专区
工具
TVP
发布

mathor

专栏成员
447
文章
619575
阅读量
50
订阅数
Dancing Links算法
 Dancing Links算法主要用于解决精确覆盖问题,精确覆盖问题就的定义:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得每个集合中每一列恰好只包含一个1。例如下面的矩阵,我们将改矩阵命名为矩阵1
mathor
2018-09-19
2.2K1
LeetCode300. 最长上升子序列
 经典dp问题,用dp[i]表示前i+1个个数的最长上升子序列,也就是以ai为末尾的最长上升子序列长度,要注意的是dp初始化应该是1而不是0,因为对于每个数其本身就是一个长度为1的最长上升子序列
mathor
2018-07-24
7130
搜索(7)
 这道题迷宫中多了一些花样。一是迷宫中有陷阱,由X表示。除非处于无敌状态,否则不能经过陷阱。二是有些位置到达后会自动获得无敌状态,持续K步  我们可以看一下样例给的两个数据:
mathor
2018-07-24
5060
搜索(1)
 在讨论图的遍历问题之前,我们先来讨论一下图的存储问题,也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如1号顶点、2号顶点……  其次,我们有两种方法表示边集。一种叫做邻接矩阵表示法,另一种叫邻接表表示法  邻接矩阵是说我们用一个二维矩阵A来表示边集。A~ij~=0表示顶点i和顶点j之间不存在边,A~ij~=1表示顶点i和顶点j之间存在边。例如:
mathor
2018-07-24
4290
搜索(2)
 上一节我们以图的遍历为例讲了深度优先搜索算法和实现程序。上一节中的深度优先算法可以算是基本款,很多深度优先搜索的题目就是在这个基本款的程序上进行修改 DFS  加强版DFS首先增加或者说变化的一点是
mathor
2018-07-04
3780
搜索(3)
例2 八皇后问题  八皇后问题用一句话来描述,就是:找到所有在8*8的国际象棋棋盘上放置8枚皇后棋子并且满足任意两枚皇后不会互相攻击的方案  我们先来看一下国际象棋的棋盘:  棋盘是由8×
mathor
2018-07-04
5290
搜索(4)
 用DFS在2D地图上找连通分量的问题 例4 蓝桥杯——全球变暖  题目大意是有一张NxN像素的照片,图片中”#”代表陆地,”.”代表海洋。”上下左右”4连通连成一片的陆地组成一座岛屿。如下图题
mathor
2018-07-04
4100
KMP(4)
例6 题目链接:POJ2752  这道题目的大意是给定一个字符串S,让找出所有既是S前缀又是S后缀的字符串。然后从小到大输出它们的长度  比如S=ababcababababcabab,既是前缀
mathor
2018-07-04
7660
KMP(3)
例2 题目链接:HDOJ1711  这个题目的大意就是给你一个整数数组A=[A1, A2, … AN]和一个整数数组B=[B1, B2, … BM],让你找到一个位置K使得从A[K]开始的M个整
mathor
2018-07-04
4310
KMP(2)
求next数组(暴力版本) Next[0] = -1 Next[1] = 0 For i = 2...P.len Next[i] = 0; For j = i - 1...1 If P[1...j] == P[i - j + 1...i]//P[1...j]是P[1...i]的后缀 Next[i] = j Break  不过上面这个根据定义直接求的算法时间复杂度太高了。如果不优化会成为整个KMP的瓶颈,导致还不如直接用O(P.l
mathor
2018-07-03
3340
C语言有参数宏定义与无参数宏定义
前两天上课,被JAVA老师问懵了,老师问:“你们学C语言,有没有写过带参的宏玩一玩”,说实话,我根本没听过什么带参的宏,我只用过宏定义,所以我下来一定要找个时间把这“带参的宏搞懂”,于是就有了这篇文章。        C语言中宏定义分两种,无参的宏和有参的宏 1.无参数的宏        无参数宏定义的一般形式为: #define name value//name是你起的名字,就跟起函数名一样,value是你要给这个名字赋予什么值 //示例: #include <iostream> using name
mathor
2018-06-22
2.8K0
枚举+优化(6)——双指针优化2
例3.题目链接:hihoCoder1514  先写一个暴力枚举的伪代码: ans = MAX_INT For i = 1...M { For j = 1...N {
mathor
2018-06-19
4740
枚举+优化(5)——双指针优化1
 有时候我们要对一个数组进行i和j两个下标的双重循环枚举 for(int i = 0;i < n;i++) { for(int j = i + 1;j < n;j++) {
mathor
2018-06-19
4730
二分查找与二分答案(2)
溢出风险  我们首先回顾一下上一次二分算法的代码 #include<iostream> using namespace std; int n,x,a[1000000]; int binary_search(int a[],int n,int x) { int l = 0; int r = n - 1; int ans = -1; while(l <= r) { int m = (l + r) / 2; if(a[m] == x)
mathor
2018-06-19
6270
二分查找与二分答案(3)
例1  关于从长方形的巧克力中切出正方形的小巧克力,可以看下面的示意图:  上图是一块5x6的巧克力分别切出1x1、2x2和3x3的示意图。切成1x1一共可以切出30块,切成2x2可以
mathor
2018-06-19
7220
二分查找与二分答案(1)
 我们在写程序的时候,经常会遇到这样一类问题:在一个数组中查找一个数是不是存在。比如在下图的数组中,查找8是不是存在:  如果不要求效率,我们最一般的查找方法就是顺序查找,依次查看a[0],
mathor
2018-06-13
7203
枚举+优化(8)——前缀和2
例3.题目链接:hihoCoder1534  这道题要注意一下数据范围。首先N小于等于10万。其次Ai,也就是数组中每个数的值,是在负100万到正100万之间。假如这里Ai都是正整数的话,那么总
mathor
2018-06-12
5910
枚举+优化(4)——哈希表优化实例2
例3.四平方和 思路1:枚举abcd,判断a^2^+b^2^+c^2^+d^2^是否等于N  分析规模  a:0 ~ sqrt(500000 / 4)  b:0 ~ sqrt(500000 /
mathor
2018-06-08
6820
没有更多了
社区活动
【纪录片】中国数据库前世今生
穿越半个世纪,探寻中国数据库50年的发展历程
Python精品学习库
代码在线跑,知识轻松学
博客搬家 | 分享价值百万资源包
自行/邀约他人一键搬运博客,速成社区影响力并领取好礼
技术创作特训营·精选知识专栏
往期视频·千货材料·成员作品 最新动态
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档