残阳似血的博客

Update：如果想了解更多第三方帐号登录，请看这篇文章。

随着新浪微博用户日益增加，我们有时候会考虑在自己的网站中整合新浪微博。比如说我现在的独立博客。

在我的博客中做到整合主要就这几方面：我写一篇文章，就会同步发送至微博。同时呢，用户可以用微博帐号登录，并且可以选择把对文章的评论，同步评论到文章的微博。另外，用户可以选择是否把博客留言同步至新浪微博。

新浪微博开放平台地址在这里。文档地址在这里。

首先要涉及的问题，就是用户用新浪微博帐号登录的问题，即授权机制。基本方法有两种：

1. OAuth
2. Basic auth（需要强调的是，微博开放平台将于6月1日正式停止Basic Auth的支持。因此，此种方法不作讨论了，其实需要用户名和密码的方式本身就不安全。）

OAuth新浪官方的文档在这里。想要了解OAuth技术说明的可以访问官方网站。

其实，OAuth的流程还是很简单的。大致如下：

1. 向API调用获得request token。
2. 将用户重定向到授权页(auth url）。
3. 用户输入用户名和密码完成授权。重定向到Callback_url。
4. 用request token向新浪微博换取access token。
5. 完成。

我们今天要讨论的问题大意是：给定一个数n，判断是否存在一个数m，使得：n == ∑i!（这里共m个不同整数）。（n≤1000000)

说白了其实就是：给定一个数n，看看这个数能不能表示成从m个不同整数阶乘的和。

刚拿到题目可能没有思路。仔细考虑可以注意到，n的最大值为1000000，小于32位机器上的int型的最大值（2^31-1），最先可能想到的是枚举法，由于10!>1000000，所以可能出现的0-9这几个数，每个数都有出现或者不出现两种情况，如果枚举将会有2^10共1024种情况，这个数量也不小。这就意味着需要换个思路来考虑。

注意到，对于一个整数k（k>1），0! + 1! + ... + (k-1)! < k!（左边 < k * (k-1)! == k!），因此，我们可以得出结论，对于一个数n，假设一个数j，使得j! ≤ n 且 (j+1)! > n，那么n分解成阶乘和的数中必定包含j!，用反证法证明，假设不包含，由之前的结论，小于j的所有数的阶乘和都小于j!，当然也必小于n。因此，当n = n - j!后，再判断n是否等于新的j!，等于证明分解成功；否则就减去新的j!，并循环判断。

于是，我们很容易得出以下代码。

public final static int count = 10;
	
public static int[] Facs(){
	int temp = 1;
	int[] facs = new int[count];
		
	for(int i=0; i<count; i++){
		if(i != 0)
			temp = temp * i;
		facs[i] = temp;
	}
		
	return facs;
}
	
public static boolean facsSum(int n){
	int rest = n;
	int current = count - 1;
		
	int[] facs = Facs();
		
	while(rest >= 0 && current >= 0){
		if(rest >= facs[current]){
			rest -= facs[current];
		}
		current--;
	}
		
	if(rest == 0)
		return true;
	return false;
}

这里有个技巧，在上面的代码中，Facs函数把0到9的阶乘储存在一个数组当中。这里有的同学可能会这么写代码。

private static int factorials(int n){
	if(n<=1)
		return 1;
	return factorials(n-1)*n;
}

private static int[] Facs(){
	int[] retFacs = new int[count];
	for(int i=0; i<count; i++){
		retFacs[i] = factorials(i);
	}
	return retFacs;
}

注意到差别没有，其实我们上一次用到的阶乘存放在临时数中，下轮就可以直接拿来使用。第二种方法更直观，但是重复的运算、加上递归的使用，使代码的效率低了许多。

因此，大家可以试试只用一个循环来计算1到100阶乘的和。

本文参考自这篇文章。文章是2003年的，但是现在来看仍然有着实际意义。

层级结构，也叫树形结构。在实际应用中，你经常需要保存层级结构到数据库中。比如说：你的网站上的目录。不过，除非使用类XML的数据库，通用的关系数据库很难做到这点。

对于树形数据的存储有很多种方案。主要的方法有两种：邻接表模型，以及修改过的前序遍历算法。本文将会讨论这两种方法的实现。这里的例子沿用参考文章中的例子，原文使用的PHP，这里将会用Java替代。（本例使用Mysql数据库，Java如何连接Mysql，见备注一。）文中使用虚拟的在线食品商店作例子。这个食品商店通过类别、颜色以及种类来来组织它的食品。如图所示：

在1960年代，计算机制造商们曾经估计，如果将所有的用户计入，他们制造的计算机有25%的时间用于排序。实际上，有很多计算机花了超过一半的计算时间在排序上。通过这样的评估结果，我们可以得出结论，可能（i）确实有很多非常重要的和排序相关的应用，或者（ii）很多人在进行一些不必要的排序计算，再或者（iii）低效的排序算法被广泛采用造成了计算的浪费。

