- 博客(256)
- 资源 (1)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 多线程排序+快速排序
多线程排序，主要是将整个排序的序列分成若干份，每一个线程排序一份，所以线程排序完成之后，就进行归并，相当于多个有序序列合并成一个有序序列。这里就需要用到线程屏障，也就是 pthread_barrier 系列函数。屏障，通俗的说就是一个比赛跑步的过程，所以队员就绪了，才能进行比赛。多线程排序也是，需要每个线程都是排序完成后，才能进行合并的过程。代码：#includ
2017-05-24 20:07:48
15245
1
原创 Linux简单高并发模型——Epoll + 线程池
首先是一个locker.h的文件，封装了信号量、互斥量、条件变量。在线程池中的任务队列需要互斥量的保护，当任务队列中有任务到达时，需要唤醒一个等待pthread_cond_wait()的线程，线程池停止时，需要唤醒所以的线程，调用的是pthread_cond_broadcast()。locker.h文件：#ifndef _LOCKER_H_#define _LOCKER_H_
2017-04-16 23:19:02
8922
3
原创 面试总结~~附：内存复制函数mymemcpy
前天，去了大学城一家公司面试C/C++实习生。 面试开始前，做了一套题，时间是一个小时。前面的选择题还好，基本都是C/C++的基础知识以及数据结构的知识，但有一些还是没有看到过的知识点。然后是简答题，这些都是比较熟悉的，回答的应该算到位。接下来的是程序题，第一个是写一个内存复制函数，需要考虑内存有重叠的情况。这题到最后还是没有写出来。第二题是单向链表的反转，很容易的写出来了。最后一题
2017-02-18 19:41:06
1195
原创 Linux C++ 实现简单的广播服务
简单的广播服务：就是客户端可以关注某个话题，当某个话题有信息发布了之后，关注了该话题的客户端就可以收到该信息。服务端主要是通过epoll来处理所有连接的文件描述符，某个文件描述符有事件产生就处理。客户端有两个，一个是关注话题的，一个是发布话题信息的。关注话题的客户端通过TCP连接，首先发送关注的话题，再等待话题信息的到来。发布话题信息的客户端通过UDP将某个话题信息发送到服
2017-01-05 22:06:43
1339
1
原创 Linux C++ 实现简易小型的Web服务器httpd
在这个简易版的Web服务器中，实现了GET静态数据，以及动态数据。 下面的是代码，其中有注释，可以很容易看明白。 #include #include #include #include #include #include #include #include #include #include #include #include #include #
2016-12-29 22:04:47
13773
1
原创 Linux C++ 回射服务器
回射服务器就是服务端将客户端的数据发送回去。 我实现的回射服务器返回增加了时间。 服务端代码，可以很容易看懂： #include #include #include #include #include #include #include #include #include #include "../thread_pool.h"#defi
2016-12-28 22:56:17
816
原创 Linux C++ 实现线程池
线程池中的线程，在任务队列为空的时候，等待任务的到来，任务队列中有任务时，则依次获取任务来执行，任务队列需要同步。 Linux线程同步有多种方法：互斥量、信号量、条件变量等。 下面是根据互斥量、信号量、条件变量封装的三个类。 线程池中用到了互斥量和信号量。 #ifndef _LOCKER_H_#define _LOCKER_H_#include #includ
2016-12-28 22:18:59
1406
2
原创 POJ1077——Eight
3 * 3的矩阵的八数码问题。比较简单因为输入的只是1-8，所以可以将x当作9.解决问题的关键是将数字序列根据康托展开转换成一个数，每一个数对应一个序列，所以可以用来判断这个序列是否查找过。用深搜搜索，总共9！种，还可以接受。下面是代码：#include #include using namespace std;const int SIZE = 362880;
2016-08-06 10:51:38
414
原创 POJ1068——Parencodings
模拟的题目。题目的意思是：一个包含括号的字符串，可以用两种方法来表示。P方法是：从左往右开始，每一个右括号，左边有多少个左括号，即写出该数，形成的数字序列即为P序列W方法是：从左往右开始，每一个右括号，往左边找第几个左括号来匹配，即写出该数，形成的数字序列即为W序列题目给你P序列，要求你求出W序列。模拟出括号字符串，再求出相应的W序列。代码：#inclu
2016-07-22 23:25:53
601
原创 POJ1028——Web Navigation
简单的模拟题目，模拟浏览器访问网址的前进和后退。需要注意的是每次访问新的网址时，需要清空前进的栈的
2016-07-21 22:38:55
453
原创 POJ3187——Backward Digit Sums
题目的意思：给你N和sum。在1~N的排列中，找到最小字典序的排列，使得这N个数的排序按照题目的方法能最后组成sum这个数。简单的穷竭搜索。用next_permutation枚举。下面的是AC的代码：#include #include using namespace std;int num[11];int temp[15];int main(){ in
2016-06-05 11:45:13
339
原创 POJ2718——Smallest Difference
题目的意思是：给你一行数，多少个不知道，每一个数都是一位数（0到9），要求求出这些数组成的两个数之差最小。很容易想到的是贪心的策略，可以将生成的所有排列平均分成两部分，求这两部分组成的数的差，不断更新最小差的值。需要注意的是0不能作为数字的开头，也就是n个数中，这样的排列是不行的，也就是0和n/2这两个位置为0.这样存在一种特殊的情况，就是两个数的时候，其中一个为0，这样所有的排列都不
2016-06-05 10:26:13
389
原创 Uva10954——Add All
题目的意思是：n个数的集合，从中拿出两个数删掉，并将他们的和放入集合。要使最后的数最小很容易想到类似与Huffman编码，但是我们可以更简单的实现，用优先队列。下面的是AC的代码：#include #include #include using namespace std;int main(){ int n, x, i; while(cin >> n &
2016-05-23 22:54:18
332
原创 Uva11054——Wine trading in Gergovia
题目的意思是：n个村庄，每一个村庄可能需要买酒或者卖酒，ai 为负，则需要买 ai 个酒，ai 为正，则需要卖 ai 个酒，从一个村庄运k单位酒到邻村需要k个单位的劳动力。求最小劳动力。考虑最左边的村庄。如果需要买酒，即a1大于0，则一定有劳动力从村庄2往左运给村庄1，而不管这些酒是从哪里来的。这样，问题就等价于只有村庄2~n，且第2个村庄的需求为a1+a2的情形。ai #
2016-05-22 18:40:50
378
原创 Uva1152——4 Values whose Sum is 0
分两边来枚举。减少时间复杂度。__int64在Uva上面用不了。。。代码很容易看懂。#include #include #include using namespace std;const int Maxn = 4005;int A[Maxn], B[Maxn], C[Maxn], D[Maxn];int AB[Maxn * Maxn];int main()
2016-05-22 15:02:28
309
原创 Uva1605——Building for UN
构造的题目，理解了题目的意思就很容易做。要你建一个大楼，有n个国家要在这里面办公，需要把格子分配给各个国家，任意两个国家都有一对相邻的格子（要么是相邻层的同一个格子，要么是同层中有公共边的格子）。只需构建两层的楼，第一层的第i列给第i个国家，第二层的第j行给第j个国家。构造出来的就符号题目的要求。AC的代码：#include using namespace std
2016-05-19 18:27:33
314
原创 Uva1157——Unique Snowflakes
题目的意思是：输入长度为N的序列，找到一个尽量长的连续子序列Ai~Aj，使得序列中没有重复的元素。可以用集合Set来求解。从0号位置开始，一直添加元素进去直到有重复，更新最长子序列的值，去掉最左边的元素，继续添加元素。不断的重复，更新。最终找到最大的子序列。下面的是AC的代码：#include #include #include #include using n
2016-05-14 23:23:51
577
原创 Uva120——Stacks of Flapjacks
简单的题目，可以直接按照题目的意思模拟那个过程就可以过了。题目的意思：一叠煎饼在锅里，每个煎饼大小不一样，煎饼叠在一起的，每次选一个位置k，从顶部往下数k个反转过来，求出最后煎饼按小到大的方案。每次输出的是煎饼的总数减掉反转的位置。（煎饼从上到下，1~n）。从底部开始往上，每次将最大的弄到最下面来，（当前位置为 j ）每次选最大的，然后选个最大的，位置是k，判断是不是在最上边，
2016-04-26 23:32:24
449
原创 Uva305——Joseph
约瑟夫环问题。#include using namespace std;int a[14];int main(){ int n; a[1] = 2; for(int i = 2; i < 14; i++) { for(int m = i + 1; ; m++) { int s = 0, j = 2 * i; while(1) { i
2016-03-27 19:36:51
757
原创 Uva299——Train Swapping
简单的题目。求冒泡排序交换的次数。#include using namespace std;int data[60];int main(){ int n, l; cin >> n; while(n--) { cin >> l; for(int i = 0; i < l; i++) cin >> data[i]; int ans = 0; fo
2016-03-27 18:55:01
601
原创 Uva160——Factors and Factorials
求n！的质因子个数。也就是2~n每个数的质因子的个数之和。输出的格式比较麻烦，需要注意。代码：#include #include #include using namespace std;int vis[110], prime[100], count = 0;int ans[100];void prime_table() //获取质数表{ int i,
2016-03-24 23:32:32
1130
原创 Uva216—— Getting in Line
题目的意思求n个点连起来的最短距离。n最大为8，直接枚举排列的所以情况，然后求最短的距离，最短距离等于连线上的每两个点的距离加上16的和.点的排序可以多种情况，只要找到最短距离就行。枚举排列用next_permutation函数。代码：#include #include #include #include using namespace std;int n,
2016-03-19 11:46:21
410
原创 Uva208——Firetruck
题目的意思：给你节点k，然后输入的是无向图，求1到节点k的所以路径。首先用Floyd算法算出两两之间的是否存在路径。然后在递归求出路径的时候可以很快的判断是否有路到达k节点。代码：#include #include using namespace std;const int maxn = 25;const int INF = 0xfffffff;int ma
2016-03-16 22:15:43
384
原创 Uva10048——Audiophobia
题目的意思，无向图中求某个点到另外一个点的路径上的最大噪声值，最大噪声值比其他路径上的最大噪声值小，比该路径上的噪声大。最后问的是有q个问题，每个问题存入两个点，求这两点之间的最大噪声值，直接用Floyd算法。代码：#include #include using namespace std;const int INF = 0xfffffff;int c, s,
2016-03-15 20:03:33
633
原创 Uva247——Calling Circles
求有向图的传递闭包，并输出各个连通分量的成员。输出各个连通分量，可以递归输出。代码：#include #include #include #include #include using namespace std;const int maxn = 40;int n, m;vector vec;bool data[maxn][maxn], vis[ma
2016-03-14 23:27:12
571
原创 Uva10603——Fill
求的是倒水量最小，不是次数。代码：#include #include #include #include using namespace std;struct Node{ int v[3], dist; bool operator < (const Node& a)const { return dist > a.dist; }};const int
2016-03-12 23:16:51
536
原创 Uva1151——Buy or Build && POJ2784——Buy or Build
最小生成树的应用。输入n个城市（1~n），和q个方案，接下来q行的第一个数为该方案中的城市数a，第二个数为用该方案需要的钱b，接下来a个数为城市的编号。接下来n行为第n个城市所在的坐标位置。在这些城市之间建设道路，使得两两城市直接连通。在两个城市之间建设道路，需要花费 两个城市之间的坐标的欧几里德距离，若买方案，则方案内的城市已经连通。先进行一次求最小生成树，再枚举方案再求最小生成
2016-03-12 16:29:03
793
原创 Uva1395——Slim Span
这题，最小生成树的应用，只是需要稍微变形一下。输入结点数为n，边数为m，对每条边进行从小到大排序，然后枚举枚举每一条边，从该边起到最后这些边中求最小生成树并找到权值最大的边。不断的更新最大权值与枚举的边的差值。代码：#include #include using namespace std;const int maxn = 110;int m, n;
2016-03-12 14:20:18
651
原创 Uva108——Maximum Sum
题目的意思，求矩阵的的子矩阵的最大和。暴力枚举行的组合，将各列数值相加，再查找最大连续和，更新最大值即可。代码：#include #include #include using namespace std;const int maxn = 110;int data[maxn][maxn], n;int main(){// freopen("1.txt
2016-03-10 14:46:03
583
原创 Uva524——Prime Ring Problem
简单的回溯的应用。代码：#include #include #include using namespace std;int data[50], vis[50], n;int is_pre[50];void dfs(int x){ if(x == n && is_pre[data[0] + data[n - 1]]) { cout << data[0];
2016-03-10 13:09:39
409
原创 Uva10976——Fractions Again?!
简单的题目，很容易看懂。主要是枚举，但是枚举的范围不确定。从x >= y , 推出 1 / x 然后就是枚举，暴力过。代码：#include #include #include using namespace std;int data[15000];int main(){// freopen("1.txt", "r", stdin); int k,
2016-03-08 19:26:16
501
原创 Uva11057——Exact Sum
简单的题目，在N个数中找到差值最小的并且相加等于所给的 M。直接暴力枚举，数据量较小。代码：#include #include #include using namespace std;int data[10010];int n, money;int main(){// freopen("1.txt", "r", stdin); int i, j; w
2016-03-08 19:06:28
479
原创 Uva11059——Maximum Product
暴力枚举，数据量相对较小。不过__int64 这个类型过不了。代码：#include #include using namespace std;int data[20];int n;long long Max, ans;int main(){// freopen("1.txt", "r", stdin); int i, j, t = 0; while(cin
2016-03-08 18:39:00
246
原创 Uva725——Division
简单的题目，暴力枚举可以过。只不过我第一次用的是五重循环枚举一直WR，2到79 的答案都对，就是不过，不知道为毛。。后来改用直接枚举其中一个数。代码：#include #include #include using namespace std;int ans[10];bool flag;int cheak(int x, int y){ memset(ans, 0
2016-03-07 22:15:25
250
原创 Uva12118——Inspector's Dilemma
这题的意思：给你V个城市，两两城市有双向的通路，给你E个边，求最短路径走过这E个边。边长为T。一开始以为是BFS来求解，但是怎么都想不到切入口。后面看到欧拉两个字，恍然大悟，这题就是无向图的欧拉回路的求解。只不过，还需要判断图是否连通，存在多个连通图，需要将他们连通起来。然后判断各个节点的度，奇数的节点大于2，则需要加上 奇数点 / 2 - 1个边，才能使图存在欧拉回路。下面的代码
2016-03-07 15:56:22
688
4
原创 Uva1600——Patrol Robot
这题：找最短路径，只是可以跨越障碍，不能连续跨越K个障碍。可以通过BFS做。一开始我没有用vis数组，是在输入的矩阵中操作的，结果一直WR，不明白，为毛加了vis就可以，同样是标记的，自己还是有待提高。下面AC代码：#include #include #include using namespace std;struct node{ int x, y,
2016-03-05 17:47:51
373
原创 Uva439——Knight Moves
简单的BFS。只是国际象棋的棋盘有点特殊，坐标需要转换下。AC代码：#include #include #include using namespace std;struct node{ int x, y, count;};int xy[8][2] = {-1, -2, -2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2};
2016-03-05 14:28:47
293
原创 Uva536——Tree Recovery
根据先序遍历以及中序遍历，构造二叉树，输出后序遍历。代码：#include #include #include using namespace std;struct node{ char c; struct node *lchild, *rchild;};node *Root;int len;char pre[30], in[30];void crea
2016-03-05 13:44:48
361
原创 Uva712——S-Trees
输入的第一行数字，是该满二叉树的叶子节点。接下来m行是查找叶子节点的数值的，0 向左走， 1 向右走。 用数组来表示二叉树。根节点为k，左孩子为2*k + 1，右孩子为2*k + 2。代码：#include #include #include using namespace std;char str[8][5];int num[300], ans[150
2016-03-05 11:35:03
351
原创 Uva673——Parentheses Balance
题目很简单，栈的应用。需要注意的是空串也是合法的。AC代码：#include #include #include #include using namespace std;int main(){// freopen("1.txt", "r", stdin); int n; bool ans; char str[140]; cin >> n; getchar
2016-03-05 10:25:17
326
vs2013 fstream 无法打开文件
2015-03-10
TA创建的收藏夹 TA关注的收藏夹
TA关注的人