- 博客(45)
- 收藏
- 关注
RSS订阅原创 从基础刷算法之字符串篇
1.反转字符串题意：就是反转char数组，要求只能使用O(1)的额外空间解决。思路：挺简单的，遍历一半的数组，交换对应位置就行。2.整数反转题意：输入一个有符号32位整数，要求反转数字部分，如果反转超出32位限制，就返回0.比如123反转之后就是321，-123反转之后是-321。思路：不断除10取余得到每一位，然后对每一位再乘10加下一次的余数，比如123，取余为3，第二次取余为2，那么直接(3*10 + 2) * 10 + 1就得到了321，不断的对上一次结果乘10加此次的余数即可完成反转，这
2021-06-27 17:29:31
173
原创 KMP算法之next数组的构建
前面一篇文章描述了KMP算法的思想和next的数组的由来，而这篇主要讲解next数组的构建。这边在放一下前面一篇文章的链接KMP算法之基础思想篇
2021-06-20 22:42:59
834
1
原创 从基础刷算法之数组篇
1.删除排序数组中的重复项题意：有序数组，删除重复的元素，要求不能申请额外的空间。思路：因为数组是有序的，定义一个变量index，用来记录非重复的长度，初始化为1，遍历数组，当发现i+1和i不相同时（这里判断i和i-1也是一样的），则证明数字开始不重复了，于是将i+1放到index的位置，index+1（后移一位）。这样遍历完成后index的位置就是数组的大小了。class Solution { public int removeDuplicates(int[] nums) {
2021-05-26 21:20:09
201
1
原创 Redis string类型底层的数据结构
对于Redis来说每个k-v都是由dictEntry存储的，对于dictEntry可以通过redis源码中的dict.h头文件查看。typedef struct dictEntry { void *key; //key union { void *val; //value uint64_t u64; int64_t s64; double d; } v;
2020-11-29 17:14:26
487
原创 50组关于sql的练习及思路解答
纯个人练习sql的过程。此文章延用了可到处搜到的50组sql，对于每句sql都会尽可能的做出多的解决方案并书写思路，希望可以帮助到更多人。有任何不理解的地方欢迎留言，有更好的解法或者觉得解法有问题的也欢迎留言讨论。下面正题开始首先是建表语句，同样的涉及到4张表student（学生信息表）， sc（学生成绩表）， course（课程信息表），teacher（教师信息表）student表CREATE TABLE student(Sid VARCHAR(10), Sname VARCHAR(10),
2020-08-16 18:28:54
926
原创 cocos2dx学习（二） 创建一个helloWorld
1.如何创建cocos2dx的工程呢，据我这边目前了解到的，只有通过cocos命令来创建，对于cocos命令，常用的有以下参数：-h：显示 cocosnew 命令的帮助信息，该信息包含了 cocosnew 命令中每个命令行参数的含义（英文描述）。-p：包名（PACKAGE_NAME）。主要用于 Android 工程。如果不指定该命令行参数，默认值是 org.cocos2dx.hellocpp...
2020-03-19 22:27:57
395
原创 cocos2dx学习（一） 开发环境搭建
1.安装vs，直接去官网下载即可 我这边下载的是vs2019，一般都是下载Community版本，emmmm因为不要钱下载地址：https://visualstudio.microsoft.com/zh-hans/vs/只是cocos2dx开发的话，只用选择这两个就可以了，因为目前学习到的cocos2dx项目只能用python命令创建，且需要执行setup.py脚本，所以要安装python...
2020-03-18 20:21:25
397
原创 cocos2dx 关于渲染的学习
exe运行起来的时候，在左下角会有三个参数，glcall指的是当前场景的渲染批次（即渲染次数），这个次数越多，界面会越卡。据前辈说：一般超过130，界面会变的开始卡顿。当时写界面的时候，这个值达到了250，界面刷新的时候会明显的顿一下，所以学习了下关于cocos2dx渲染的机制，从而降到了120，下面讲一下关于对渲染机制的理解。cocos2dx 的分批次渲染机制，可以理解为：准备-渲染-...
2019-12-14 22:30:08
299
原创 PAT 1013
水。。。。。红果果的并查集。。。。题意就是给了N个城市，M个路，就是求，去掉第Ki个城市，需要添加多少条路才能把所有的城市都连起来。。。脑残数组开小了一次。弄出来一个段错误，傻乎乎的去百度了段错误半天。。。。。。#include int fa[1005],a[1005*1005],b[1005*1005];int n,m,k;int Find(int x){ if(x!=
2016-02-06 11:22:23
404
原创 PAT 1031
水。模拟就行了#include #include int main(){ int n1,n2,n3,len; int i,j; char s[88]; gets(s); len=strlen(s); n1=(len+2)/3; n3=n1; n2=len-n3-n1; for(i=0;i<n1-1;i++) { printf("%c",s[i]); for(j=
2016-02-06 10:18:47
353
原创 PAT 1002
开始看了题目猜的数据好像蛮简单的。结果………… 又是一道坑。题目意思很简单的，就是模拟多项式相加，指数相同系数相加，就这么简单，但是有2个地方很坑。题目要求不需要输出系数为0的项，计算有多少个项的时候也不能算上系数为0的项。当指数相同，系数就应该相加，判断应该放在系数相加之后，如果为0则跳过，不为0存入并且计数+1。=。= #include struct Point{ double
2016-02-06 10:01:31
367
原创 PAT 1001
题目连接：http://www.patest.cn/contests/pat-a-practise/1001这题好阴啊。被搞了2次。一些情况输出要03d的。比如-1000000 0下面又是贴代码了QAQ#include int main() { int a,b; int sum; scanf("%d %d",&a,&b); sum = a+b; if(s
2016-02-05 10:25:44
286
原创 hdu 5523 （这是一道水题。。。。。）
#include int abs(int x){ if (x < 0)return -x; return x;}int main(){ int n, s, t; while (~scanf("%d %d %d", &n, &s, &t)) { if (n == 1)puts("0"); else
2015-11-01 14:27:53
391
原创 hdu 3065
#include #include #include #include #pragma warning (disable : 4996)using namespace std;const int Max = 50005;int Next[Max][128], Fail[Max], End[Max];int L, root;char str[1010][100];int Ne
2015-08-18 16:24:50
320
原创 hdu 2896
AC 自动机模板题，输出路径。End数组记录路径。#include #include #include #include #pragma warning (disable :4996)using namespace std;const int Max = 210 * 505;int Next[Max][128], Fail[Max], End[Max];int root, L
2015-08-16 20:02:20
356
原创 HDU 2222
第一道AC 自动机的题目。。代码参考了网上大牛才写的。#include #include #include #include #pragma warning (disable :4996)using namespace std;const int Max = 500010;int Next[Max][26], Fail[Max], End[Max];int root, L;
2015-08-14 16:15:49
330
原创 cf 10D lcis 最长上升子序列+输出路径
用个数组记录下路径然后dfs 输出就可以了#include #include #include #pragma warning (disable : 4996)using namespace std;const int Max = 505;int dp[Max][Max], pre[Max][Max];int a[Max], b[Max];int m, n;void df
2015-08-12 19:48:48
415
原创 light oj 1110 LCS 记录路径
#include #include #include #pragma warning (disable : 4996)using namespace std;const int Max = 105;int dp[Max][Max];char s[Max][Max][Max];char str1[Max], str2[Max];int main(){ int T, k, i
2015-08-12 15:34:14
440
原创 poj 1080 LCS 应用
题意：给定两个DNA序列，然后按照给出的表格进行匹配，求匹配的最大值，利用lcs 原理，不过加了权值，就不能再像之前那样进行匹配了，但是原理是一样的。因为有‘-’的存在，所以这边要先对边界进行处理一下。因为带权值，所以求得的不一定会是最长公共子序列，所以就不用判断str1[i]==str2[j]这种条件了。转移方程：dp[i][j]表示的是str1从0~i-1和str2从0~j-1 匹
2015-08-12 14:47:06
289
原创 light oj 1021 状态压缩dp
给一个B进制的数，一个10进制的数K，B进制数有x位，对着x位进行全排列的话，有x！种可能，问这x！的可能中，有多少种可以整除K，各个位置上的数字都不同。代码也是看过题解之后才会写的 QAQ。。。。。。。。状态压缩dp，每次选一个没有用过的数，然后选一个没有用过的位置放上去，位置不一样，加上的值也不一样，然后直接记录对K取余，余数有多少种。dp[i][j]表示数位为i（i为1表示数字
2015-08-11 19:40:40
492
原创 poj 1182 深入并查集
#include #include #include #pragma warning (disable : 4996)using namespace std;const int Max = 50005;int Father[Max], Rank[Max], n;void Init(){ for (int i = 0; i <= n; i++) Father[i] = i;
2015-08-11 15:04:28
295
原创 poj 1631 LIS nlogn算法
题意：给出n个点，分别和1~n相连构成相交线段，现在要去几条线段，要求剩下的线段不想交，且不相交的线段数量最多。因为p#include #include #include #pragma warning(disable :4996)using namespace std;const int Max = 40005;int c[Max];int Binary(int l,
2015-08-09 14:48:51
380
原创 light oj 1017 Brush (III)
题意：给N个点，然后刷子的宽度w，刷子可以平行于x轴无限刷，给出可以刷的次数，求刷子可以覆盖多少个点。因为可以平行于x轴无限刷，所以不需要考虑x轴上的点， 直接对Y轴进行排序，预处理一个数组mv，mv[i]表示如果刷子的底部刷到了i，那么会向上影响mv[i]个点。#include #include #include #pragma warning (disable :4996)us
2015-08-09 12:31:34
398
原创 poj 1458 LCS
#include #include #include #pragma warning (disable :4996)using namespace std;const int Max = 1000;int dp[Max][Max];char str1[Max], str2[Max];int LCS(int lenstr1, int lenstr2){ memset(dp,
2015-08-07 16:31:13
286
原创 light oj 1013 LCS 应用
题意：给定两个字符串A,B，要求求一个字符串S，使得A,B是S 的子串，求S 的最小长度，以及在此长度下有多少种构成S 的方案。LCS的变形，S的最小长度肯定是A+B的长度-A和B的最长公共组序列的长度。之后的方案用DP思想去写就可以了。QAQ 我也是看了题解才会写的。先用lcs 去求A和B 的最长公共子序列。然后dp[i][j][k]表示构造了i长度的字符串，在利用了A串的前j个字符
2015-08-07 14:40:10
455
原创 light oj 1025 区间dp
题意：给一个字符串，问有多少种方法通过移动去除中的字符使之变成回文串。思路：区间dp，dp[i][j]表示区间i~j的方案总数。对于串str，两个for进行控制，第一个for从后往前，第二个for从i+1开始，到串的最后，如果str[i] == str[j]，那么dp[i][j] += dp[i+1][j-1] + 1，因为如果去掉i+1~j-1之后，因为str[i] == str[j]
2015-08-06 16:50:34
371
原创 Hdu 1599 Floyd
#include #include #include #pragma warning (disable :4996)using namespace std;const int Max = 105;const int Inf = 1 << 29;int map[Max][Max], dis[Max][Max], n, m, ans;void Floyd(){ ans = In
2015-08-05 13:32:06
312
原创 poj 1125 Floyd
题意：从一个人开始散步谣言，问传到所有人所花费的最小时间。输入n 然后下面n行，每一行第一个数m，表示第i个人和m个人有关系，之后又m对数，对于每对数，第一个数j表示i和j有关系，第二个数表示谣言从i传到j所花费的时间。#include #include #include #pragma warning (disable :4996)using namespace std;co
2015-08-04 16:35:02
260
原创 light 1011 状态压缩dp
题意：给一个N*N的二维数组，从中选出N个数 要求不能同行同列， 求这N个数最大数的和 状态压缩。每个i+1由上一个i推出来，这个直接一个for 搞一下就可以，剩下的就是枚举每个列。开一个dp[1（1异或表示去掉一个1，比如1000&1010 = 1 然后1010^1000 = 0010，这样就去掉了一个1 ，就表示我要选择这列m-1 就表示换到下一层。#incl
2015-08-04 12:11:21
332
原创 HDU 5339
搜索题目，题意：给定n和a，然后一个序列b1……bn，问能不能从序列中取出任意个数组成c1……cn，然后满足a mod c1 mod c2……mod cn = 0；#include #include #include using namespace std;#pragma warning (disable :4996)const int N = 22;int a[N],
2015-08-04 11:59:53
335
原创 ural 1019
题意：给定一个数N 下面有N 行操作，每行有两个数a，b和一个字符c，把区间a-b染成c 的颜色，求最后全部染完色后最长白色区间的左右端点坐标。线段树成段更新+染色，由于数据量很大数据要进行离散。离散后映射到数组上，按条件查询最长的白色区间就可以了。#include #include #include using namespace std;#define Max 10010#pra
2015-08-01 16:01:03
388
原创 ural 1017
题意：有N 块砖头，问可以组成多少种楼梯，条件是楼梯至少为两层，每层的数量也不能相等，题解和划分数很相似。dp 思想的一道题，转移方程很难想，想了解如何想出的状态转移方程的，请移步这个牛人的博客：http://www.cnblogs.com/skyivben/archive/2009/03/02/1401728.htmldp[k][i] 表示数k 的最小被加数不小于k 的划分的个数。#in
2015-08-01 13:45:49
590
原创 CF 124B
#include #pragma warning(disable:4996)#include #include using namespace std;int main(){ int n, k; char s[9][9]; int a[9]; int Min; vectorData; while (~scanf("%d %d", &n, &k)) { for (i
2015-07-31 18:35:59
301
原创 HDU 4267 线段树区间内部某个值更新
题意：输入N 下面有N个数， Q个操作，对于每次操作 有两种情况。情况1.输入1 a b k c,表示更新操作，将a-b区间内的符合a 情况2：输入2 a 表示查询操作，输出a 上的值。思路：对于这种不是对整个区间都进行更新的操作，似乎lazy算法就没什么用了，这题一开始看的感觉是单点更新，但是看下数据量单点更新根本不可行。那我们可以想一下他给的条件，（i-a）%k==0，
2015-05-10 14:35:27
381
原创 HDU 5023
题意：和POJ 2777类似，建n的线段树，然后m个操作，P a b c 表示将ab区间的颜色换成c，Q a b表示查询ab的颜色，输出区间的颜色，按照从小到大的顺序，POJ 2777是输出区间颜色的个数。思路：用位运算进行加速，lazy【id】表示的是我当前的第id位变成1之后转化成10进制的数。 比如大小为3的树，我给id=3的位置涂颜色3，那么我就将二进制从后往前数第3位变成1，就相当于
2014-12-22 21:52:27
315
原创 poj 3264 线段树水题
#include #include using namespace std;#define maxn 55555int sum1[maxnint maxx,minn;void pushup(int id){sum1[id]=max(sum1[idsum2[id]=min(sum2[id}void build(int l,i
2014-12-21 16:12:46
357
原创 POJ 3667 线段树区间合并
题意：一个旅馆有n个房间，m条操作，如果输入1 b 表示住进来b个人 然后输出这b个人住的房间编号最前面的那个，如果输入 2 b c, 就是说要将b到b+c-1的房间全部全部清空。思路：此题更新操作简单，但是查询的时候不好做，这题要添加两个数组，lsum表示一个区间从最左端开始可用的且连续的最大长度，例如区间[1,5]，覆盖情况为[0,0,0,1,1]，lsum=3，从最左端有3格可以利用
2014-12-20 14:24:14
635
原创 HDU 2795 线段树
题意：给你一个长方形的木板，往上面贴广告，广告的要求是如果第一行可以贴下那么就贴在第一行，而且尽可能的往左贴，最后输出这个广告贴在哪一行。给你高度h，宽度w的长方形木板和n个操作，下面有n行操作，每一行有一个数表示广告的宽度，所有广告的高度都是1.如果木板可以容纳这个广告就输出贴在哪行，如果不能就输出-1。思路：因为之前别人介绍这道题的时候说这是道坑题，所以先百度看了一下坑的所在，这题的数据看
2014-12-09 19:37:00
429
原创 POJ 2528 线段树成段更新，数据离散化
题意：就是张贴海报，问最后可以看到有多少张海报。因为数据太大，直接建树会爆掉，所以要进行数据离散化。数据的离散化意思是 比如说我有两张海报，一张从1-1000，另一张从30000-1000000，那我完全可以将第一张看成1-2，第二张看成3-4啊，这样数据量不就减少很多了么。我们只用对所有的点一次快排然后不同的点不断加1就行了，但是单单是这样还是不行，比如1-10，1-3，6-10，这样按照上
2014-12-02 11:56:07
453
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人