这样的面试题，你会吗？——博文视点杯有奖答题活动

可惜现在才看到,都过期了,25号的
也看了上面兄弟的代码果然精辟
我只能自己献丑了,青蛙跳的问题

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Test {
	public static void main(String[] args) {
		TreeSet<String> t = new TreeSet<String>();
		// 台阶高度为 n
		int n = 10;
		// 可以跳多少级
		int w = 6;
		jump(n, t, new ArrayList<Integer>(n), w);
		System.out.println("跳" + n + "高度的阶梯,一次可以跳:" + w + ".有以下跳法:");
		for (String step : t) {
			System.out.println(step);
		}
		System.out.println("共有" + t.size() + "种跳法");
	}

	public static void jump(int n, Set<String> record,
			List<Integer> tempRecord, int 可以跳多少步) {
		if (isOutOfN(tempRecord, n) > 0) {
			for (int i = 1; i <= 可以跳多少步; i++) {
				tempRecord.add(i);
				jump(n, record, tempRecord, 可以跳多少步);
			}
		} else if (isOutOfN(tempRecord, n) < 0) {
			if (tempRecord.size() > 0) {
				tempRecord.remove(tempRecord.size() - 1);
			}
			return;
		}
		// 记录为一种跳跃的记录
		else if (isOutOfN(tempRecord, n) == 0) {
			record.add(tempRecord.toString());
		}
		if (tempRecord.size() > 0) {
			tempRecord.remove(tempRecord.size() - 1);
		}
	}
	/**
	 * 
	 * <DL>
	 * <DT><B> 标题. </B></DT>
	 * <p>
	 * <DD>
	 * 详细介绍</DD>
	 * </DL>
	 * <p>
	 * <DL>
	 * <DT><B> 创建时间: </B></DT>
	 * <DD>2011-12-28 下午11:43:47</DD>
	 * </DL>
	 * 
	 * @return 0为刚刚好, 正数表示还差多少级,负数表示超出多少
	 * @since 1.0 2011-12-28
	 */
	public static int isOutOfN(List<Integer> tempRecord, int n) {
		int j = 0;
		for (int i = 0; i < tempRecord.size(); i++) {
			j += tempRecord.get(i);
		}
		return n - j;
	}
}

url:http://liuqing-2010-07.iteye.com/blog/1330830
大家去我的博客看看 讨论讨论欢迎光临！

在没有进这个帖子之前，我就猜到了一定会有人贴上‘自己的代码’的。既然是蛋疼，既然不是答案，那为什么还要贴呢？总是有一部分人这样搞。哎。

同意楼主的看法 但少放点广告 多放点有价值 营养的 东西 有时候一进去看 啥东西也没有。我的建议 以后不足500子的博客不能在首页显示。

同意楼主的看法 但少放点广告 多放点有价值 营养的 东西 有时候一进去看 啥东西也没有。我的建议 以后不足500子的博客不能在首页显示。

    非常感谢大家关注、参与本次活动。刚才逐一拜读了大家的解答，很有收获，我看到了很多有意思的思路与讨论，学到了不少新方法。谢谢各位。

    我会根据大家的思路的可行性、代码的完整性、时间效率以及答题的先后打分。最终的获奖结果随后由主办方公布。

    参考答案：

    第一题：本题是《剑指Offer——名企面试官精讲典型编程题》的第三个例题。书中的解题思路碰巧和这里22楼crazyhadoop的思路一致。暂时没有买书的朋友，可以到china-pub网上的免费试读样章（http://images.china-pub.com/ebook195001-200000/198770/ch02.pdf）的第38-42页中看到详细的分析以及代码。

    这一题很多网友都试图用二分法查找来解决。试图用二分法在对角线上做文章的朋友，可以参考一篇博客（http://blog.csdn.net/expp/article/details/7008972）。这是一个网友参加同一活动时（在新浪微博上举行）的解答。博客中有插图，分析很形象。

    第二题：第一问很多网友都分析出来了，它的规律是fibonacci数列。fibonacci数列不同的实现方式的时间效率大不一样。通常我们认为递归不是一个很好的办法。感兴趣的网友可以试着用递归的方法去就fibonacci的43项，看看需要很长时间才能算出结果。我在一篇博客（http://zhedahht.blog.163.com/blog/static/25411174200722991933440/）讨论了不同实现方式的效率。通常在面试的时候，面试官会期待基于循环的解法。基于矩阵乘法的O(lgN)的解法由于代码量很大，面试时一般不会作要求。

    第二问的结果和很多网友分析的一样，是2^(n-1)次方。没有得出这个结果的网友，可以用数学归纳法证明f(n)=f(n-1)+f(n-2)+...+f(2)+f(1)+1=2^(n-1)。由于是求2的乘方，写代码时可以通过移位运算符实现。这样效率比在一个循环里做乘法要快一些。

    这个题目也收录到了《剑指Offer——名企面试官精讲典型编程题》中了，是书中的第9个例题，在书中73-77页。

    祝大家新年快乐，万事如意。

老师，您差点吓死我，第二题 当n= m（n为台阶数，m为青蛙跳的最大台阶数）时是F(n)=2^(n-1)
我做的是通用算法。我以为我做错了，我已经在博客（url：http://liuqing-2010-07.iteye.com/blog/1330830）中发表。差点跑去把它删了。当n= m 时 归纳猜想就行了就没有太大难度了。老师，吓死我了 我没做错吧！

首先非常感谢您对本次活动的关注。

您博客中的版本的解答比您最初递交的解答好多了。第二题的解决方案已经很完备了。尤其喜欢您用一个队列解决f(n,m)，这样很好地解决了递归方法的效率问题。

您第一个问题的解法，尽管您做了一些优化，但本质上仍然是一个O(n*log(m))的算法。在前面的回复中，列举了两个O(m+n)的解法，可供参考（当m、n大致相等的时候，O(m+n)的算法优于O(n*log(m))的算法。但当m远大于n时，O(n*log(m))的算法优于O(m+n)的算法）。

祝您新年愉快，心想事成。

哦，我已经好久没搞这种没意义的算法什么的了；看来落伍了。