- 浏览: 90680 次
- 性别:
- 来自: 杭州
最新评论
-
zhyawshhz:
顶上!我就是算缺少代码能力型的 !
百度面试归~~我还是太年轻了。。。。 -
lanjf635241:
...
递归组合算法
文章列表
问题:要处理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 用于指针的两种情况分析:
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对象貌似已经消亡,返回的指针指向的对象不 ...