vergilwang的博客
vergilwang · 共 341 篇文章
集合合并
百度面试题:将多个集合合并成没有交集的集合 2010-03-20 18:25 给定一个字符串的集合,格式如:{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应输出{aaa bbb ccc ddd hhh},{eee fff}, {ggg}。 (1)请描述你解决这个问题的思路; (2)请给出主要的处理流程,算法,以及算法的复杂度 (3)请描述可能的改进。 解决方案: 采用hash的方法,key为字符串,value为一个链表,存储集合编号。 算法思想: 用一个数组来存储集合…
2013-04-23 16:42 · Algorithm · Data structure · 评论(0)
求全排列问题
基本思路就是: 1、判断是否到达数组末尾,若是,输出数组,返回。 2、否则依次取出片段数组的每个元素,对剩下的元素组成的片段数组再进行排列。 注意,生成第二步的剩余片段数组的技巧是将每个元素与片段首个元素互换,这样首个元素之后到数组末尾的连续元素 就是 剩余片段数组——当然,互换完了还要互换回来,否则 第二步的剩余片段数组 的内容就会混乱。 #include<stdio.h> #include<stdlib.h> voidswapArrayElements(chara[],intlhs,intrhs) { chartemp; temp=a[lhs]; a[lhs]=a[rhs]; a[rhs…
2013-04-23 13:10 · Algorithm · 评论(0)
C++ STACK Queue
STL--stack/queue的使用方法 2010-01-05 17:36 stack(栈)和queue(队列)也是在程序设计中经常会用到的数据容器,STL为我们提供了方便的stack(栈)的queue(队列)的实现。 准确地说,STL中的stack和queue不同于vector、list等容器,而是对这些容器的重新包装。这里我们不去深入讨论STL的stack和queue的实现细节,而是来了解一些他们的基本使用。 1、stack stack模板类的定义在<stack>头文件中。 stack模板类需要两个模板参数,一个是元素类型,一个容器类型,但只有元素类型是必要的,在不指定容器类型时,默认…
2013-04-22 20:47 · Data structure · C++ · 评论(0)
C++ Set常用用法
set集合容器:实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,把元素放到适当的位置,以保证每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值;另外,还得保证根节点左子树的高度与右子树高度相等。 平衡二叉检索树使用中序遍历算法,检索效率高于vector、deque和list等容器,另外使用中序遍历可将键值按照从小到大遍历出来。 构造set集合主要目的是为了快速检索,不可直接去修改键值。 常用操作: 1.元素插入:insert() 2.中序遍历:类似vector遍历(用迭代器) 3.反向遍历:利用反向迭代器reverse_iterator。 例:…
2013-04-22 19:24 · Data structure · C++ · 评论(0)
腾讯附加题
给定一个数组a[N],我们希望构造数组b [N],其中b[j]=a[0]*a[1]…a[N-1] / a[j],在构造过程中,不允许使用除法:要求O(1)空间复杂度和O(n)的时间复杂度;除遍历计数器与a[N] b[N]外,不可使用新的变量(包括栈临时变量、堆空间和全局静态变量等) 解析:设b[0]=1 由b[i]=b[i-1]*a[i-1]可得 b[1] = a[0] b[2] = a[0]a[1] … b[i] = a[0]a[1]a[2]…a[i-1] … b[n-1] = a[0]a[1]…a[n-2] 那么再通过b[0]这个变量来迭代出1, a[n-1], a[n-2]a[n-1]…
2013-04-22 14:08 · Algorithm · 评论(0)
哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算
最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 (1) 请画出所构造的散列表。 …
2013-04-20 00:10 · Algorithm · Data structure · 评论(0)
const pointer
const在函数前与函数后的区别 一 const基础 如果const关键字不涉及到指针,我们很好理解,下面是涉及到指针的情况: int b = 500; const int* a = &b; [1] int const *a = &b; [2] int* const a = &b; [3] const int* const a = &b; [4] 如果你能区分出上述四种情况,那么,恭喜你,你已经迈出了可喜的一步。不知道,也没关系,我们可以参考《effective c++》item21上的做法,如果const位于星号的左侧,则const就是用来修饰指针所指向的变量,即指针指向为常量;如果con…
2013-04-19 21:23 · C++ · 评论(0)
BookList
[收藏]最近看到的机器学习、NLP相关书单 2013年04月01日⁄ 读书 ⁄ 共 310字 ⁄ 评论数 3 ⁄ 被围观 557 阅读+ 书单再多,不去读,也是白搭~~ 水木上的machine learning书单: http://www.newsmth.net/bbscon.php?bid=5&id=34859&ftype=11 weibo上 @王威廉 最近有人询问教材的问题,在此我列12本北美比较常用的机器学习/自然语言处理/语音处理经典书籍。欢迎各位补充。 http://weibo.com/1657470871/zpZ87mhND 还有以前整理的一个书单: http://www.zhi…
DP经典5题
DP一年多没碰过了,今天突然想找找感觉,找了经典的几道DP复习着敲了敲。虽然最大子矩阵,滑雪,石子合并等问题也足够经典,我还是从中找了5道最经典的DP写了这篇博文,如果您是大一,大二想踏入程序竞赛的同学可以当习题做做,如果您像我一样不是ACMer,平时项目中也很少用DP,同样可以回顾一下DP的奥妙。 1.最大连续子序列之和 给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序中元素和最大的一个, 例如给定序列{ -2, 11, -4, 13, -5, …
2013-04-16 18:08 · Algorithm · 评论(0)
卡特兰
http://buptdtt.blog.51cto.com/2369962/832586 http://blog.csdn.net/hackbuteer1/article/details/7450250
2013-04-15 21:13 · Algorithm · 评论(0)
动态规划基本问题
http://www.cnblogs.com/chinazhangjie/archive/2010/11/16/1878400.html 动态规划 动态规划 算法总体思想 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。 动态规划基本步骤: (1)找出最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方…
2013-04-12 13:29 · Algorithm · 评论(0)
基本动态规划讲解
动态规划 动态规划 算法总体思想 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。 动态规划基本步骤: (1)找出最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息,构造最优解。 实例一、完全加括号的矩阵连乘积 问题可递归定义: (1)单个矩阵是完全加…
2013-04-12 13:28 · Algorithm · 评论(0)
(int&)a和(int)a的区别
(int&)a和(int)a的区别 float a = 1.0f; cout << (int)a << endl; cout << (int&)a << endl; cout << boolalpha << ( (int)a == (int&)a ) << endl; // (1)输出什么? float b = 0.0f; cout << (int)b << endl; cout << (int&)b << endl; cout << boolalpha << ( (int)b == (int&)b ) << endl;// (2)输出什么? 输出结果是: 1 1065353216 fals…
2013-04-11 16:34 · C++ · 评论(0)
程序员面试【Brainteasers】
偶然间在网上看到几个原来没见过的面试智力题,有几个题目在国内流传相当广,什么n个人怎么分饼最公平,屋里的三个灯泡分别由哪个开关控制,三架飞机环游世界,用火柴和两根绳子测量45分钟之类的题目,火星得已经可以考古了,这里就不再说了。 1、考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币,每次必需且只能放置一枚硬币,要求硬币完全置于桌面内(不能有一部分悬在桌子外面),并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币,谁就输了。游戏的先行者还是后行者有必胜策略?这种策略是什么? 答案:先行者在桌子中心放置一枚硬币,以后的硬币总是放在与后行者刚才放的…
2013-04-10 14:48 · Algorithm · 评论(0)
素数生成算法
1. 根据概念判断: 如果一个正整数只有两个因子, 1和p,则称p为素数.这是通常最先想到的判断方法: 代码: bool isPrime(int n){ if(n <2)returnfalse; for(int i =2; i < n;++i) if(n%i ==0)returnfalse;returntrue;} 时间复杂度O(n). 2. 改进, 偶数都可以被2整除,去掉所有偶数 代码: bool isPrime(int n) { if(n <2)returnfalse; if(n ==2)returntrue; if(n%2==0)returnfalse; for(int i =3; …