以前下Youtube的视频一般都是在嗅探URL的网站上嗅探出URL然后用下载器下载，今天在网上看见一个Chrome插件，可以直接下载Youtube的视频，还能选择分辨率，很不错，所以写个日志mark一下，怕以后找不到了。

地址在这里，貌似也支持FF。

安装完后，在Youtube视频的下面就会出现Download按钮，直接就能下了，相当方便。

至于怎么上YTB，这里就不说了。

Cydia里面的mobile terminal在iOS5下面没法用，因为版本太老了。其实作者已经更新了，但是不知道为什么cydia里面没有更新。

点这里下载新版的terminal，这是个deb包，然后用你喜欢的方式装就行了(ifile或者在拷进cydia的自动安装目录)。

参考自这里

首先引用一下《编程珠玑》中的两句话：

1. 尽管给了那么充裕的时间，只有大约10%的专业程序员能够写出正确的二分查找。
2. 尽管第一个二分查找程序于1946年就公布了，但是第一个没有bug的二分查找程序在1962年才出现。

当时看到这的时候，我觉得有点夸张。这里不去讨论是否真的花了20年才人们才写出正确的代码，但这两句话至少告诉我们，不要小看二分搜索。

确实，写过bsearch的人都知道，迭代的出口很难在短时间内想清楚（反正我经常糊涂）。当然，常规的二分搜索大家现在基本都能写了，(写过这么多次，背也背下来了)，但能写出来不代表真正理解了二分搜索。比如我今天在做一道题的时候就卡在了这里：从一个有序数组中找到大于x且最接近x的数。

说白了就是二分搜索，但是迭代的出口是什么？

先来看一下常规的二分查找的代码：

/* ---------------------------------------------------------------*/
/**
 * 函数简介: 有序数组中搜索指定元素
 *
 * 参数: a  数组指针
 * 参数: n  元素数目
 * 参数: x  要搜索的值
 *
 * 返回值:  若找到，返回该元素下标
 *          若找不到，返回-1
 */