来源《The Art of Computer Programming》，作者Donald Knuth

在Python实践中，我们往往遇到排序问题，比如在对搜索结果打分的排序（没有排序就没有Google等搜索引擎的存在），当然，这样的例子数不胜数。《数据结构》也会花大量篇幅讲解排序。之前一段时间，由于需要，我复习了一下排序算法，并用Python实现了各种排序算法，放在这里作为参考。

最简单的排序有三种：插入排序，选择排序和冒泡排序。这三种排序比较简单，它们的平均时间复杂度均为O(n^2)，在这里对原理就不加赘述了。贴出来源代码。

插入排序：

def insertion_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(1, iter_len):
        key = sort_list[i]
        j = i - 1
        while j >= 0 and sort_list[j] > key:
            sort_list[j+1] = sort_list[j]
            j -= 1
        sort_list[j+1] = key
    return sort_list

冒泡排序：

def bubble_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(iter_len-1):
        for j in range(iter_len-i-1):
            if sort_list[j] > sort_list[j+1]:
                sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j]
    return sort_list

选择排序：

def selection_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len < 2:
        return sort_list
    for i in range(iter_len-1):
        smallest = sort_list[i]
        location = i
        for j in range(i, iter_len):
            if sort_list[j] < smallest:
                smallest = sort_list[j]
                location = j
        if i != location:
            sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
    return sort_list

A杜：“我也曾经坠入爱河，可惜只有我一个掉进去了！”

老秦：“小刁，你只要不投篮就不会被盖的！！“

老秦：“那家伙胖得，踩你脚上你的脚就变成二维的了。”

钱波：“一朝碰周进，十年怕大娘。”

A杜：“那女生我就不喜欢。”小刁：“你是喜欢不上吧？”（真话有时候很伤人的）

刁:“我将来不想结婚了。” 周:“我也不想结婚啊.就是爸爸妈妈们不会答应的。”刁:“那我们假结婚吧.表面是夫妻,实际还是兄弟。”周:“那我女朋友和你男朋友要是不答应呢？”刁：“让他们结婚去。”周：“爷爷的。·#￥%……—~*”   

浦口大妈说过:“只许同居，不许混居......”

刁:“恋爱就像喝茶。不是必须品。但喝惯了的人又总少不了它。”杜：“我要喝茶.....”刁：“没有一碗茶愿意让你喝的。”   

进对刁说：“爱情可以长跑,但不要虚脱啊......”

某次，杜又去见一个暗恋他的女生，回来后只说了一句话：＂人生是如此地绝望！＂...............

A杜说高夫:"你们的生活真TMD颓废..."(我们呢?)   

A杜曾经曰过：“LOFT？兄弟不缺，缺钱！”

A杜口头禅：“死的个德国人啊！！”

刁刁：“自从见过丈母娘睡觉的照片之后，我觉得世界其他任何睡姿都是好看的！”

老秦：“8似叟有dei龅牙都似张蓉啊！”（普通话翻译：不是所有的龅牙都是张蓉！）

丫头：“我妹妹现在的身材比我好多了，要哪儿有哪儿！”刁刁：“废话!!!要哪儿没哪儿还是人啊！”ORZ

刁刁：“爷爷的，我就喜欢嫩的！”丈母娘：“我通吃。。。”……（丈人至今米有着落）

高夫：“我在你们小门那儿！”老秦：“哦，我到了，你在哪儿？”高夫：“就是那个小门那儿啊”…N久之后，老秦气喘吁吁对高夫说：“靠，这是我们大门，害我跑遍了东大所有的门！”

刁刁从南大回来：“南大除了大门，其他的都刚被轰炸过，尚未重建！”“南大浦口相当惨不忍睹啊”

陌生人：“同学，请问这里是什么学校？”（老秦正在吹嘘东大ing，众人倒绝……）

刁刁：“钱波太WS了，每次喝酒都第一个上厕所……”

看完释放的百合心，众人BS萎缩男ing，钱波力排众议：“他最后还是追到了啊！”BS对象更换。。。

丫头的家人：“倩啊，你这些朋友怎么都长的奇形怪状的啊？”

A杜：“我们在中央商场大门对面那个肯德基。”N久之后，老秦：“中央商场每个大门对面都有一个肯德基……”

刁刁：“高夫，泡个 俄国mm回来啊 ....高鼻梁大眼睛，顺便给你的家族改良下基因！”

高夫：“传记准备好没有？”进：“传记。。。靠，，，你怎么不让刁刁写啊。她可以写纪传体通史了，钱同学好像还是开篇第一章呢！”钱：“……我是前言，不是第一章！”进：“那A杜的出来就是诺贝尔文学奖了！”

钱：“以前一朋友（女生），说你怎么还是处男啊。。。。。。”