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

LINUX人123

学习学习。。

koolcoy

1. 用stl二分查找
2. 青蛙1，通过递推公式计算，也可以用F数列的计算公式直接算；
青蛙2，f(n) = f(n - 1) + f(n - 2) + .. + f(1) + 1 最终结果就是f(n) = 2^(n - 1)

1. 
   
2. #include <algorithm>
   
3. 
   
4. bool f1_search(int** array, int needle, int rowCount, int columnCount) {
   
5.         for (int i = 0; i < rowCount; ++i) {
   
6.                 if (array[i][0] > needle) {
   
7.                         return false;
   
8.                 }
   
9.                 int* x = std::lower_bound(array[i], array[i] + columnCount, needle);
   
10.                 if (x != array[i] + columnCount && *x == needle) {
    
11.                         return true;
    
12.                 }
    
13.         }
    
14.         return false;
    
15. }
    
16. 
    
17. int f2_frog1(int n) {
    
18.         int array[n + 1];
    
19.         array[0] = 0;
    
20.         array[1] = 1;
    
21.         array[2] = 2;
    
22.         for (int i = 3; i <= n; ++i) {
    
23.                 array[i] = array[i - 1] + array[i - 2];
    
24.         }
    
25.         return n > 0 ? array[n] : 0;
    
26. }
    
27. 
    
28. int f2_frog2(int n) {
    
29.         return (n > 0) ? (1 << (n - 1)) : 0;
    
30. }
    

复制代码

cjaizss

明白了,
对于第一个问题,
如果整体
如果设整体的数据为n个的话
这个问题
只有平方根级别的时间复杂度算法,对数级别应该是不存在的
大致想出了证明方法

hbmhalley

回复 72# cjaizss


    求思路!!

cjaizss

回复  cjaizss


    求思路!!
hbmhalley 发表于 2011-12-07 22:31

    我的证明思路就是用区域割图,直到割出至多常数个线型.但这只是一个思路,还没成为现实

jonas_mao

回复 1# 无风之谷


    个人觉得两道题都是一种常见的算法题。都可以用递归的方法实现：
   
   第一题是二维数组中查找特定值的问题。由于整个二维数组是有序的。所以就可以直接用简化的方法来查找。  
   下面是自己设计的一个递归的实现：

1. /*
   
2. 1，二维数组中的查找
   
3. 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
   
4. 例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字4，由于数组不含有该数字，则返回false。
   
5. 
   
6. 1   2   3   5   7
   
7. 3   6   8   9   12
   
8. 5   7   11  14  17
   
9. 7   8   12  16  20
   
10. 8   9   16  19  22
    
11. 
    
12. 分析，查找出这个二维数组a[x][y]的第一行中第N个元素开始比要查找的数字大，
    
13.       查找出这个二维数组的第一列中第M个元素开始比要查找的数字大，然后以N和M为下标找出对角线上的数，如果比要找的数大，则开始递归
    
14.           递归的规则是：分别把行和列减去1进行递归，递归的退出条件是其中行或列为小于1.
    
15. */
    
16. 
    
17. #include <stdio.h>
    
18. 
    
19. #define PAL_TRUE      1
    
20. #define PAL_FALSE     0
    
21. 
    
22. unsigned int findNumber (int a[][5], int line, int row, int numb)
    
23. {
    
24.   int i, j;
    
25.   int line_index, row_index;
    
26.   int is_find;
    
27. 
    
28.   is_find = PAL_FALSE;
    
29.   
    
30.   if (a == NULL)
    
31.     {
    
32.           return PAL_FALSE;
    
33.         }
    
34.        
    
35.   if (line == 0 || row == 0)
    
36.     {
    
37.           return PAL_FALSE;
    
38.         }
    
39.    
    
40.   
    
41.   for (i = 0; i < line; i++)
    
42.     {
    
43.           if (a[0][i] == numb)
    
44.             {
    
45.                   printf("\n a[0][%d] = %d", i, numb);
    
46.                   return PAL_TRUE;
    
47.                 }   
    
48.       else if (a[0][i] > numb)
    
49.             {
    
50.                   line_index = i - 1;
    
51.                   break;
    
52.                 }
    
53.         }
    
54.   
    
55.   if (i == line)
    
56.     {
    
57.           line_index = line;
    
58.         }
    
59.        
    
60.   for (j = 0; j < row; j++)
    
61.     {
    
62.           if (a[j][0] == numb)
    
63.             {
    
64.                   printf("\n a[%d][0] = %d", j, numb);
    
65.                   return PAL_TRUE;
    
66.                 }
    
67.           else if (a[j][0] > numb)
    
68.             {
    
69.                   row_index = j - 1;
    
70.                   break;
    
71.                 }
    
72.         }
    
73.   
    
74.   if (j == row)
    
75.     {
    
76.           row_index = row;
    
77.         }
    
78.        
    
79.   if (a[row_index][line_index] == numb)
    
80.     {
    
81.           printf("\n a[%d][%d] = %d", row_index, line_index, numb);
    
82.           return PAL_TRUE;
    
83.         }
    
84.    
    
85. 
    
86.   if (findNumber (a, line_index - 1, row_index, numb) == PAL_TRUE)
    
87.     return PAL_TRUE;
    
88. 
    
89.   if (findNumber (a, line_index, row_index - 1, numb) == PAL_TRUE)       
    
90.     return PAL_TRUE;
    
91.   
    
92.   return PAL_FALSE;  
    
93. }
    
