- 博客(620)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 Leetcoder 887. Super Egg Drop（动态规划）
题意：给K个鸡蛋，有N层楼，问至少要多少次扔鸡蛋才能保证找出摔破鸡蛋的临界楼层，鸡蛋碎了就没了。思路：首先题意要搞清楚，是要保证能找出临界点，也就是你采取的方案无论临界点在哪一层，都必须在扔这么多次之内找出来。方法一：dp[i][j]表示剩余i个鸡蛋处理j层楼至少要扔几次，那么怎么推理dp[i][j]呢？枚举第一个鸡蛋扔的楼层（1～j）,假设扔到了第k层，碎了，转移到dp[i-1][k-1...
2019-08-26 14:24:43
368
原创 记一次Linux C++ Segmentation fault处理
段错误有可能是重复free指针或者操作野指针，今天遇到了一个段错误bug，是由于某函数声明了返回值（应该返回一个shared_ptr），但是函数实现忘记return导致的，虽然使用这个函数时没有用到它的返回值，但是依然报错，gdb调试指向一个new语句，牛头不对马嘴，注释掉new语句后traceback指向下一个使用new的地方，所以当项目代码比较多时，调试不一定能找出来问题！段错误如果找不到原因...
2019-08-06 20:42:39
1057
原创 IO多路复用EPOLL的ET模式下EPOLLIN事件触发时机
网上说的太宏观，自己测试一下各种情况，FD为nonblock。0.客户端发送新数据过来，单线程阻塞在epoll_wait，epoll_wait返回可读事件。1.单线程阻塞在epoll_wait，客户端发送新数据过来，epoll_wait返回可读事件。2.单线程阻塞在epoll_wait，客户端发送新数据过来，epoll_wait返回可读事件开始读数据，同时客户端不再发送数据过来，并且缓...
2019-08-03 13:35:17
482
原创 leetcoder：41. 缺失的第一个正数 & 76. 最小覆盖子串
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。思路：首先答案肯定在1~n，那么我们建个长度为N的数组，扫一遍元素组把位于1~n的数放到桶里面，最后扫一下哪个最小的空桶就行，怎么分到困难题的，代码略。下一题给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。示例...
2019-07-20 23:40:40
191
原创 leetcoder：124. 二叉树中的最大路径和 & 149. 直线上最多的点数
给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。思路：递归，维护以每个点为开始往下延伸的路径的最大值回传给父节点，同时更新答案最大值。/** * Definition for a binary tree node. * struct TreeNode { * int val...
2019-07-20 09:47:01
222
原创 利用yaml-cpp库对数据结构序列化
有时候我们要将一个int、float、bool转成字符串，这个用boost能简单地实现，但是一些复杂的数据结构比如STL的vector、map、list、set甚至是组合的vector<vector<int> >、map<string, vector<list<double> > >数据结构，可以通过yaml库来实现序列化成字符串，下面简...
2019-07-12 17:20:28
925
原创 C++模板类实现std::list
list是以链表为底层的STL容器，下面用模板类实现它的基本功能，部分思路参考C++泛型STL原理和应用。list实现的函数：push_front()push_back()pop_front()pop_back()begin()end()size()迭代器重载了：===!=++--*# include <iostrea...
2019-05-16 11:40:31
948
原创 signal()信号测试
测试代码1：# include <stdio.h># include <error.h># include <sys/types.h># include <string.h># include <signal.h>typedef void Sigfunc(int);void sig_usr(int signo){ if...
2019-04-25 21:38:57
640
原创 fork()函数测试
测试代码1：# include <stdio.h># include <error.h># include <sys/types.h># include <string.h>int main(int argc, char *argv[]){ char s[] = "hello\n"; write(1, s, strlen(s));...
2019-04-24 14:40:52
276
原创 JSON字符串解析器（unicode转utf-8）
图片和代码思路均参考：https://zhuanlan.zhihu.com/p/22731540json的字符串格式为"..."，下面写个解析器来解析json的字符串也就是主要处理包含转义字符\这种情况，其中\u表示unicode字符，我们需要转成utf-8的编码格式，为什么呢？看下图将会如果unicode用上图第一列的默认编码（utf-16），将会使每一个字符至少占用两个字节，而使用...
2019-03-23 12:48:06
9946
原创 CF1132C：Painting the Fence（暴力）
C. Painting the Fencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou have a long fence which consists ofnnsections. Unfort...
2019-03-06 22:01:42
694
原创 C语言多线程互斥锁
互斥锁是为了防止多个线程同时操作临界资源，下面看看用法：# include <stdio.h># include <pthread.h>pthread_mutex_t mute;int value = 0;void *fun(void *arg){ //上锁，函数是阻塞的 pthread_mutex_lock(&mute); ...
2019-03-04 22:56:09
21037
1
原创 EPOLL高并发服务器
IO复用模型有select、poll、epoll，关于它们的区别：1.select能处理的fd数量很少，我的电脑是1024个(sizeof(fd_set)*8)，而epoll的fd数量没有限制，只与内存大小有关。2.select当fd就绪时，需要将所有fd拷贝到内核态再将活跃的fd拷贝回用户态，还有遍历fd数组判断哪个是活跃的。而epoll不需要频繁的拷贝，当fd就绪时调用回调函数插入到f...
2019-03-02 21:22:25
825
原创 CF1117C. Magic Ship（二分）
C. Magic Shiptime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou a captain of a ship. Initially you are standing in a point (x1,...
2019-02-21 11:19:35
302
原创 剑指offer：数组中的逆序对（分治）
[编程题]数组中的逆序对热度指数：243682 时间限制：2秒 空间限制：32768K 算法知识视频讲解 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007输入描述: 题目保证输入的数组中没有的相同的数字数据范围：...
2019-02-18 20:55:01
219
原创 剑指offer：整数中1出现的次数（从1到n整数中1出现的次数）（数位dp）
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。思路：正解的数学方法不想了，万金油的做法就是记忆化搜索，dp[pos][sum]表...
2019-02-18 16:31:41
514
原创 剑指offer：最小的K个数（大根堆）
题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 思路：维护一个大根堆，pop掉大的数，剩下的就是K小，O(nlogn)。手写堆或者STLclass Solution {public: int *a, tot=0; int top(){ return a[1];...
2019-02-12 21:15:59
269
原创 剑指offer：数组中出现次数超过一半的数字
题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。思路：这题显然要O(n)，使用map或者hash复杂度都不理想。方法一：随机算法，假设存在一个数超过一半，随机找出这个数，错误的概率最坏情况下为1/2，那么进行x次随机取...
2019-02-12 20:49:25
146
原创 剑指offer：二叉搜索树与双向链表
题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路：模拟中序遍历的过程就OK，或者利用分治的思想，递归分别处理左右子树，再合并左右子树成一条链。/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;...
2019-02-09 19:20:31
255
原创 leetcode239：Sliding Window Maximum（单调队列）
为了避免毕业后失业，还是要好好刷题，上次面试的时候问leetcode和剑指offer的比较多，去这里练习一下。239. Sliding Window MaximumHard127477FavoriteShareGiven an array nums, there is a sliding window of size k which is moving from the very ...
2019-01-26 17:39:04
220
原创 TSP旅行商问题各种算法实现
C++版本遗传算法、模拟退火、蚁群算法、Hopfield神经网络、禁忌搜索，部分思路参考网络或者Paper。//遗传算法解决TSP问题,35s# include <bits/stdc++.h>using namespace std;typedef long long LL;const int times = 3000;//遗传代数const int chrom =...
2019-01-03 19:44:31
21703
2
原创 nowcoder：[编程题] 字典序（贪心）
时间限制：1秒空间限制：32768K给定整数n和m, 将1到n的这n个整数按字典序排列之后, 求其中的第m个数。对于n=11, m=4, 按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2. 对于n=200, m=25, 按字典序排列依次为1 10 100 101 102 103 104 105 106 107 108 109 11...
2018-11-21 00:55:32
343
原创 nowcoder：[编程题] 异或（01字典树）
[编程题] 异或时间限制：1秒空间限制：32768K给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。输入描述:第一行包含两个整数n,m. 第二行给出n个整数A1，A2，...，An。数据范围对于30%的数据，1 <= n, m <= 1000对于100%的数据...
2018-11-20 16:57:41
282
原创 nowcoder：[编程题] 头条校招（贪心）
时间限制：1秒空间限制：32768K头条的2017校招开始了！为了这次校招，我们组织了一个规模宏大的出题团队，每个出题人都出了一些有趣的题目，而我们现在想把这些题目组合成若干场考试出来，在选题之前，我们对题目进行了盲审，并定出了每道题的难度系统。一场考试包含3道开放性题目，假设他们的难度从小到大分别为a,b,c，我们希望这3道题能满足下列条件：a<=b<=cb-a<=...
2018-11-20 16:38:04
232
原创 HDU3966：Aragorn's Story（树链剖分）
Aragorn's StoryTime Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 18159 Accepted Submission(s): 4792 Problem DescriptionOur protagonist...
2018-10-31 15:37:01
171
原创 ZOJ4011：Happy Sequence（递推 & 质因子）
题目链接题意：给N，M要求构造一个长为M的数组A，每个数不大于N，且A[i]是A[i+1]的因子。思路：枚举第M个数的值，显然每个质因子可以独立讨论，只需要用每个质因子的数量计算，最后将每个质因子的答案乘起来就行，先预处理dp[i][j]表示长度为i，第i个数为j的非降序列长度，计算复杂度O(T*N*sqrt(N))，加点优化实际跑得更快。# include <bits/std...
2018-10-18 23:42:52
241
原创 AGC：Removing Blocks（计数）
Problem StatementThere are N blocks arranged in a row, numbered 1 to N from left to right. Each block has a weight, and the weight of Block i is Ai. Snuke will perform the following operation on the...
2018-10-17 20:38:47
409
原创 洛谷：[ZJOI2014]力（FFT）
点我查看题目题目描述给出n个数qi，给出Fj的定义如下：F_j = \sum_{i<j}\frac{q_i q_j}{(i-j)^2 }-\sum_{i>j}\frac{q_i q_j}{(i-j)^2 }Fj=∑i<j(i−j)2qiqj−∑i>j(i−j)2qiqj令Ei=Fi/qi，求Ei.输入输出格式输入格式： 第一...
2018-10-11 00:00:55
255
原创 ZOJ4046：Good Permutation（逆序数）
题目链接题意：给N（1e5）个数的一个全排列，每次可以交换相邻的数，问最小交换次数达到数组满足a[i+1] = (a[i]%n)+1。思路：假如换成1，2，3...n的排列，显然答案就是逆序数，那么加如1最终在位置2，留意到逆序数的变化与数字5的位置有关，因为数字5要最终去位置1了，所以枚举1的最终位置，过程O(1)维护逆序数。# include <bits/stdc++.h&...
2018-10-10 17:33:25
402
原创 SPOJ：Counting Divisors (general)（min_25筛）
Let \sigma_0(n)σ0(n) be the number of positive divisors of nn.For example, \sigma_0(1) = 1σ0(1)=1, \sigma_0(2) = 2σ0(2)=2 and \sigma_0(6) = 4σ0(6)=4.LetS_k(n) = \sum _{i=1}^n \sigma_0(...
2018-10-08 23:08:18
231
原创 洛谷：[国家集训队]middle（主席树 + 二分）
题目描述一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。输入输出格式输入格式： 第一行序列长度...
2018-09-29 22:46:04
197
原创 洛谷：牛场围栏（同余类BFS）
题目背景小L通过泥萌的帮助，成功解决了二叉树的修改问题，并因此写了一篇论文，成功报送了叉院（羡慕不？）。勤奋又勤思的他在研究生时期成功转系，考入了北京大学光华管理学院！毕业后，凭着自己积累下的浓厚经济学与计算机学的基础，成功建设了一个现代化奶牛场！题目描述奶牛们十分聪明,于是在牛场建围栏时打算和小L斗智斗勇！小L有N种可以建造围栏的木料，长度分别是l1,l2 … lN，每种长度的木...
2018-09-28 20:24:11
358
原创 洛谷：改造二叉树（LIS）
题目背景勤奋又善于思考的小L接触了信息学竞赛，开始的学习十分顺利。但是，小L对数据结构的掌握实在十分渣渣。所以，小L当时卡在了二叉树。题目描述在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数...
2018-09-28 16:16:09
538
原创 洛谷：多少个1？（BSGS）
题目描述给定整数KK和质数mm，求最小的正整数NN，使得 11\cdots111⋯1（N个1） \equiv K \pmod m≡K(modm)说人话：就是 111...1111 mod m =K输入输出格式输入格式： 第一行两个整数，分别表示KK和mm 输出格式： 一个整数，表示符合条件最小的NN 输入输出样例输入样例#1： 复制9 17...
2018-09-26 23:56:11
359
原创 计蒜客：String and Times（后缀自动机）
Now you have a string consists of uppercase letters, two integers AA and BB. We call a substring wonderful substring when the times it appears in that string is between AA and BB (A \le times \le BA≤t...
2018-09-15 20:13:34
419
原创 LOJ114：k 大异或和（线性基）
题目描述这是一道模板题。给由 n nn 个数组成的一个可重集 S SS，每次给定一个数 k kk，求一个集合 T⊆S T \subseteq ST⊆S，使得集合 T TT 在 S SS 的所有非空子集的不同的异或和中，其异或和 T1xorT2xor…xorT|T| 是第 k kk 小的。输入格式第一行一个数 n nn。第二行 n nn 个数，表示集合 S SS。第三行一个数 m...
2018-09-11 23:21:20
1668
原创 洛谷：传送方阵Mitrix（splay + 思维）
题目背景在博弈和yhzq颓废的时候，dp正在机房认真的学习。题目描述他正在学习如何玩一个游戏《传送方阵Mitrix》，据说如果通关，就可以被传送进入虚拟世界。游戏中，dp可以布置2n2n个传送方阵。这些方阵都是矩形。第ii个方阵的长宽分别是x_i,y_ixi,yi.他需要把nn个传送方阵一起放在一个坐标系里。方阵可以相互重叠。方阵的四条边必须平行于坐标系的X，Y轴。这些方阵...
2018-09-11 00:29:07
323
原创 BZOJ1861：Book 书架（splay）
1861: [Zjoi2006]Book 书架Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 2297 Solved: 1338[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候，每...
2018-09-05 19:54:37
158
原创 BZOJ3223：Tyvj 1729 文艺平衡树（splay + 区间翻转）
Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 Input第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1<=l<=r&...
2018-09-05 18:01:58
159
原创 BZOJ3224：Tyvj 1728 普通平衡树（splay）
Description您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1. 插入x数2. 删除x数(若有多个相同的数，因只删除一个)3. 查询x数的排名(若有多个相同的数，因输出最小的排名)4. 查询排名为x的数5. 求x的前驱(前驱定义为小于x，且最大的数)6. 求x的后继(后继定义为大于x，且最小的数)Input第一行为n，表示操作的个数,下...
2018-09-05 00:27:34
140
算法之道第二版
2017-03-28
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人