“算法&&ACM”目录存档

几个在线教育网站的使用感受

2014年01月12日,星期日

最近经常使用的在线教育站点有Coursera,CodeSchoolCodeCademy

先说下Coursera,这个应该是知名度最高的,覆盖了很多学科。教课的形式跟大学差不多,一般是每周放出几段视频(每段十几二十分钟)和课后作业,课后作业各种形式的都有:问答的,提交程序代码在线测评的,同学之间相互测评的等等。今年以来,Coursera对中文的支持提高了很多,第一次访问Coursera的界面都是中文的比较友好,另外中文教学课程也逐渐丰富,典型的比如国立台湾大学的《機器學習基石》、《機率》,上交的《数学之旅》、《社会与法》,北大的《计算概论A》、《人群与网络》等等等等。当完成一项课程合格之后,大多数会提供一份Statement of Accomplishment, 就是pdf版的证书。Coursera还有一项收费服务Signature Track,提交作业时会有让用户打一段文字并会拍摄头像识别是不是本人,如果成功完成课程会有学校官方认可的证书发放,可以放到简历或者LinkedIn上。不过在国内这种环境下貌似意义不大,唯一有意义的是催促你按时完成课程,毕竟一份Signature Track要四五十刀,不过了就可惜了。在Coursera上混了一年多,只完完整整学完了两门课,一门是创始人Andrew Ng的《Machine Learning》,另一门是仅有四周的《Computing for Data Analysis》,主要原因是太贪了,有时候同时进行十几门,哪能学好呢。我现在老实了,在一个时间段只学习一门课程,现在正在跟的是UIUC的Android课程,并且注册了Signature Track,希望能认真完成,然后再去找其他感兴趣的东西。

推荐课程:
(更多…)

又是一年校招时

2013年10月10日,星期四

这两天刷微博,发现去年关注的很多校园招聘的账号又开始浮出水面了,各个公司都开始造势,吸引优秀的应届毕业生。与此同时,千千万万蛋子们浏览心仪公司的招聘页面,计划着行程,希望能找到个好工作。想起去年这个时候,我在郑州、武汉和西安之间折腾了几个月,为工作奔波,中间还生了场小病,不过还好,结局是美好的,从实习到现在已经工作了半年了,感觉还算可以,最近工作不是很忙,详细回忆下我找工作的历程。

找工作的构想是从大三区域赛结束之后开始的,那时,北京站凑合拿了个铜牌倒数第一,成都站打铁(实在是弱爆了),不过好歹有个牌牌能为简历加点分。当时没有项目经验,都在学校里面闷头学算法了,想学点实际可以用到的,当时跟同学谈论了一下linux系统编程的东东,后来就打算以这个为切入点,那时的确感觉挺高端的,况且大型的互联公司都会用到这些东西,所以暑假就将所有时间投入到了这个上面。我看的入门书是《linux程序设计》,过年时候除了年前年后的几天,基本上泡在图书馆,把书上重要章节的代码都敲了敲,这样,才算是对linux编程有了一定了解。
(更多…)

最长上升子序列nlogn算法

2013年08月22日,星期四

以前搞算法的时候看到过这个算法,但是没有仔细钻研过,似懂非懂,这两天看了看,总算是搞明白了。

问题的背景我就不多说了,相信通过搜索引擎来到这里的都是为了寻求简单易懂的nlogn的答案。

这个算法dp的状态有点诡异:

dp[i] = 长度为i+1的上升子序列中末尾元素的最小值(没有某个长度的上升自序列的话相应位置是无穷大)

初看有点不太明白,为什么是末尾的最小值呢?为什么可以求出最长的公共子序列呢?为什么可以到nlogn呢?别急,我慢慢说。

首先,当这个算法执行完毕的时候,dp数组中的每一个都符合我们定义的状态,每个长度的上升子序列末尾最小值都有了。那么我们看看含有末尾最小值的最大的位置是什么就能找到问题的解了。

其次,我们怎么去进行状态的推算和更新?其实,这个算法已经是优化过的算法,搞的人都不清楚他要干啥了。这个算法的原始版本其实还有一维(详见PSS),如果我们知道N个元素组成的dp数组,那么如果这时候又来了一个元素怎么办?dp数组能很快更新么?必须是可以的。只要新来的元素比dp数组中的某个位置j上的元素大就可以了,那么新来的元素就可以更新dp[j]了,具体是if(dp[j-1]<new)     dp[j] = min(dp[j],new),奉上代码:

