这样的面试题，你会吗？（有奖）

无风之谷

获奖名单已公布，详情请看：http://bbs.chinaunix.net/thread-3630628-1-1.html

程序员求职找工作，谁也逃不掉做编程面试题，这样的面试题，你做过吗？
1，二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。



2，青蛙跳台阶问题
（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？

活动流程：
1.请将你的答案跟帖回答
2我们邀请了何海涛老师对参与者的回复进行评选，将根据提交的思路及答案评选出5个获奖者。
3.获奖者均可获得图书《剑指Offer：名企面试官精讲典型编程题》1本。

活动时间：2011-11-30——2011-12-14

活动要求：
参赛者以跟帖的方式提交代码，相似代码以最先提交为准。
注：严禁抄袭，一经发现，取消评选资格；

king_819

学习下

kns1024wh

回复 1# 无风之谷


（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？

考察是程序员的算法问题  同时也是思维逻辑问题
不算太BT的题目

参考解题思路

按照传统遍历来解题思路是这样的矩阵行列都是从小到大排好序的，要查找的话自然用二分效率比较高，
而且这样的矩阵有个性质，最左上角的元素必定是最小值，最右下角的是最大值，在一个
n*n的矩阵中，对角线的元素也是排好序的，找到对角线上的一个元素，使得这个元素小于
待查找的key，并且下一元素大于待查找的key，那么只要在这个元素的左下角矩阵和右上角
矩阵递归继续对角线查找就可以了，例如上图例子里查找7，只要找到对角线的元素4，然后
递归查找红圈的矩阵就可以了，左上角矩阵最大值4<7，右下角
矩阵最小值10>7，无需查找了，但是此题并没有告诉我们原始矩阵是n*n的，这是比较麻烦的
地方，不过思路是一样的，无非不能用对角线查找这样简单的办法了，假设m*n的矩阵，对角线
查找的办法改进为i = (m1+m2)/2，j = (n1+n2)/2 进行查找就可以了，(m1,n1)为矩阵最左上角
元素下标，(m2,n2)为最右下角元素下标

假设查找17，第一次比较10，然后比较25，然后比较13，返回元素13，这时候再递归查找13
左下角的矩阵和右上角的矩阵就可以了（红色椭圆部分）；如果是查找9，第一次比较10，然后比较4，
然后比较然后比较6，返回元素6，这时候递归查找6左下角的矩阵和右上角矩阵（绿色椭圆部分）
代码如下：
a是二维数组首地址，(m1, n1)左上角坐标，(m2, n2)右下角坐标，参数n是矩阵一行的元素个数
int binsearch(int value, int *a, int n, int m1, int n1, int m2, int n2)
{
        int begin_m1 = m1, begin_n1 = n1, end_m2 = m2, end_n2 = n2;
        int left_result = 0,  right_result = 0;
        int i = (m1+m2)/2, j = (n1+n2)/2;
        if (value < *(a+m1*n+n1) || value > *(a+m2*n+n2))
                return 0;
        else if (value == *(a+m1*n+n1) || value == *(a+m2*n+n2))
                return 1;

        while ((i!=m1 || j!=n1) && (i!=m2 || j!=n2)){
                 if ( value == *(a+i*n+j) )
                         return 1;
                 else if ( value < *(a+i*n+j) ){
                         m2 = i;
                         n2 = j;
                         i = (i+m1)/2;
                         j = (j+n1)/2;
                  }
                 else{
                         m1 = i;
                         n1 = j;
                         i = (i+m2)/2;
                         j = (j+n2)/2;
                 }
           }
           
           //search left & right
           if ( i<end_m2 )
                   left_result = binsearch(value, a, n, i+1, begin_n1, end_m2, j);
           if ( j<end_n2 )
                   right_result = binsearch(value, a, n, begin_m1, j+1, i, end_n2);
           if (left_result | right_result )
                   return 1;
           else
                   return 0;
}

renxiao2003

这个题有难度。看看。

x9x9

占位学习~

taojie2000

编程 不懂写

不过青蛙跳到1000阶累死它

amarant

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

设二维数组的大小是 x * y
那么从 a = x / 2 , b = y / 2 里的元素开始对比，对比出结果以该点构成新的矩阵
再从 a = a / 2; b = b / 2 或者 a = (x-a)/2; b= b/2 对比 或者 。。 或者  。。 （四种情况）
整体的算法就是一直把矩阵平分成四块，做四次if判断，判断要查找的元素在那个块里再重复上一次的查找

hellioncu

1. unsigned int count2_1(unsigned int num)
   
2. {
   
3.         if (num <= 2)
   
4.         {
   
5.                 return num;
   
6.         }
   
7. 
   
8.         unsigned int a = 1;  
   
9.         unsigned int b = 2;  
   
10.         unsigned int tmp;  
    
11.         for(unsigned int i = 3; i <= num; ++i)  
    
12.         {  
    
13.                 tmp = a;  
    
14.                 a = b;  
    
15.                 b += tmp;  
    
16.         }  
    
17.         return b;  
    
18. }
    
19. 
    
20. unsigned int count2_2(unsigned int num)
    
21. {
    
22.         assert(num <= sizeof(unsigned int) * 8);
    
23.         return 2 << (num - 1);
    
24. }
    

复制代码

EnjoyKernel

假设青蛙从平地第0级阶梯跳起，很明显啊，它可以跳到第1和第2啊。
假设青蛙已经跳到了第n-2级阶梯，很明显啊，它累了，它用力跳两级就跳到了n级。
假设还是这只青蛙，已经跳到了第n-1级阶梯，很明显啊，它累了，它轻轻跳了一级终于跳完了。
乱了。。 是不是f(n)=f(n-1)+f(n-2)？

第一次回帖，穷人求加分，求书，求美眉。

dooros

占位学习……