/* ---------------------------------------------------------------*/
int bsearch(int *a, int n, int x)
{
	int m;
	int l = 0, r = n -1;

	while( r >= l )
	{
		m = (l+r)/2;
		if(a[m] == x)
			return m;
		else if(a[m] < x)
			l = m+1;
		else
			r = m-1;
	}
	return -1;

考虑一下要查找的元素不在序列中的情况：函数会返回-1，那l和r分别指向什么呢？

可以证明：l指向大于x的第一个元素，r指向小于x的第一个元素。(为什么？迭代的最后一步必然是l和r指向同一元素，然后为什么会变得比r大呢？想想就明白了)

既然得出了这个结论，那么代码就好写了，但是还得注意一些边界条件，比如最后返回的时候检查l和r是否越界，如果越界就说明找不到。

代码如下，如果有错，欢迎讨论：

/*=============================================================================
#     FileName: binary_search.cpp
#         Desc: 二分搜索及变形
#       Author: Ace
#        Email: goace@acm.org
#     HomePage: http://t.matong.me
#      Version: 0.0.1
#   LastChange: 2011-09-18 18:37:09
#      History:
=============================================================================*/
#include  
using namespace std;

/* ---------------------------------------------------------------*/
/**
 * 函数简介: 有序数组中搜索指定元素
 *
 * 参数: a  数组指针
 * 参数: n  元素数目
 * 参数: x  要搜索的值
 *
 * 返回值:  若找到，返回该元素下标
 *          若找不到，返回-1
 */
/* ---------------------------------------------------------------*/
int bsearch(int *a, int n, int x)
{
	int m;
	int l = 0, r = n -1;

	while( r >= l )
	{
		m = (l+r)/2;
		if(a[m] == x)
			return m;
		else if(a[m] < x)
			l = m+1;
		else
			r = m-1;
	}
	return -1;
}

/* ---------------------------------------------------------------*/
/**
 * 函数简介:  在有序数组中查找比x大但是最接近x的数
 *
 * 参数: a  数组指针
 * 参数: n  元素数目
 * 参数: x  要搜索的值
 *
 * 返回值:  若找到，返回该元素下标
 *          若找不到，返回-1
 */
/* ---------------------------------------------------------------*/
int bsearch_more(int *a,int n, int x)
{
	int m;
	int l = 0, r = n -1;

	while( r >= l )
	{
		m = (l+r)/2;
		
		if(a[m] == x)
			return ( (m+1) >= n ? -1 : (m+1) );
		else if(a[m] < x)
			l = m+1;
		else
			r = m-1;
	}
	l = (l >= n ? -1 : l);
	return l;
}

/* ---------------------------------------------------------------*/
/**
 * 函数简介:  在有序数组中查找比x小但是最接近x的数
 *
 * 参数: a  数组指针
 * 参数: n  元素数目
 * 参数: x  要搜索的值
 *
 * 返回值:  若找到，返回该元素下标
 *          若找不到，返回-1
 */
/* ---------------------------------------------------------------*/
int bsearch_less(int *a,int n, int x)
{
	int m;
	int l = 0, r = n -1;

	while( r >= l )
	{
		m = (l+r)/2;
		if(a[m] == x)
			return ( (m-1) < 0 ? -1 : (m-1) );
		else if(a[m] < x)
			l = m+1;
		else
			r = m-1;
	}
	return r;
}

int main(int argc, char *argv[])
{
	int x;
	int arr[] = {8, 17, 26, 32, 40, 72, 87, 99};
	while(cin >> x)
	cout << bsearch_less(arr,8,x)+1 
		<< " "
		<< bsearch_more(arr,8,x)+1<< endl;
}

刚才做完POJ1191(棋盘分割)后，发现这题中的一个小技巧可以衍生出一道蛮好的面试题，题目如下：

给定一个n*m个数字的矩阵，后跟k组查询Qi = [(x1,y1),(x2,y2)] (i = 0 ~ k)，(x1,y1),(x2,y2)分别表示矩形的左上角和右下角坐标，对每个查询，输出由这两点确定的子矩阵的元素和。

最简单的方法就是对每个查询都遍历矩阵求和，这样的复杂度是O(kmn)，k如果很大的话，这个效率是无法接受的。

下面这个方法可以在O(m*n)的预处理后，用O(1)时间求解每组查询：

我们用sum(i,j)表示左上角是(0,0),右下角是(i,j)的子矩阵的和，那么[(x1,y1),(x2,y2)] = sum(x2,y2) - sum(x1,y2) - sum(x2,y1) + sum(x1,y1)。如果每个sum(i,j)都已知，那么就能在常数时间求出每组查询的结果。

计算每个sum(i,j)可以这样: sum(i,j) = sum(i-1,j) + sum(i,j-1) - sum(i-1,j-1) + matrix(i,j)

因此，只需要一轮O(m*n)的迭代即可完成预处理。

update1: 用这个思想可以直接过hdu1559.

[题意] 用最少的圆覆盖所有的点

[分类] 贪心

[思路] 先对每个点算出能覆盖自己的雷达的放置区间，然后按左端点升序排序所有区间。把包含别的小区间的大区间去掉，比如[1,9]，和[2,6]，因为[1,9]完全包含[2,6]，所以如果满足后者，一定满足前者，因此去掉多余的[1,9]。去掉所有包含小区间的大区间后，从左到右扫描，如果该区间还没有被前面的雷达包括，就在这个区间的右端点放个雷达，依次类推。

[代码]

#include  
#include  
#include  
#include  
using namespace std;

typedef struct point
{
	int x,y;
}P;

typedef struct range
{
	bool exist;
	double l,r;
}R;

P points[1001];
R ranges[1001];

bool mycmp(const R &a,const R &b)
{
	return a.l < b.l;
}

int main(int argc, char *argv[])
{
	int n,d,sum,counter = 0;;
	bool flag;
	double r;
	double px;
	while( scanf("%d%d",&n,&d) && n!=0 )
	{
		printf("Case %d: ",++counter);
		sum = 0;
		flag = true;
		int i = 0;
		while(i < n)
		{
			scanf("%d%d",&(points[i].x),&(points[i].y));
			if(points[i].y > d || points[i].y < 0)
				flag = false;
			r = sqrt(d*d - points[i].y * points[i].y);
			ranges[i].l = points[i].x - r;
			ranges[i].r = points[i].x + r;
			ranges[i].exist = true;
			i++;
		}
		if(!flag)
			printf("-1\n");
		else
		{
			sort(ranges,ranges+n,mycmp);
			for(int i = 0; i < n - 1; ++i)
			{
				for(int j = i+1; j < n; ++j)
				{
					if(ranges[i].r <= ranges[j].l)
						break;
					if(ranges[i].r >= ranges[j].r)
					{
						ranges[i].exist = false;
						break;
					}
				}
			}
			
			for( int i = 0; i < n ; ++i )
			{
				if(ranges[i].exist == false)
					continue;
				if(sum == 0)
				{
					px = ranges[i].r;
					sum++;
				}
				else
				{
					if(px >= ranges[i].l && px <= ranges[i].r)
						continue;
					else
					{
						px = ranges[i].r;
						sum++;
					}
				}
			}
			printf("%d\n",sum);
			
		}
	}
}

月光博客6月12日发表了《写给新手程序员的一封信》，翻译自《An open letter to those who want to start programming》，我的朋友（他在本站的id是Mailper）告诉我，他希望在酷壳上看到一篇更具操作性的文章。因为他也是喜欢编程和技术的家伙，于是，我让他把他的一些学习Python和Web编程的一些点滴总结一下。于是他给我发来了一些他的心得和经历，我在把他的心得做了不多的增改，并根据我的经历增加了“进阶”一节。这是一篇由新手和我这个老家伙根据我们的经历完成的文章。

我的这个朋友把这篇文章取名叫Build Your Programming Technical Skills，我实在不知道用中文怎么翻译，但我在写的过程中，我觉得这很像一个打网游做任务升级的一个过程，所以取名叫“技术练级攻略”，题目有点大，呵呵，这个标题纯粹是为了好玩。这里仅仅是在分享Mailper和我个人的学习经历。（注：省去了我作为一个初学者曾经学习过的一些技术(今天明显过时了)，如：Delphi/Power builder，也省去了我学过的一些我觉得没意思的技术Lotus Notes/ActiveX/COM/ADO/ATL/.NET ……）

前言

你是否觉得自己从学校毕业的时候只做过小玩具一样的程序？走入职场后哪怕没有什么经验也可以把以下这些课外练习走一遍（朋友的抱怨：学校课程总是从理论出发，作业项目都看不出有什么实际作用，不如从工作中的需求出发）

建议：

• 不要乱买书，不要乱追新技术新名词，基础的东西经过很长时间积累而且还会在未来至少10年通用。
• 回顾一下历史，看看历史上时间线上技术的发展，你才能明白明天会是什么样。
• 一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
• 一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考。

注：你也许会很奇怪为什么下面的东西很偏Unix/Linux，这是因为我觉得Windows下的编程可能会在未来很没有前途，原因如下：

• 现在的用户界面几乎被两个东西主宰了，1）Web，2）移动设备iOS或Android。Windows的图形界面不吃香了。
• 越来越多的企业在用成本低性能高的Linux和各种开源技术来构架其系统，Windows的成本太高了。
• 微软的东西变得太快了，很不持久，他们完全是在玩弄程序员。详情参见《Windows编程革命史》

所以，我个人认为以后的趋势是前端是Web+移动，后端是Linux+开源。开发这边基本上没Windows什么事。

启蒙入门

1、 学习一门脚本语言，例如Python/Ruby

可以让你摆脱对底层语言的恐惧感，脚本语言可以让你很快开发出能用得上的小程序。实践项目:

• 处理文本文件，或者csv (关键词 python csv, python open, python sys) 读一个本地文件，逐行处理（例如 word count，或者处理log）
• 遍历本地文件系统 (sys, os, path)，例如写一个程序统计一个目录下所有文件大小并按各种条件排序并保存结果
• 跟数据库打交道 (python sqlite)，写一个小脚本统计数据库里条目数量
• 学会用各种print之类简单粗暴的方式进行调试
• 学会用Google (phrase, domain, use reader to follow tech blogs)

为什么要学脚本语言，因为他们实在是太方便了，很多时候我们需要写点小工具或是脚本来帮我们解决问题，你就会发现正规的编程语言太难用了。

2、 用熟一种程序员的编辑器(不是IDE) 和一些基本工具

• Vim / Emacs / Notepad++，学会如何配置代码补全，外观，外部命令等。
• Source Insight (或 ctag)

使用这些东西不是为了Cool，而是这些编辑器在查看、修改代码/配置文章/日志会更快更有效率。

3、 熟悉Unix/Linux Shell和常见的命令行

• 如果你用windows，至少学会用虚拟机里的linux， vmware player是免费的，装个Ubuntu吧
• 一定要少用少用图形界面。
• 学会使用man来查看帮助
• 文件系统结构和基本操作 ls/chmod/chown/rm/find/ln/cat/mount/mkdir/tar/gzip …
• 学会使用一些文本操作命令 sed/awk/grep/tail/less/more …
• 学会使用一些管理命令 ps/top/lsof/netstat/kill/tcpdump/iptables/dd…
• 了解/etc目录下的各种配置文章，学会查看/var/log下的系统日志，以及/proc下的系统运行信息
• 了解正则表达式，使用正则表达式来查找文件。

对于程序员来说Unix/Linux比Windows简单多了。（参看我四年前CSDN的博文《其实Unix很简单》）学会使用Unix/Linux你会发现图形界面在某些时候实在是太难用了，相当地相当地降低工作效率。

4、 学习Web基础（HTML/CSS/JS) + 服务器端技术 (LAMP)