for( int i = 0; i < n; i++ ){// index for arrays
    for( int j = 0; j < n; j++ )// index for dp
        if( j == 0 || (dp[j-1] < a[i] && a[i] < dp[j] ) )
            dp[j] = a[i];
}

上面简单的代码有个奇特的性质,就是每次循环完dp是单调递增的(除了无穷大),为什么呢,假如dp[3]>dp[5],长度为5的上升子序列的最后一位最小值竟然比长度为3的末尾最小值小,那我们拿长度为5的上升自序列的后面三个数更新dp[3]不就行了?

最后还有个性质,从上面代码的if语句中可以看出,因为dp是递增的,所以a[i]最多也就更新一次。不妨用二分找出更新的位置,然后复杂度就降到nlogn,你说优美不?

贴上《挑战程序设计竞赛》,65页的代码,大家好好品味

int dp[MAX_N];

void solve{
    fill( dp, dp + n, INF );
    for( int i = 0; i < n; i++ )
        *lower_bound( dp, dp + n, a[i] ) = a[i];
    printf("%d\n", lower_bound(dp,dp+n,INF) - dp );
}

什么?没看懂?再看一遍吧。。

PS:以上代码未经验证
PSS:原始算法什么的是我想出来的,为了使思维过程更清晰一点,具体有没有就不知道了
PSSS:有人知道最长不下降自序列可以用nlogn的算法解么?

编程珠玑 第四章 习题解答

2012年07月8日,星期日

1.为了保证范围不超过范围,我们需要在初始化的时候,让变量不超出范围。这样每次循环得到的新的范围是慢慢缩小的,不会越界。

2.迭代的二分查找。

int bs( int *a, int l, int r, int v ){
	while( l <= r ){
		if( a[l] == v ) return l;
		int mid = (l+r)/2;
		if( a[mid] < v ) l = mid+1;
		if( a[mid] == v )r = mid;
		if( a[mid] > v ) r = mid-1;
	}
	return -1;
}

这个二分可以返回所需要查询的元素第一次出现的位置,如果不存在,则返回-1.在每个循环内,我们假定元素第一次出现的范围是闭区间[l,r]内,当循环体内语句执行完之后,我们得到了一个新的区间。新的区间的范围是一直在收敛的(不会存在r,l执行完循环之后大小没有变化。),所以程序可以终止,得到正确结果。

3.将2的二分程序改写成递归的形式。

int bss( int *a, int l, int r, int v ){
	if( l > r ) return -1;
	if( a[l] == v ) return l;
	int mid = (l+r)/2;
	if( a[mid] < v ) return bss( a, mid+1, r, v );
	if( a[mid] == v )return bss( a, l, mid, v );
	if( a[mid] > v ) return bss( a, l, mid-1, v );
}

(更多…)

ZOJ 1503 One Person “The Price is Right”

2012年06月6日,星期三

好久没有做题了..刷刷DP吧,之前都没有好好做过这方面的题,比赛一遇到就放过..没有一点思路.

这是个比较基础的,还好是我自己想出来的,没有看hints.对于每对猜测次数G和生命值L,需要得到一个最大的N,让其可以找到一个策略,能在G和L都没用完前猜出正确的数,即必胜策略. 我们平时玩这种游戏的时候都是二分..然后从经验上判断这个是最快能猜到那个数的.这里因为有生命值,所以复杂了些.我们假设这个某对GL对应的最大的N为nmax,第一步我们的必胜策略肯定是从中间找一个数k,然后判断这个数是大了还是小了还是刚好. 如果没有猜中,就从左边或者右边的范围内继续查找.假设dp[i][j]表示当猜测次数是i,生命值是j的时候能得到的最大的N.

再来看k,如果k猜大了,那么生命值就减少了1.需要从小于k的范围内再猜,在小于k的范围内所能得到的最大N是dp[i-1][j-1],在大于k的范围内的到最大N是dp[i-1][j],所以可得dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1,这就是状态转移方程.

编程珠玑 第三章 习题解答

2012年06月3日,星期日

为什么我看完这一章不知道该写啥?。。整体来看是比较基础的。

1.if-else语句的每个分支的形式都差不多,我们可以用数组来使循环简单一点。数组中每个点表明一个阶段,用level[i]表示阶段i的起始点,tax[i]表示阶段i的税率,用have [i]表示这个阶段已经有的税收,然后得到收入后二分到相应的阶段,计算税收。

2.不知所云(用递归实现应该很简单,不用数组的话代码量会比较大)。

3.这个不会,看了答案了。这个方法的精髓就是把重复出现n次的字符用 n+‘字符’来表示,重复出现的行用同样的方法可以得到。这个方法给了我很大的启示,以前没有思路的一道题目,瞬间来了灵感。
(更多…)

