- 博客(31)
- 收藏
- 关注
RSS订阅转载 算法和数据结构的实际应用
转自：http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/19773#19773181down voteacceptedAlgorithms that are the main driver behind a system are, in
2013-11-24 21:21:58
1430
原创 szuoj b47 有符号大整数加减法
题意很简单：输入两个整数A和B（范围均为10的-1000次方到10的1000次方之间）。输出A+B，和A-B。题目有一点没有讲清楚，就是要去掉前导0，即-000000也是0-00001是-1000000是000001200是1200因为不知道这个，WA了好多次拙计如下代码这个思路是，不管有没有前导，都可以处理。第一步：实现一个加法函数和减法函数，
2013-07-26 17:40:00
2309
原创 【面试题】1到1000有多少个7？
考官直接问，1到1000到多少个7？要求，不编程，直接给出答案，并简单给出思路。————————第一种思路——————————首先应该有个合理的归类，我一开始就想到了一个合理的分类法，即可1到1000，每个数都看作3位数，而1000明显没有7，不考虑那1看成001，19看成019，以此类推。这样每个数字可以用三个格子表示，就有了一个统一的表示
2013-07-21 17:25:35
5188
原创 C++:虚函数和多态
//举例理解虚函数和多态#include using namespace std;/* 动物 / | \ 陆动物 水动物 / | \ 狗 马这里的动物、陆动物、水动物都是抽象类，因为他们不存在实例(对象)没有一个具体的"它"，可以说"它是动物"（这里是“是”不是“属于”的意思而狗类可以有一个具体"它"，可
2013-05-31 20:43:15
642
原创 C语言：关于数组指针
//关于指向数组的指针#include //我们知道，将数组传入函数时，参数表写成数组形式本质上仍是指针（有些人称之为退化）//其实可以看成一个语法糖//比如以下四个函数中的参数写法 对于编译器来看 是一模一样的//对编译器而已，最直接（经过最少转化）的写法是最后一种void f10(int a[10]) //按照数组声明的形式（不带分号）{ printf("%d\n", a[0
2013-05-31 19:51:46
625
原创 简单面试题::字符串按单词反转
字符串按单词反转输入格式是："this is a string"输出格式是: "string a is this"要求不能用任何库函数这个题目看似非常简单，但是用纯C语言且不用任何库函数来写，还是挺考察基础的。下面给出一个实现，对于单词之间有多个空格的（称之为“缝隙”），每个单词之间的相对缝隙不作改变。比如I_kill___you输出会是you___kill_I
2013-05-31 13:49:15
10831
原创 STL map的使用
刚学了标准模板库的map，感觉很好很强大，所以马上做题试试！！！map是一个容器。最直观的用法就是先定义一个容器：map mapsi;通过这样子来映射——mapsi[字符串] = 整形数字最后遍历的话，用迭代器，it->first是关键字（索引），it->second是映射的内容另外，这个容器里面元素的类型实际上是pairhdoj1004这个最典型最基础了，完全
2013-05-30 20:05:53
650
原创 poj2945
前阵子用Trie树过了poj2945，当然题目本身比较水，但数据量应该还是比较大的。限制时间为5秒。4548K && 547MSTrie树解法：#include #include #include using namespace std;int const childnum = 4;const int map[] = { 0, -1, 1, -1, -1, -1, 2
2013-05-30 09:41:18
1086
原创 Trie树学习
最近重看了下KMP，然后学习AC自动机、DFA（Trie图），但发现还没有做过Trie树的题目。于是做了四五题简单的Trie树。Tire树，发音“Try树”，也就是字典树。建立和查询的方式，类似我们建造字典和查询字典。比如she he her his share查找her，我们会找到h开头的那部分，然后找到he开头的部分，最后找到这个单词her。当然，建立字典也是类似的，只是不是查看而
2013-05-23 17:27:32
1890
原创 Dijkstra算法求单源最短路径
与Prim算法朴素版实现起来差不多。。。//朴素版Dijkstra算法//输入一个图的矩阵，假定两点不相邻则权值为0//输出每个顶点的最短路径长度,可以打印指定顶点的路径//Dijkstra算法跟Prim算法很像//相同的地方是://两者都有一个已经求得"MST"和已经求得"最短路"的集合//每纳入一个结点x到集合，更新的是集合外与x直接相连的点的key[]或者d[
2013-05-14 20:04:58
3030
1
原创 Prim算法求最小生成树 附hdoj1162
以下测试数据所用的图为：#include using namespace std;//Prim算法//朴素版本/*key[所有] = INF；done[所有] = false；par[i] = -1;根据指定树根r，设置key[r] = 0;执行n次{选择key[]最小的一个点，记录为xdone[x] = true对于所有x可达的点，更新它们key[]及pa
2013-05-14 17:26:51
777
原创 并查集的实现
上一篇实现kruskal算法用到了并查集，并大概自说自话地讲了并查集的原理。即只关心是否属于一个集合这个属性，不关心元素之间的关系（并查集看着有根树，肯定是连通且无环的），即不关心它们是怎么连接的。通常优化并查集的查询，用到了一种叫做路径压缩的技术。这个听起来很高端，其实没什么。如果觉得递归版本不好理解，就使用迭代版本。优化并查集的合并，用到了一种叫做按秩合并的做法，用一个ra
2013-05-14 14:33:25
3054
原创 Kruskal算法求最小生成树 附hdoj1162
自己实现的kruskal算法。其实懂了并查集，实现kurskal算法便很简单了。按照克鲁斯卡尔算法，从最小的边开始选（所以把所有边按权值非降序排序），然后选的过程一定是从小到大地选，如果发现不适合的就抛弃，而且绝对不会回溯再次检查是否适合（不吃回头艹）。因此如何判断边适合就是算法的关键了。这里的关键其实就是并查集，并查集是用集合的观点来看结点与结点的关系。结点作为元素，只有属于和不属于
2013-05-14 12:04:48
3994
原创 堆排序 纯C代码
跟上一篇实现思路一样，感觉还是少出现点幻数比较好，由于heapAdjust()调用频繁，故要尽量提高这段代码的效率#include #define N 1000#define INF 999999999int h[N];//调整堆(迭代法)//n：规模 i：二叉子堆的堆顶voidheapAdjust(int n, int par){ int tmp, pos, lc,
2013-05-13 22:44:30
7326
原创 自底向上实现堆排序
堆排序是变治法的一个实例以实现大根堆为例首先，设置一个数组h[N]存储堆，第一个元素h[0] = INF，不作使用，堆元素从1到n；其次，完全二叉树是指：除最后一层，树的每层是满的，最后一层最右边的元素可以缺少；堆需要满足两个条件：（1）堆逻辑上看是一颗完全二叉树，这具备了一些性质：如父母结点（非叶子结点）下标一定是从1到n/2（'/'为整除）（2）父母结点
2013-05-13 20:01:16
5906
2
转载 uva难度表
#IDTitleSolved byDifficulty1100The 3n + 1 problem2648512102Ecological Bin Packing10608231007
2013-04-05 16:42:34
20103
转载 ACM做题细节！
1. 如果题目是枚举的话,即最后化成十分简单的形式比较小, 可以直接将各种不同状态的结果运算过程写出来,但是这并不见得比写函数要快多少 而且比较容易出错,比如下标没有更改之类,这种错误比较烦人,因为你会查看算法, 但是算法本身并没有错误,所以如果复制粘贴的话,注意不同情况的不同点,如果自己 不够细心,最好写成函数的形式(注意判断边界),以
2013-04-05 00:33:10
1635
原创 算法竞赛入门经典第四章 【uvaoj在线习题（二）】
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96uva401http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&probl
2013-03-30 19:34:29
1510
原创 hdoj2024
这是一个水题，但是怎么提高程序的可读性是一个无止境的问题程序是用来：测试多组字符串是否符合C语言的命名规则程序首先定义test case(tc)然后每次读入一行字符串，这行“字符串”不是标准读入的，包含了换行符首先判断str的第一个字符是否为数字，是的话即可以下结论输出NO后进入下一次测试；否则判断字符串是否含有 合法字符集（isalnum or is'_'） 以外的字符，是的
2013-03-30 12:00:38
1188
原创 算法竞赛入门经典第4章 【uvaoj习题（一）】
题目合集http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=94uva10055http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=94&page=show_probl
2013-03-30 11:53:50
4719
转载 算法竞赛入门经典+挑战编程+USACO
下面给出的题目共计560道，去掉重复的也有近500题，作为ACMer Training Step1，用1年到1年半年时间完成。打牢基础，厚积薄发。 一、UVaOJ http://uva.onlinejudge.org 西班牙Valladolid大学的程序在线评测系统，是历史最悠久、最著名的OJ。 二、《算法竞赛入门经典》 刘汝佳 （UVaOJ 351道题）
2013-03-28 20:47:26
4471
原创 算法竞赛入门经典第3章【小结与习题】
习题3-1 分数统计(stat)输入一些学生的分数，哪个分数出现的次数最多？如果有多个并列，从小到大输出。任务1：分数均不超过100的非负整数任务2：分数均不超过100的非负实数，但最多保留两位小数。这个类似单词统计词频，按字典序输出频率最高的那些。【思路】pic任务1和任务2差不多，换成double类型即可；现在以任务1为例解答——一种思路是从第二个读入的
2013-03-27 20:50:11
2992
原创 算法竞赛入门经典第3章【读书笔记】
【学习目标】01掌握一维数组的声明和使用方法（OK）02掌握二维数组的声明和使用方法（OK）03掌握字符串的声明、赋值、比较和连接方法（连接很少用）04熟悉字符的ASCII码和ctype.h中的字符函数05正确认识++、+=等能修改变量的运算符（OK）06学会用编译选项-Wall获得更多的警告信息（OK）07了解不同操作系统中换行符的表示方法（嗯）08掌握fgetc
2013-02-08 09:10:59
1144
1
原创 算法竞赛入门经典第2章【读书笔记】
【学习目标】01掌握for循环的使用方法（OK）02掌握while循环的使用方法（OK）03学会使用计数器和累加器（OK）04学会使用输出中间结果的方法调试（OK）05学会用计时函数测试程序效率（不熟悉）06学会用重定向的方法读写文件（基本不会）07学会用fopen的方式读写文件（基本不会）08了解算法竞赛对文件读写方式和命名的严格性（嗯）09记住变量在赋值之前
2013-02-03 20:36:29
953
1
原创 算法竞赛入门经典第2章【小结和习题】
2.4.1 输出技巧#include intmain(void){ int i, n; scanf("%d", &n); for (i = 1; i <= n; i++) printf("%d\n", i); return 0;}目的：输出2, 4, 6, 8, ..., 2n任务1：只修改printf()printf("%d\n", 2*i);\
2013-01-30 22:36:56
5360
4
原创 算法竞赛入门经典第1章【读书笔记】
虽然前四章内容比较基础，是作者给出了不少细节问题，值得全面学习一遍。由于时间紧迫，所以先按照学习目标做一次学习。第一章【学习目标】01熟练C语言程序的编译和运行（OK）02学会编程计算并输出常见的算法表达式的结果（数学函数不熟悉）03掌握整数和浮点数的含义和输出方法（对浮点数陷阱理解不够）04掌握数学函数的使用方法（包括常用的哪些？）05初步了解变量的含义（
2013-01-30 19:02:33
1037
原创 算法竞赛入门经典第1章【小结与习题】
数据类型：6个1的平方用int数据类型存已经溢出了，并且用-Wall还给出警告：test.c:7: warning: integer overflow in expression。6个1的平方用double没问题，修改程序时，只需要改111111*111111为111111.0*111111就能正确运行了。sqrt(-10) 没有报错，输出是nan；而用"%d"来输出，警告
2013-01-30 18:58:16
3533
4
转载 9个offer，12家公司，35场面试，从微软到谷歌，应届计算机毕业生的2012求职之路
转自：http://www.cnblogs.com/figure9/archive/2013/01/09/2853649.html感谢作者的分享！字体加颜色是我加的，原文字体全黑。9个offer，12家公司，35场面试，从微软到谷歌，应届计算机毕业生的2012求职之路1，简介毕业答辩搞定，总算可以闲一段时间，把这段求职经历写出来，也作为之
2013-01-29 16:09:07
3652
1
原创 素数筛
素数筛#include #include #include #define N 10000int v[N];//visited indicated not primeintmain(void){ int i, j, n, m; scanf("%d", &n); memset(v, 0, sizeof (int)); m = (int)sqrt(n+0.5);
2013-01-26 15:25:45
456
原创 关于二分查找
二分查找实现起来确实非常容易出错，下面贴几个我实现过的版本。实现思想：二分查找是分治思想应用的一个典型例子，对于递归实现，可以画一个二分查找树来辅助理解，这棵动态生成树并不像归并排序那样需要全部遍历（前序），而是根据条件判定生成结点且仅遍历其中一个结点或者中止遍历。【版本一】直观递归（成功则返回查找元素key的下标，不成功则返回-1或者返回小于key的最大元素下标）
2013-01-22 11:30:57
1624
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人