94. 
    
95. int main (void)
    
96. {
    
97.   int a[4][5] = {{1,2,3,5,100},{3,6,8,9,90},{5,7,11,14,80},{7,8,12,16,60}};
    
98.   
    
99.   int if_find1, if_find2, if_find3;
    
100.   
     
101.   if_find1 = findNumber (a, 5, 4, 16);
     
102.   printf ("\n %s the number %d", if_find1 ? "find" : "not find", 16);
     
103. 
     
104.   if_find2 = findNumber (a, 5, 4, 5);
     
105.   printf ("\n %s the number %d", if_find2 ? "find" : "not find", 5);
     
106.   
     
107.   if_find3 = findNumber (a, 5, 4, 7);
     
108.   printf ("\n %s the number %d", if_find3 ? "find" : "not find", 7);
     
109. 
     
110.   return 0;  
     
111. }
     

复制代码

第二题：
第一种情况可以先枚举一下，应该是费波那西数列 f(1)=1, f(2)=2. f(n)= f(n-1)+ f(n-2).   递归即可求得；
第二种情况应该是背包算法原理的一个另外一种延伸。题目可以理解为1到N里面的整数有几种组合相加可以得到n. 这里可以认为从1到N里的数组合要相加得到N，那么每一个数都有两种可能，一种是参与相加，一种是不参与相加。
           这样定义一个N个元素的数组a[N]，如果1参与，则a[1] = 1;1不参与则a[1] = 0;  依次类推，定义一个全局变量，用递归的方法即可计算出所有的组合数。

隔了四五天没有逛论坛了，今天看到，不知道这样理解正不正确？ 望老师纠正

jjboy110

帖子怎么这么难写？？

1. 
   
2. 第一题：
   
3. 我只说思路，程序就不写了呵呵
   
4. 将该数与矩阵对角线元素做二分查找，如果有相等的，返回true，否则该数出现在刚好比他大的那个数a[i][i]上方和左方，，然后在a[0][i]到a[i][i]和a[i][0]到a[i][i]对该数做二分查找，如果相等返回true，否则返回false
   
5. 第二题：
   
6. 呵呵，我是学数学的：
   
7. 1、f(n)=f(n-1)+f(n-2)  f(1)=1 f(2)=2
   
8. 2、f(n)=f(n-1)+f(n-2)+...+f(1)+1 f(1)=1
   

复制代码

补充：
第一题被误导了，没有考虑到不是方阵的情况，不过也没关系，不是方阵把他补成方阵，酌情加1，这样来只用进行两次较长边的二分查找，从算法复杂度来说应该是优于22L的方法，不过22L的方法非常不错。

Flashboy2005

学习了。

第一题到真没想到二分查找。
第二题也只考虑到递归，没想到2^(N-1)。

hbmhalley

回复 76# jjboy110

将该数与矩阵对角线元素做二分查找，如果有相等的，返回true，否则该数出现在刚好比他大的那个数a[ i ][ i ]上方和左方，，然后在a[ 0 ][ i ]到a[ i ][ i ]和a[ i ][ 0 ]到a[ i ][ i ]对该数做二分查找，如果相等返回true，否则返回false

    1 2 3
    4 5 6
    7 8 9

    Query = 3

    怎么找

jjboy110

回复 78# hbmhalley

你说的没错，我思路是错误的。
    我同意22L是最佳答案