未来必然是Web的世界，学习WEB基础的最佳网站是W3School。

• 学习HTML基本语法
• 学习CSS如何选中HTML元素并应用一些基本样式（关键词：box model）
• 学会用  Firefox + Firebug 或 chrome 查看你觉得很炫的网页结构，并动态修改。
• 学习使用Javascript操纵HTML元件。理解DOM和动态网页（http://oreilly.com/catalog/9780596527402) 网上有免费的章节，足够用了。或参看 DOM 。
• 学会用  Firefox + Firebug 或 chrome 调试Javascript代码（设置断点，查看变量，性能，控制台等）
• 在一台机器上配置Apache 或 Nginx
• 学习PHP，让后台PHP和前台HTML进行数据交互，对服务器相应浏览器请求形成初步认识。实现一个表单提交和反显的功能。
• 把PHP连接本地或者远程数据库 MySQL（MySQL 和 SQL现学现用够了）
• 跟完一个名校的网络编程课程（例如：http://www.stanford.edu/~ouster/cgi-bin/cs142-fall10/index.php ) 不要觉得需要多于一学期时间，大学生是全职一学期选3-5门课，你业余时间一定可以跟上
• 学习一个javascript库（例如jQuery 或 ExtJS）+  Ajax (异步读入一个服务器端图片或者数据库内容）+JSON数据格式。
• HTTP: The Definitive Guide 读完前4章你就明白你每天上网用浏览器的时候发生的事情了(proxy, gateway, browsers)
• 做个小网站（例如：一个小的留言板，支持用户登录，Cookie/Session，增、删、改、查，上传图片附件，分页显示）
• 买个域名，租个空间，做个自己的网站。

进阶加深

1、 C语言和操作系统调用

• 重新学C语言，理解指针和内存模型，用C语言实现一下各种经典的算法和数据结构。推荐《计算机程序设计艺术》、《算法导论》和《编程珠玑》。
• 学习（麻省理工免费课程）计算机科学和编程导论
• 学习（麻省理工免费课程）C语言内存管理
• 学习Unix/Linux系统调用（Unix高级环境编程），，了解系统层面的东西。
• 用这些系统知识操作一下文件系统，用户（实现一个可以拷贝目录树的小程序）
• 用fork/wait/waitpid写一个多进程的程序，用pthread写一个多线程带同步或互斥的程序。多进程多进程购票的程序。
• 用signal/kill/raise/alarm/pause/sigprocmask实现一个多进程间的信号量通信的程序。
• 学会使用gcc和gdb来编程和调试程序（参看我的《用gdb调试程序》）
• 学会使用makefile来编译程序。（参看我的《跟我一起写makefile》）
• IPC和Socket的东西可以放到高级中来实践。
• 学习Windows SDK编程（Windows 程序设计 ，MFC程序设计）
• 写一个窗口，了解WinMain/WinProcedure，以及Windows的消息机制。
• 写一些程序来操作Windows SDK中的资源文件或是各种图形控件，以及作图的编程。
• 学习如何使用MSDN查看相关的SDK函数，各种WM_消息以及一些例程。
• 这本书中有很多例程，在实践中请不要照抄，试着自己写一个自己的例程。
• 不用太多于精通这些东西，因为GUI正在被Web取代，主要是了解一下Windows 图形界面的编程。@virushuo 说：“ 我觉得GUI确实不那么热门了，但充分理解GUI工作原理是很重要的。包括移动设备开发，如果没有基础知识仍然很吃力。或者说移动设备开发必须理解GUI工作，或者在win那边学，或者在mac/iOS上学”。

2、学习Java

• Java 的学习主要是看经典的Core Java 《Java 核心技术编程》和《Java编程思想》（有两卷，我仅链了第一卷，足够了，因为Java的图形界面了解就可以了）
• 学习JDK，学会查阅Java API Doc http://download.oracle.com/javase/6/docs/api/
• 了解一下Java这种虚拟机语言和C和Python语言在编译和执行上的差别。从C、Java、Python思考一下“跨平台”这种技术。
• 学会使用IDE Eclipse，使用Eclipse 编译，调试和开发Java程序。
• 建一个Tomcat的网站，尝试一下JSP/Servlet/JDBC/MySQL的Web开发。把前面所说的那个PHP的小项目试着用JSP和Servlet实现一下。

4、学习关系型数据库

• 你可以安装MSSQLServer或MySQL来学习数据库。
• 学习教科书里数据库设计的那几个范式，1NF，2NF，3NF，……
• 学习数据库的存过，触发器，视图，建索引，游标等。
• 学习SQL语句，明白表连接的各种概念（参看《SQL  Join的图示》）
• 学习如何优化数据库查询（参看《MySQL的优化》）
• 实践任务：设计一个论坛的数据库，至少满足3NF，使用SQL语句查询本周，本月的最新文章，评论最多的文章，最活跃用户。

5、一些开发工具

• 学会使用SVN或Git来管理程序版本。
• 学会使用JUnit来对Java进行单元测试。
• 学习C语言和Java语言的coding standard 或 coding guideline。（我N年前写过一篇关C语言非常简单的文章——《编程修养》，这样的东西你可以上网查一下，一大堆）。
• 推荐阅读《代码大全》《重构》《代码整洁之道》

高级深入

1、C++ / Java 和面向对象

我个人以为学好C++，Java也就是举手之劳。但是C++的学习曲线相当的陡。不过，我觉得C++是最需要学好的语言了。参看两篇趣文“C++学习信心图” 和“21天学好C++”

• 学习（麻省理工免费课程）C++面向对象编程
• 读我的 “如何学好C++”中所推荐的那些书至少两遍以上（如果你对C++的理解能够深入到像我所写的《C++虚函数表解析》或是《C++对象内存存局（上）（下）》，或是《C/C++返回内部静态成员的陷阱》那就非常不错了）
• 然后反思为什么C++要干成这样，Java则不是？你一定要学会对比C++和Java的不同。比如，Java中的初始化，垃圾回收，接口，异常，虚函数，等等。
• 实践任务：
• 用C++实现一个BigInt，支持128位的整形的加减乘除的操作。
• 用C++封装一个数据结构的容量，比如hash table。
• 用C++封装并实现一个智能指针（一定要使用模板）。
• 《设计模式》必需一读，两遍以上，思考一下，这23个模式的应用场景。主要是两点：1）钟爱组合而不是继承，2）钟爱接口而不是实现。（也推荐《深入浅出设计模式》）
• 实践任务：
• 使用工厂模式实现一个内存池。
• 使用策略模式制做一个类其可以把文本文件进行左对齐，右对齐和中对齐。
• 使用命令模式实现一个命令行计算器，并支持undo和redo。
• 使用修饰模式实现一个酒店的房间价格订价策略——旺季，服务，VIP、旅行团、等影响价格的因素。
• 学习STL的用法和其设计概念  - 容器，算法，迭代器，函数子。如果可能，请读一下其源码。
• 实践任务：尝试使用面向对象、STL，设计模式、和WindowsSDK图形编程的各种技能
• 做一个贪吃蛇或是俄罗斯方块的游戏。支持不同的级别和难度。
• 做一个文件浏览器，可以浏览目录下的文件，并可以对不同的文件有不同的操作，文本文件可以打开编辑，执行文件则执行之，mp3或avi文件可以播放，图片文件可以展示图片。
• 学习C++的一些类库的设计，如： MFC（看看候捷老师的《深入浅出MFC》） ，Boost, ACE,  CPPUnit，STL （STL可能会太难了，但是如果你能了解其中的设计模式和设计那就太好了，如果你能深入到我写的《STL string类的写时拷贝技术》那就非常不错了，ACE需要很强在的系统知识，参见后面的“加强对系统的了解”）
• Java是真正的面向对象的语言，Java的设计模式多得不能再多，也是用来学习面向对象的设计模式的最佳语言了（参看Java中的设计模式）。
• 推荐阅读《Effective Java》 and 《Java解惑》
• 学习Java的框架，Java的框架也是多，如Spring, Hibernate，Struts 等等，主要是学习Java的设计，如IoC等。
• Java的技术也是烂多，重点学习J2EE架构以及JMS， RMI, 等消息传递和远程调用的技术。
• 学习使用Java做Web Service （官方教程在这里）
• 实践任务： 尝试在Spring或Hibernate框架下构建一个有网络的Web Service的远程调用程序，并可以在两个Service中通过JMS传递消息。

C++和Java都不是能在短时间内能学好的，C++玩是的深，Java玩的是广，我建议两者选一个。我个人的学习经历是：

• 深究C++（我深究C/C++了十来年了）
• 学习Java的各种设计模式。

2、加强系统了解

重要阅读下面的几本书：

• 《Unix编程艺术》了解Unix系统领域中的设计和开发哲学、思想文化体系、原则与经验。你一定会有一种醍醐灌顶的感觉。
• 《Unix网络编程卷1，套接字》这是一本看完你就明白网络编程的书。重要注意TCP、UDP，以及多路复用的系统调用select/poll/epoll的差别。
• 《TCP/IP详解 卷1:协议》- 这是一本看完后你就可以当网络黑客的书。了解以太网的的运作原理，了解TCP/IP的协议，运作原理以及如何TCP的调优。
• 实践任务：
• 理解什么是阻塞（同步IO），非阻塞（异步IO），多路复用（select, poll, epoll）的IO技术。
• 写一个网络聊天程序，有聊天服务器和多个聊天客户端（服务端用UDP对部分或所有的的聊天客户端进Multicast或Broadcast）。
• 写一个简易的HTTP服务器。
• 《Unix网络编程卷2，进程间通信》信号量，管道，共享内存，消息等各种IPC…… 这些技术好像有点老掉牙了，不过还是值得了解。
• 实践任务：
• 主要实践各种IPC进程序通信的方法。
• 尝试写一个管道程序，父子进程通过管道交换数据。
• 尝试写一个共享内存的程序，两个进程通过共享内存交换一个C的结构体数组。
• 学习《Windows核心编程》一书。把CreateProcess，Windows线程、线程调度、线程同步（Event,  信号量，互斥量）、异步I/O，内存管理，DLL，这几大块搞精通。
• 实践任务：使用CreateProcess启动一个记事本或IE，并监控该程序的运行。把前面写过的那个简易的HTTP服务用线程池实现一下。写一个DLL的钩子程序监控指定窗口的关闭事件，或是记录某个窗口的按键。
• 有了多线程、多进程通信，TCP/IP，套接字，C++和设计模式的基本，你可以研究一下ACE了。使用ACE重写上述的聊天程序和HTTP服务器（带线程池）
• 实践任务：通过以上的所有知识，尝试
• 写一个服务端给客户端传大文件，要求把100M的带宽用到80%以上。（注意，磁盘I/O和网络I/O可能会很有问题，想一想怎么解决，另外，请注意网络传输最大单元MTU）
• 了解BT下载的工作原理，用多进程的方式模拟BT下载的原理。

3、系统架构

• 负载均衡。HASH式的，纯动态式的。（可以到Google学术里搜一些关于负载均衡的文章读读）
• 多层分布式系统 – 客户端服务结点层、计算结点层、数据cache层，数据层。J2EE是经典的多层结构。
• CDN系统 – 就近访问，内容边缘化。
• P2P式系统，研究一下BT和电驴的算法。比如：DHT算法。
• 服务器备份，双机备份系统（Live-Standby和Live-Live系统），两台机器如何通过心跳监测对方？集群主结点备份。
• 虚拟化技术，使用这个技术，可以把操作系统当应用程序一下切换或重新配置和部署。
• 学习Thrift，二进制的高性能的通讯中间件，支持数据(对象)序列化和多种类型的RPC服务。
• 学习Hadoop。Hadoop框架中最核心的设计就是：MapReduce和HDFS。MapReduce的思想是由Google的一篇论文所提及而被广为流传的，简单的一句话解释MapReduce就是“任务的分解与结果的汇总”。HDFS是Hadoop分布式文件系统（Hadoop Distributed File System）的缩写，为分布式计算存储提供了底层支持。
• 了解NoSQL数据库（有人说可能是一个过渡炒作的技术），不过因为超大规模以及高并发的纯动态型网站日渐成为主流，而SNS类网站在数据存取过程中有着实时性等刚性需求，这使得目前NoSQL数据库慢慢成了人们所关注的焦点，并大有成为取代关系型数据库而成为未来主流数据存储模式的趋势。当前NoSQL数据库很多，大部分都是开源的，其中比较知名的有：MemcacheDB、Redis、Tokyo Cabinet(升级版为Kyoto Cabinet)、Flare、MongoDB、CouchDB、Cassandra、Voldemort等。

写了那么多，回顾一下，觉得自己相当的有成就感。希望大家不要吓着，我自己这十来年也在不断地学习，今天我也在学习中，人生本来就是一个不断学习和练级的过程。不过，一定有漏的，也有不对的，还希望大家补充和更正。（我会根据大家的反馈随时更新此文）欢迎大家通过我的微博（@左耳朵耗子）和twitter（@haoel）和我交流。

—– 更新  2011/07/19 —–

1）有朋友奇怪为什么我在这篇文章开头说了web+移动，却没有在后面提到iOS/Android的前端开发。因为我心里有一种感觉，移动设备上的UI最终也会被Javascript取代。大家可以用iPhone或Android看看google+，你就会明白了。

2）有朋友说我这里的东西太多了，不能为了学习而学习，我非常同意。我在文章的前面也说了要思考。另外，千万不要以为我说的这些东西是一些新的技术，这份攻略里95%以上的全是基础。而且都是久经考验的基础技术。即是可以让你一通百通的技术，也是可以让你找到一份不错工作的技术。

3）有朋友说学这些东西学完都40了，还不如想想怎么去挣钱。我想告诉大家，一是我今年还没有40岁，二是学无止境啊，三是我不觉得挣钱有多难，难的是怎么让你值那么多钱？无论是打工还是创业，是什么东西让你自己的价值，让你公司的价值更值钱？别的地方我不敢说，对于互联网或IT公司来说，技术实力绝对是其中之一。

4）有朋友说技术都是工具，不应该如此痴迷这句话没有错，有时候我们需要更多的是抬起头来看看技术以外的事情，或者是说我们在作技术的时候不去思考为什么会有这个技术，为什么不是别的，问题不在于技术，问题在于我们死读书，读死书，成了技术的书呆子。

5） 对于NoSQL，最近比较火，但我对其有点保守，所以，我只是说了解就可以。对于Hadoop，我觉得其在分布式系统上有巨大的潜力，所以需要学习。 对于关系型数据库，的确是很重要的东西，这点是我的疏忽，在原文里补充。

转自 酷壳

一直以为VLSM和CIDR是同一个意思，不就是把ABC类固定长度的掩码改成变长的了吗？今天仔细查了一下，两者还是有区别的

可变长度子网掩码 (VLSM) ：VLSM提出供了在一个主类(A、B、C类)网络内包含多个子网掩码的能力，以及对一个子网的再进行子网划分的能力。它的优点如下： 对IP地址更为有效的使用-如果不采用VLSM，公司将被限制为在一个A、B、C类网络号内只能使用一个子网掩码； 就用路由归纳的能力更强-VLSM允许在编址计划中有更多的体系分层，因此可以在路由表内进行更好的路由归纳。 

无类别域间路由（CIDR）：CIDR是开发用于帮助减缓IP地址和路由表增大问题的一项技术。CIDR的理念是多个C类地址块可以被组合或聚合在一起生成更大的无类别I P地址集（也就是说允许有更多的主机）。成块的C类地址是分配给各个ISP的。

CIDR，是将路由表中的条目汇总，如将多个C类地址汇总为一个B类地址。VLSM，是将一个网划分为多个子网，充分利用网络资源。简单直观的说就是，vlsm 是把一个ip分成几个连续的ip网段；cidr 是把几个ip地址合并成一个ip在外网显示。

转自百度知道

VLSM可变长子网掩码

　　VLSM(Variable Length Subnet Mask 可变长子网掩码)，这是一种产生不同大小子网的网络分配机制，指一个网络可以配置不同的掩码。开发可变长度子网掩码的想法就是在每个子网上保留足够的主机数的同时，把一个网分成多个子网时有更大的灵活性。如果没有VLSM，一个子网掩码只能提供给一个网络。这样就限制了要求的子网数上的主机数。

　　VLSM技术对高效分配IP地址(较少浪费)以及减少路由表大小都起到非常重要的作用。但是需要注意的是使用VLSM时，所采用的路由协议必须能够支持它，这些路由协议包括RIP2，OSPF，EIGRP和BGP。

CIDR无类别编址

　　1992年引入了CIDR，它意味着在路由表层次的网络地址“类”的概念已经被取消，代之以“网络前缀”的概念。Internet中的CIDR Classless Inter-Domain Routing 无类别域间路由 的基本思想是取消地址的分类结构，取而代之的是允许以可变长分界的方式分配网络数。它支持路由聚合，可限制Internet主干路由器中必要路由信息的增长。IP地址中A类已经分配完毕，B类也已经差不多了 剩下的C类地址已经成为大家瓜分的目标。显然 对于一个国家、地区、组织来说分配到的地址最好是连续的 那么如何来保证这一点呢？于是提出了CIDR的概念。CIDR是Classless Inter Domain Routing的缩写 意为无类别的域间路由。“无类别”的意思是现在的选路决策是基于整个32位IP地址的掩码操作。而不管其IP地址是A类、B类或是C类，都没有什么区别。它的思想是：把许多C类地址合起来作B类地址分配。采用这种分配多个IP地址的方式，使其能够将路由表中的许多表项归并 summarization 成更少的数目。

区别

以前总以为没有区别，因为都是为节约IP地址而设计的，

其实他们是有很大区别的

CIDR是把几个标准网络合成一个大的网络

VLSM是把一个标准网络分成几个小型网络（子网）

CIDR是子网掩码往左边移了，VLSM是子网掩码往右边移了

CIDR（Classless Inter.Domain Routing 无类别域间路由）

VLSM（Variable Length Subnetwork Mask     可变长子网掩码）

转自这里

[题意] 在一条单向公路上，有n个村庄，第i个村庄只能到i以后的村庄，而不能到i之前的村庄(因为是单行道)。新村长要建两条新路，使得各个村庄之间都能走通(一条反向的就可以，为什么要建两条？题目说了，只建一条不足矣增加自己的政绩，哎。。PARTY啊)。

[分类] 水

[思路] 找出所有路段中最短的，加上原来的总长，就是答案。有一点要注意，题目说两条路的4个端点必须不同，因此要排除端点重合的问题(我就是因为没看见那句话，WA了好几次)。另外，n=2和n=3是无解的。

[代码]

#include  
#include  

int main(int argc, char *argv[])
{
	int n;
	int pre,d,x,sum = 0,min = INT_MAX;
	scanf("%d",&n);
	for( int i = 1; i < n ; ++i )
	{
		scanf("%d",&d);
		int dif = d - sum;
		sum = d;
		if(i != 1 && i != n-1 && dif < min)
		{
			min = dif;
			x = i;
		}
	}
	if( n < 4)
	{
		printf("0\n");
		return 0;
	}
	printf("%d\n",sum+min);
	printf("%d %d %d %d\n",x+1,1,n,x);
}

[题意] 给定一个N＊N的矩阵，给出多组查询，每组查询指定一个子正方形矩阵，输出每个子矩阵中最大数与最小数的差。

[分类] DP

[思路] 这题可以用的普通的方法直接过，即对每次查询，线性扫描一次，我用的800MS过的。实际上，这是一个2维的RMQ问题。得到矩阵后，先对每一行用ST算法预处理，然后针对每一次查询，得到各行的最值，再从这几个最值中算出最值，总的复杂度是预处理O(nlgn)，每次查询O(b)。用这个方法，200MS可以过。

[代码]

#include  

int n,b,k;
int a[260][260];
int _min[260][260][8],_max[260][260][8];

int max(int x, int y)
{
	return x > y ? x : y;
}

int min(int x, int y)
{
	return x < y ? x : y;
}

void init()
{
	for( int i = 0; i < 260 ; ++i )
		for(int j = 0; j < 260; ++j)
			for( int m = 0; m < 8 ; ++m )
			{
				_max[i][j][m] = -1;
				_min[i][j][m] = -1;
			}
}

int get_min(int x, int y)
{
	int getm(int);
	int res = 251;
	int m = getm(b);

	for( int i = x; i < x+b  ; ++i )
		res = min(res,min(_min[i][y][m],_min[i][y + b - (1 <<  m)][m]));	
	
	return res;
}

int get_max(int x, int y)
{
	int getm(int);
	int res = -1;
	int m = getm(b);

	for( int i = x; i < x+b  ; ++i )
		res = max(res,max(_max[i][y][m],_max[i][y + b - (1 <<  m)][m]));	
	return res;
}

int getm(int x)
{
	int sum = 0;
	while(x >>= 1 != 0) sum++;
	return sum;
}

void search(int i, int j, int m)
{
	if( _max[i][j][m] != -1)
		return;
	if( m == 0)
	{
		_max[i][j][m] = _min[i][j][m] = a[i][j];
		return;
	}

	search(i,j,m-1);
	search(i,j + (1 << (m-1) ), m-1);
	_max[i][j][m] = max( _max[i][j][m-1], _max[i][j+(1 << (m-1)) ][m-1] );
    _min[i][j][m] = min( _min[i][j][m-1], _min[i][j+(1 << (m-1)) ][m-1] );
	return;
}

void process()
{
	for( int i = 1; i <= n ; ++i )
	{
		int m = getm(n);
		for( int j = 1; j <=n ; ++j )
		{
			if(j + (1 << m) -1 > n)
				m--;
			search(i,j,m);
		}
	}
}

int main(int argc, char *argv[])
{
	init();
	scanf("%d%d%d",&n,&b,&k);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			scanf("%d",&a[i][j]);

	process();
	int x,y;
	for( int i = 0; i < k ; ++i )
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",get_max(x,y) - get_min(x,y));
	}
}

