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

tomac_cu

我来晚了

cibn09

学习了，，真是强大

cjaizss

22L应该是最优的
那些分块四分的如何处理左下与右上的大小关系？
hbmhalley 发表于 2011-12-03 19:25

    通用情况下来说，这种做法是最次的

午夜凋零

程序员求职找工作，谁也逃不掉做编程面试题，这样的面试题，你做过吗？
1，二维数组中的查找
在一个二维 ...
无风之谷 发表于 2011-11-30 11:52

我用的perl，下面是代码。
1.数组中查找：

1. $r_array = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]];
   
2. $goal = 14;
   
3. foreach $i (0..$#{$r_array}) {
   
4.     foreach $j (0..$#{$r_array->[0]}) {
   
5.         if ($r_array->[$i]->[$j] == $goal ) {
   
6.             print "true\n";
   
7.             exit 0;
   
8.         }
   
9.     }
   
10. }
    
11. print "false\n";

复制代码

2(1).青蛙跳：

1. $goal = 5;
   
2. $step = 2;
   
3. if ( ($goal < 1) or ($step < 1) ) {
   
4.     print "ERROR\n";
   
5.     exit -1;
   
6. }
   
7. $former0 = 1;
   
8. $former1 = 1;
   
9. $way = 0;
   
10. for (2..$goal) {
    
11.     $way = $former0 + $former1;
    
12.     $former0 = $former1;
    
13.     $former1 = $way;
    
14. }
    
15. print "way:$way\n";

复制代码

2(2).n个台阶，1..n都可以跳时，跳的方法就是2的n次方种。
记跳上第n个台阶的方法数是$way_n，跳上第n-1个台阶的方法是$way_n_1，则$way_n = $way_n_1 + $way_n_2 + … + $way_1 + 1;
最后一个1是从地上直接跳了n个台阶。
$way_1 = 1;
$way_2 = 2;
$way_3 = 4;
...
$way_n = 1 + 2^1 + 2^2 + 2^3 + ... + 2^(n-1) = 2^n;

pozenfly

在算法里面也就算1+1=2的问题！

1， 折半查找 效率O(log(n)+log(m))

2， 第一问简单递推 t[n] = t[n-1] + t[n-2]
      第二问最特么简单的DP

不贴代码，因为我不想要书，，，呵呵， 表告诉我书里面内容就这水平，，，

zhoucosin

青蛙问题第一个

ahutwgs

/*思路：
1、先看第一个数是否小于num（所查找的数）最后一个是否小于num,是则输出false，否则判断是否相等，相等则输出true,否则下一步
2、从第一行找第一个大于num所在的列j，如果有等于的则退出且输出true,否则下一步
3、从j=j-1列的i行到n-1行找=num的数所在的行i，若有则输入true，否则重复3;
*/

#include<stdio.h>

#define maxsize 100


int main(void)
{
        int n,i,j;
        int a[maxsize][maxsize];
        int num;
        int low,high;
        i=0,j=0;
        printf("n=");
        scanf("%d",&n);
        printf("a[%d][%d]=\n",n,n);
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                scanf("%d",&a[i][j]);
        printf("num=");
        scanf("%d",&num);
        if(num<a[0][0]||num>a[n-1][n-1])
        {
                printf("false!\n");
                return 0;
        }
        if(num==a[0][0]||num==a[n-1][n-1])
        {
                printf("true!\n");
                return 0;
        }
       
        for(i=0,j=1;j<n;j++)
        {
                if(a[i][j]==num)
                {
                        printf("true!\n");
                        return 0;
                }
                if(a[i][j]>num)
                        break;
               
        }
        i=1;
        for(j=j-1;j>=0;j--)
        {       
                if(j<0||i>n-1)
                {
                        printf("false!\n");
                        return 0;
                }
                for(;i<n;i++)
                {
                        if(num==a[i][j])
                        {
                                printf("true!\n");
                                return 0;
                        }
                        if(num<a[i][j])
                                break;
                }
        }
        printf("false!\n");
        return 0;
       
}

ahutwgs

补充，查找时我用的是顺序查找，当然我用二分法效率肯定是会高点的.

ahutwgs

青蛙问题:
1、
f(n)=f(n-1)+f(n-2)
f(0)=2;
2、
f(n)=f(n-1)+f(n-2)+.....+f(0);
f(0)=n;

都是用递归解决的.

没有抄袭楼上的意思，我是想过之后再看楼上的回答的。

ahutwgs

呵呵…… 不好意思，那个思路写的太……

改为
/*思路：
1、先看第一个数是否小于num（所查找的数）最后一个是否大于num,是则输出false，否则判断是否相等，相等则输出true,否则下一步
2、从第一行找第一个大于num或等于所在的列j，if等于则退出且输出true,否则下一步
3、从j=j-1列的i行到n-1行找=num或者第一个大于num的数所在的行i，若==num则输出true且退出程序，否则重复3;
*/