编程珠玑 第二章 习题解答

2012年06月2日,星期六

这一章很奇葩啊。。书中B问题在一面的时候被问到,C在笔试的时候是第一大题(当时写了好多)。

1.在给定单词和字典的情况下,遍历字典,计算每个的标签,然后与给定的单词的标签比较。可以预处理的话就好说了,将所有单词按照标签排序,然后可以用equal_range求出区间,O(logN)。

2.可以类比如何找出没有出现的整数。43 0000 0000 大于int的表示范围。可以先扫面一遍,把第一位为0的和第一位为1的放到两个不同的文件中,看哪个文件里面的数多,就开始处理这个文件,把第二位的0和1的数字放到两个文件中,看哪个的数字多,依此类推,最后肯定得到一个数,他出现了不止一次。

3.我实现了两个算法。gao函数是那个杂技算法,gaogao是块交换算法。经过简单的测试还没有发现什么问题。n和len的最大公约数就是置换的次数。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int gcd( int a, int b ){
    return b==0?a:gcd(b, a%b);
}
int gao( int *start, int *end, int n ){
    int len = end - start;
    int d = gcd( n, len );
    for( int i = 0; i < d; i++ ){
        int t = *(start+i);
        int next = i;
        while( (next+n)%len != i ){
            *(start+next) = *(start+(next+n)%len);
            next = (next+n)%len;
        }
        *(start+next) = t;
    }
}

(更多…)

编程珠玑 第一章 习题解答

2012年05月21日,星期一
编程珠玑虽然说给了习题的题目和答案,而且也比较详尽,但是鉴于以前看书有答案的往往看的不是太仔细,以至于很多东西都没有搞清楚,所以我决定把习题都记录下来。这样有助于我研究题目,解决问题。
第一章简单来说就介绍了个用bitmap排序的实例,从思维上给了我们思考问题的另一个角度。
1.c语言的话可以用qsort,但是感觉qsort的比较函数的定义较为复杂,还是推荐用c++中的sort。

int main(void){
    vector v;
    for( int i = 0; i < 100; i++ )
        v.push_back( rand() );
    sort( v.begin(), v.end() );
    for( int i = 0; i < 100; i++ )
        cout << v[i] << endl;
    return 0;
}

(更多…)

一个简单的vector实现

2012年03月13日,星期二

学算法用的是《数据结构与算法分析(c++描述)》,里面有用c++实现算法和数据结构的,我看了看感觉不错,就把敲了出来。
ps:不是我写的,,基本是照抄的,不过倒是学到不少东西。

vector的特点就是可以动态的改变数组的大小,一般的vector应该是容量不够的时候扩展到2倍的容量,微软的实现应该是不够的时候扩展到1.5倍容量.
(更多…)

一个简单的list实现

2012年03月9日,星期五

此List仿照的时STL中的list 写的,完成了一些基本功能。学习时候时按照书上(数据结构与算法分析,c++描述)学习的,了解到了迭代器的基本实现,感觉很有成就感。List用双向链表实现的,这样就可以方便地对迭代器应用++,–操作符。链表中又添加了两个节点tail和head,这样在插入删除元素的时候在操作上就统一了。

虽然说写出来了,而且经过简单的测试,没有啥问题(当然,我没有做任何的错误处理。。),但是感觉这种接口与实现分离的写法实在是太麻烦了。以后考虑把这些接口都放到注释中去,然后再在实际代码中实现,这样就不用去写一堆的template<typename Object>了。

前两天学习了git的用法,准备把自己的代码放到github上面,repo名称为fkcode。有兴趣的可以watch me。放代码~

#include<iostream>
template<typename Object>
class List{
private:
	struct Node;	//存放节点信息
	int theSize;	//List包含的元素的个数
	Node *head,*tail; //当容器为空的时候,有两个节点

	void init();
public:
	class const_iterator; //const迭带器
	class iterator;			//迭带器

	List();//constructor
	List( const List & rhs );
	~List();
	const List & operator= (const List & rhs );
	//the "Big Three"

	//basic routines, easy to understand by name
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;

	int size() const;
	bool empty() const;
	void clear();

	Object & front();
	Object & back();
	const Object & front() const;
	const Object & back()  const;

	void push_front( const Object & x );
	void push_back(  const Object & x );
	void pop_front();
	void pop_back();

	iterator insert( iterator itr, const Object & x );
	iterator erase( iterator itr );
	iterator erase( iterator start, iterator end );

};

(更多…)