昨天做POJ2019的时候，一开始直接暴力过了，800MS，看discuss里说这是RMQ问题，可以用DP过。

之前没听说过RMQ问题，于是上网学习了一下，总结如下：

一、什么是RMQ问题

RMQ是Range Minimum Query的缩写，是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小值下标。以下是一个例子：

         对数列：5,8,1,3,6,4,9,5,7 有：
         RMQ(2,4)=3 ， RMQ(6,9)=6 。

二、RMQ问题的解法

最常规的方法就是O(n)线性扫描了，但是如果查询的量很大的话(比如有1亿组查询)，这个效率显然是不行的。RMQ问题目前公认比较好的算法叫ST算法，即Sparse Table - 稀疏表算法(不知道为什么这么取名 - -|||)。此算法通过O(nlgn)的时间进行预处理，然后每个查询只需要O(1)就可以出结果。

算法描述如下(以最大值为例)：

定义状态 f(i,m) : 从第i个数开始连续的2^m个数字中的最大值。 要求f(i,m)，可以把这串数字平分两半，每半2^(m-1)个数，先求出左右两半各自的最大值，两者取大者，就是f(i,m)的解。于是状态转移方程就出来了 : f(i,m) = max ( f(i,m-1) , f(i + 2^(m-1),m-1) )。 那递归的出口呢？很明显，当m=0的时候，f(i,m)等于第i个数。

对每个数，都要求出所有的f(i,m)，有一点要注意，实现的时候要注意m是否太大，即i+2^(m-1)不能越界，所以对每个数来说，m的最大值是不一样的，这个要判断一下。

那么如果在O(1)时间内求出结果呢？比如查询RMQ(i,j)，我们可以把i到j这一串数字分成两串，每一串都有2^m个数，m满足2^m < n && 2^(m+1) > n(n是数组长度)，大家会发现，这么分出来的两段，中间是有重跌的，没关系，只要求出max(f(i,m), f(i+2^m, m))，就是问题的解，当中有重复部分不影响结果。

以上就是ST算法的整体思想，大家如果在实现方面有问题，欢迎留言。

PS:今天下午上课程设计的时候花了1个多小时用ST算法重写了POJ2019，200MS过了～果然很快