`
plussai
  • 浏览: 90680 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论
文章列表
    问题:要处理200000个自然数,统计每个不同的自然数出现的次数(不同的自然数个数小于10000)。      算法思路:将N个不同的键值对nodePair(num,value)存在一张HashTable中,可以达到O(1)的存取效率(不考虑冲突)      1)使用什么样的HASH函数,这里使用fibonacci散列法。      HashCode=n*265435769>>18。为什么是左移18位,因为2^14=16384>10000,满足10000个不同自然数的要求      2)如何处理寻址冲突,这里使用顺延法。当然顺延会导致存取的效率略慢。      代码如下 ...
先上代码: int sub(int x=8,int y=3) { return x-y; } void main() { sub(20,15); //20-15 sub(10); //10-3 sub(); //8-3 } 注意事项 1)C++调用函数时,参数是自由到左入栈的。因此,默认形参必须从右向左连续定义,并且在一个默认形参的右边不能有非默认的形参。 int f(int a,float b=5.0,char c='.',int d=10);//正确 int f(int a=1,float b=5.0, ...
    并查集被评为历史上最经典的算法。其形式很简单,但是可以对数据进行很高效的处理。并查集的主要功能为1)合并两个不相交的几何2)查找元素是否在同一个集合中。      并查集为简单的树形结构,没一个节点指向它的父节点,根节点指向它自己。我们可以用一个数组father[]来表示元素的父子关系,用一个数组count[]来表示每一个节点所在集合的元素个数。      并查集可以提供几个操作1)获取一个节点所在集合的根节点2)判断2个元素是否在一个集合3)合并2个不相交的集合。      并查集在1操作中可以结合路径压缩,提高并查集的查找性能 zoj2833 #include<iostre ...
    dijkstra算法个人感觉挺怪异的,不过复杂度O(n2),速度快,但是不能理解WSM很多人都推荐用FLOYD,可能是实现简单吧,但是FLOYD必须用邻接矩阵来实现。两者的功能上稍有不同,dijkstra算法对于输入的节点,能够找出该点到所有其他点的最短路径。     基本的算法思路是,把图中的点集分为2部分,一部分为访问过的点(即已经找到了输入点到该点的最短路径),另一部分为还没访问到的点。dijkstra算法的进行过程就是把第二类点归并到第一类点的过程。     如何归并,首先在第二类点中找到距输入点(v)距离最近的点(i),把这个点归入第一类,然后开始更新其余第二类点到输入点的距离 ...
  FLOYD用于求图中任意点对的最短路径,DP,时间复杂O(N3),状态转移方程dist[i][j]=min{dist[i][j],dist[i][k]+dist[k][j]},dist[i][j]表示节点i到节点j的最短路径,如果dist[i][j]的值发生改变,path[i][j]=k,表示从节点i到节点j需要连续经过i,k.如path[0][5]=4,path[4][5]=3,path[3][5]=5可以推出从节点0到节点5的路径为0-4-3-5. #include<iostream> #include<string.h> using namespace ...
    从哪里跌倒从哪里爬起来,明年我会再来见你的,亲爱的百度HR。艰苦的路从LCA开始。如何求一棵树中节点的最近公共先祖,Tarjan算法,复杂度O(N)网上说O(N+E)有点不太能理解,基于深度优先搜索和并查集。      算法基本思路,从根开始深度遍历,经过任意一个节点,都要以该节点为根建立一个集合,随着深度遍历的进行,当一个节点的子节点标记被访问时(即该子节点的所有子节点都标记被访问),将该节点所在的集合和该子节点所在的集合合并,并以该节点为根。上述的过程随着深度遍历递归进行。      遍历的过程同时也是查询的过程,当遍历到的节点是其中查询的节点中的一个,判断另一个节点是否已经被访问, ...
   一大早还没怎么睡醒就打了辆车去酒店面试,到了9点,我被带到一个房间,里面摆了张桌子,上面有纸笔。面我的是个看起来挺年轻的GG,说话感觉挺亲切稳重的。    上来让我写快速排序,基本的思想我清楚,但是写到了的比较交换那个地方有点卡壳,但是还是更具自己的理解把代码完成了。之后果然,他看看我的代码之后,对比较交换的那部分有些疑问,针对我的代码让我想想优化的方案,我嗯嗯啊啊没有给出理想的方案。之后让我分析了快速排序的复杂度,这个还算顺利。    然后给了个算法题,让我求一颗树中任意2个节点的最近公共父节点,我擦了。。。之前没听说过。一开始,我还以为通过子节点可以直接找到父节点,结果GG说,不提供这 ...

const与指针

const 使用情况分类详析   const 用于指针的两种情况分析:   int const *a; //a/可变,*a不可变   int *const a; //a不可变,*a可变   分析:const 是一个左结合的类型修饰符,它与其左侧的类型修饰符合为一个类型   修饰符,所以,int const 限定 *a,不限定a。int *const 限定a,不限定*a。
最近要百度面试,压力有点大。。。复习一下 已知 char *str1="absde";      char str2[]="absde";      char str3[8]={'a',};      char ss[] = "0123456789"; sizeof(str1)=4 sizeof(str2)=6; sizeof(str3)=8; sizeof(ss)=11 首先说明一点,char类型占一个字节,所以sizeof(char)是1,这点要理解 str1是一个指针,只是指向了字符串"absde" ...
先在百度上抄两段:     问题:已知序列X,Y,求序列Z,使得Z是X,Y的子序列,不要求连续,且Z严格递增   最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。简而言之,百度知道、百度百科都用得上。     显然穷举发需要指数开销,DP开销可以到O(MN)    用C[i][j]记录序列X,Y的最长公共子序列的长度,有如下动态规划状态转移方程: C[i][j]=0    i=j=0; C[i][j]=c[i ...
要去百度面试,心情很复杂,复习一下DP DP经典问题,LIS---最长上升子序列。 设A[i]表示序列中的第i个数,F[i]表示从1到i这一段中以A[i]结尾的最长上升子序列的长度,初始时设F[i] = 0(i = 1, 2, ..., len(A))。 则有动态规划方程:F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])。 举例:原序列为1,5,8,3,6,7 F[0]=1,F[1]=2,F[2]=3,F[3]=2,F[4]=3,F[5]=4 
order数组是栈指针,利用栈指针将递归问题转化为回溯的非递归问题 #include<stdio.h> #include<iostream> using namespace std; int getCombine(int*a,int* order,int m,int n) { while(1) { int flag=0; for(int i=1;i<=n;i++) { if(i==n) { if(order[i]==m) order[i]=order[i-1]+1; else order[i ...
递归组合算法 算法思想:对于一个长度为M的序列,要求N个数的组合。 1.从索引最小的元素遍历到第N-M个元素,将遍历到的元素定为组合中的第一个元素 2.判断组合中N个元素是否已满,如果满了,打印该组合,如果不满重,则截取1中选择的元素之后的序列,复步骤一。 #include<stdio.h> #include<iostream> using namespace std; void getCombine(int* a,int* b,int m,int n,int index) { for(int i=0;i<=m-n;i++) { b[ind ...
今天做作业 ,研究凸包算法,写了一个专说中很快的方法。听说效率N,算法的精髓在于任何的判断操作都基于一个点和向量的位置关系。 例如,要判断点是否在多边形内,只需判断点和每条边向量的位置是否都一直,都在左边或者都在右边。 bool CGrahamView::isLeft(CPoint point,m_line *line) { //m_line x; float a=line->a; float b=line->b; float c=line->c; float v=a*point.x+b*point.y+c*1.0f; if(v<=0) ...
今天写作业 ,想通过写一个函数createLine来创建一条直线于是开写 m_line* CGrahamView::createLine(CPoint i, CPoint j) { m_line* line; line->i=i; line->j=j; line->a=i.y-j.y; line->b=j.x-i.x; line->c=i.x*j.y-j.x*i.y; return line; }    FUCK出错了。。而且是内存问题,后来找到了这段函数,想了想,发现栈中的m_line对象貌似已经消亡,返回的指针指向的对象不 ...
Global site tag (gtag.js) - Google Analytics