【已结束】这样的面试题，你会吗？ ——博文视点有奖答题活动全面启动

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

    程序员求职找工作，谁也逃不掉做编程面试题，这样的面试题，你做过吗？春节过后新一轮的招聘季即将到来，你准备好迎接面试官的挑战了吗？ CSDN&ITeye联合 电子工业出版社博文视点推出有奖答题活动，只要你开动脑筋，积极参与，不仅可以锻炼自己的答题能力，更有机会获得由博文视点送出的畅销精品图书——《剑指Offer：名企面试官精讲典型编程题》。心动不如行动，让智慧为你赢得新年好运大礼吧！

活动时间：2011年12月14日—12月25日

活动流程：

1.为避免抄袭，请将您的论坛id、姓名、电话、地址和答案发送至webmaster(at)csdn.net， 答案以压缩包的形式提交。
2.由《剑指Offer：名企面试官精讲典型编程题》的作者何老师根据提交的思路及答案评选出5位获奖者。
3.每位获奖者均可获得博文视点最新热销图书《剑指Offer：名企面试官精讲典型编程题》1本。

博文视点有奖答题第一题：

二维数组中的查找

  在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
    
    例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

博文视点有奖答题第二题：

青蛙跳台阶问题

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


看完题目是不是跃跃欲试？快来提交你的答案吧！下一个面霸就是你！

图书介绍

《剑指Offer：名企面试官精讲典型编程题》
何海涛 编著
ISBN 978-7-121-14875-0
45.00元272页
面试官的视角    50余道编程题
系统的解题方法超写实体验与感悟

内容简介

  本书剖析了50个典型的程序员面试题，从基础知识、代码质量、解题思路、优化效率和综合能力五个方面系统整理了影响面试的5个要点。全书分为7章，主要包括面试的流程，讨论面试流程中每一环节需要注意的问题；面试需要的基础知识，从编程语言、数据结构及算法三方面总结了程序员面试的知识点；高质量的代码，讨论影响代码质量的的3个要素（规范性、完整性和鲁棒性），强调高质量的代码除了能够完成基本的功能之外，还能考虑到特殊情况并对非法输入进行合理的处理；解决面试题的思路，总结在编程面试中解决难题的常用思路，如果在面试过程中遇到了复杂的难题，应聘者可以利用画图、举例和分解复杂问题3种方法化繁为简，先形成清晰的思路再动手编程；优化时间和空间效率，介绍如何优化代码的时间效率和空间效率，读完这一章读者将学会常用的优化时间效率及空间换时间的常用算法，从而在面试中找到最优的解法；面试中的各种能力，本章总结应聘者在面试过程中如何表现学习能力和沟通能力，并通过具体的面试题讨论如何培养知识迁移能力、抽象建模能力和发散思维能力；两个面试案例，这两个案例总结了应聘者在面试过程中哪些举动是不好的行为，而哪些表现又是面试官所期待的行为。

  本书适合即将走向工作岗位的大学生阅读，也适合作为正在应聘软件行业的相关就业人员和计算机爱好者的参考书

目前已经成功提交答案的用户：

id：pmars

id：dogfish

参赛者一定要将id、姓名、电话、地址、答案（以压缩包形式）发送到webmaster(at)csdn.net

136 个解决方案

#1

本帖最后由 zhaixiaohu 于 2011-12-15 10:29:25 编辑

欢迎大家踊跃参加，答题赢好书~

参赛者一定要将id、姓名、电话、地址、答案（以压缩包形式）发送到webmaster(at)csdn.net

#2

1，矩阵，二分查找？
2，类似，斐波那契数列？

#3

有难度...

#4

青蛙跳台阶问题

（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
---------------------
1、类似概率论里学的组合问题，f(n)=f(n-1)+f(n-2) 类似斐波那契数列
2、递推公式，f(n)=f(n-1)+f(n-2)+...+f(1)+1

#5

收藏了，等牛人回答。

#6

建议转到C/C++或者数据结构算法板块吧。
一般没人来投诉区看技术问题的。

#7

#8

#9

第一题 暂时能想到比较快的方法应该是 沿对角线找第一个比 要查找数大的位置，
然后在 那个位置的所在行 和 列找，如果找得到就存在，找不到就不存在

如果矩阵的行 和 列 不相等，要划分成几个行列相等的小矩阵查找

//M行 N列的数组a[M][N]
//沿对角线找到 第一个 比 要找的数 大的位置，然后在这个位置所在的行 和 列 找
 if (M == N)
 {
   for (i = 0; i < M; i++)
   {
      if (nfind == a[i][i])
      {
        return true;
      }
      else if (nfind < a[i][i])
      {
        // 比较第i行中 0 ~ i - 1有没有 nfind
        j = i - 1;
        while (j >= 0)
        {
           if (a[i][j] == nfind)
           {
             return true;
           }
           j--;
        }
        // 比较第i列中 0 ~ i - 1有没有 nfind
        j = i - 1;
        while (j >= 0)
        {
           if (a[j][i] == nfind)
           {
             return true;
           }
           j--;
        }
        return false;
      }
   }
   return false;
}

#10

引用 9 楼 cuidx 的回复:

第一题 暂时能想到比较快的方法应该是 沿对角线找第一个比 要查找数大的位置，
然后在 那个位置的所在行 和 列找，如果找得到就存在，找不到就不存在

如果矩阵的行 和 列 不相等，要划分成几个行列相等的小矩阵查找
C/C++ code


//M行 N列的数组a[M][N]
//沿对角线找到 第一个 比 要找的数 大的位置，然后在这个位置所在的行 和 列 找
 if (M == N)
……

最好发答案到，webmaster（at）csdn.net

#11

第一个题目还是挺简单的。

#12

引用 8 楼 mockqi 的回复:

没有考虑M!=N的情况

#13

引用 8 楼 mockqi 的回复:

第一题 暂时能想到比较快的方法应该是 沿对角线找第一个比 要查找数大的位置，
然后在 那个位置的所在行 和 列找，如果找得到就存在，找不到就不存在

如果矩阵的行 和 列 不相等，要划分成几个行列相等的小矩阵查找
C/C++ code

//M行 N列的数组a[M][N]
//沿对角线找到 第一个 比 要找的数 大的位置，然后在这个位置所在的行 和 列 找
 if (M == N)
 {
   for (i = 0; i < M; i++)
   {
      if (nfind == a[i][i])
      {
        return true;
      }
      else if (nfind < a[i][i])
      {
        // 比较第i行中 0 ~ i - 1有没有 nfind
        j = i - 1;
        while (j >= 0)
        {
           if (a[i][j] == nfind)
           {
             return true;
           }
           j--;
        }
        // 比较第i列中 0 ~ i - 1有没有 nfind
        j = i - 1;
        while (j >= 0)
        {
           if (a[j][i] == nfind)
           {
             return true;
           }
           j--;
        }
        return false;
      }
   }
   return false;
}

没有考虑M!=N的情况

#14

引用 9 楼 cuidx 的回复:

第一题 暂时能想到比较快的方法应该是 沿对角线找第一个比 要查找数大的位置，
然后在 那个位置的所在行 和 列找，如果找得到就存在，找不到就不存在

如果是这样的呢？
1  2  8  9
2  4  9  12
4  5  10 13
7  8  11 15
按这种算法应该确定在
1  2  8
2  4  9
4  5  10
这个范围，然后没找到7，就判断它不存在么？
这样的思维很灵活，但是不是太就题论题了，没考虑普遍性，不一定就是题目的那个数组啊！我这个也是从上倒下和从左到右递增的！
如果数组不是很大，直接用二重循环遍历一道，逐个比较！

#15

还好，想不想尝试一番啊、

#16

有意思

#17

路过的

#18

顶！顶！顶！

#19

#20

加上一句判断不就解决了吗 

if (i != m - 1)
                    {
                        i = m - 1;
                    }

#21

有奖答题  

#22

用啥语言回答？java?c?.net?

#23

这答案有问题，你找6试试

引用 9 楼 cuidx 的回复:

第一题 暂时能想到比较快的方法应该是 沿对角线找第一个比 要查找数大的位置，
然后在 那个位置的所在行 和 列找，如果找得到就存在，找不到就不存在

如果矩阵的行 和 列 不相等，要划分成几个行列相等的小矩阵查找
C/C++ code


//M行 N列的数组a[M][N]
//沿对角线找到 第一个 比 要找的数 大的位置，然后在这个位置所在的行 和 列 找
 if (M == N)
……

#24

有难度。。。。。。。

#25

引用 14 楼 chenshenggangatxjgc 的回复:

...

嗯，的确有问题,谢谢大家
修改一下，大家再给指正下

//...
        // 比较第i ~ M行中 0 ~ i - 1有没有 nfind
        k = i;
        while (k < M)
        {
           j = i - 1;
           while (j >= 0)
           {
              if (a[k][j] == nfind)
              {
                 return true;
              }
              if (a[k][j] < nfind)
              {
                 break;
              }
              j--;
           }
           k++;
        }
        // 比较第i ~ N列中 0 ~ i - 1有没有 nfind
        k = i;
        while (k < N)
        {
            j = i - 1;
            while (j >= 0)
            {
               if (a[j][k] == nfind)
               {
                  return true;
               }
               if (a[j][k] < nfind)
               {
                  break;
               }
               j--;
            }
            k++;
        }
//...

原来只比较所在行和列的思路肯定是错的，现在改成比较 左下 和 右上 两个区域
这样M ！= N的情况，应该也可以处理了

#26

第一题一个一个查，不行吗

#27

顶贴的份啊！顶贴的份啊！

#28

顶贴的份啊！顶贴的份啊！顶贴的份啊！

#29

学生党，学习了，谢谢楼上的老师。

#30

引用 28 楼 gblspys 的回复:

顶贴的份啊！顶贴的份啊！顶贴的份啊！

唉 。。。
谁有答案别忘了给我发一份啊 、我也好学习学习
[e-mail]
谢谢了。

#31

#32

引用 26 楼 ysm804471920 的回复:

第一题一个一个查，不行吗

既然给出了附加条件，从左到左，从上到下递增，就应该有更加省时的方法

#33

找个时间做下

#34

顶一下 关注！

#35

这问题，谁能解开啊？

#36

#include "stdio.h"
#include "stdlib.h"
int fond = 0;
//1 2 3 4 5 7 8 9 10 11 12 13 15 16 17 18
//         6                 14          19 20
int array[5][5]={
{ 1, 2, 8, 9,11},
{ 3, 4, 9,11,12},
{ 4, 5,10,13,16},
{ 7, 8,11,15,17},
{ 9,10,12,16,18}
};
int x=0,y=0;
int check(int &sy,int &sx,int &ey,int &ex,int goal)
{
	if(sx>=ex||sy>=ey)
		return 1;

	y=sy,x=sx;//[sy][sx]|

	for(x=sx;x<ex;x++)
	{//向下搜寻
		if(array[y][x]<goal)
			continue;
		else
			if(array[y][x]==goal)
			{
				fond = 1;
				return 1;
			}
			else
			{
				ex=--x;
				break;
			}
	}
	sy++;

	y=sy,x=sx;//[sy][sx]-
	for(y=sy;y<ey;y++)
	{//向右搜寻
		if(array[y][x]<goal)
			continue;
		else
			if(array[y][x]==goal)
			{
				fond = 1;
				return 1;
			}
			else
			{
				ey=--y;
				break;
			}
	}
	sx++;

	y=ey,x=ex;//[ey][ex]
	for(x=ex;x>=sx;x--)
	{//向上搜寻
		if(array[y][x]>goal)
			continue;
		else
			if(array[y][x]==goal)
			{
				fond = 1;
				return 1;
			}
			else
			{
				sx=++x;
				break;
			}
	}
	ey--;

	y=ey,x=sx;//[ey][ex]
	for(y=ey;y>=sy;y--)
	{//向左搜寻
		if(array[y][x]>goal)
			continue;
		else
			if(array[y][x]==goal)
			{
				fond = 1;
				return 1;
			}
			else
			{
				sy=++y;
				break;
			}
	}
	ex--;
	return 0;
}

int main()
{
	int x0=0,y0=0,x1=4,y1=4;
	int goal = 15;

	for(int i=0;i<=20;i++)
	{
		fond =0;
		x0=0,y0=0,x1=4,y1=4;
		while(!check(y0,x0,y1,x1,i));
		printf("%d:[%d,%d]  %s\n",i,y,x,(fond?"Fond it!":"Not Fond"));
	}

	return 0;
}

#37

2 斐波那契数列...f(n)=f(n-1)+f(n-2)
3  f(n)  = f(n-1)+f(n-2)+...f(1)+f(0)
   f(n-1)=        f(n-2)+...f(1)+f(0)
  得出 f(n)=(2^1)f(n-1)= (2^m)f(n-m) = (2^(n-1))f(1)=2^(n-1)

#38

- -

#39

还真不会

#40

该回复于2011-12-15 15:46:43被版主删除

#41

第一题更快一点的思路是 二分查找

可以对每行做二分查找
也可以变通一下，在二维数组上直接做二分查找 应该会更快些

#42

该回复于2011-12-15 15:46:34被版主删除

#43

顶上....

#44

1. 二分查找思想，从左下角开始作为第一个关键字，比关键字大，就将右边设为关键字，比关键字小就将上面的设为关键字，依次类推直到到达右上角或者找到该数。

2. 递推公式，类似fibonacci数列

#45

public class ShuzuTest {
public static void main(String args[]){
int num[][]={{1,3,5,6,8,67},
     {2,4,6,7,10,100},
     {21,41,61,71,101,1001},
     {211,411,161,711,1011,10011},
                     {222,422,622,722,1022,10022}};
display(num);
boolean bool=false;
bool=isExist(num,10011);
System.out.println(bool);//true
bool=isExist(num,15);
System.out.println(bool);//false
}

//比较的方法，遍历数组
public static boolean isExist(int a[][],int num){
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++){
//如果找到有相等的直接返回true
if(num==a[i][j]){
return true;
}
}
}
//遍历数组结束后都没有找到相等的数据，返回false
return false;
}
//显示数组
public static void display(int a[][]){
System.out.println("数组数据如下：");
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++){
System.out.print(a[i][j]+"\t");
}
//换行
System.out.println();
}
}
}

#46

还有这样的？

#47

学生看的好有压力啊！！  不会哦

#48

基本什么都看不懂唉……

#49

写了一段code 觉得可以工作 大家看看

// InterviewQuestion.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <iostream>
#include "windows.h"


/*
Question 1, find the particular number in a two vector array

{1, 2, 8, 9},
{2, 4, 9, 12},
{4, 7, 10, 13},
{6, 8, 11, 15}

the array is sorted from small to big in both left->right and top->bottom

*/



typedef std::vector< std::vector<unsigned int> > TwoDArray;

// if find, return 0 else return -1
int FindNumber (const TwoDArray& a, unsigned int number, int& posx, int& posy)
{
	// find an cut

	int startx = 0;
	int starty = 0;
	int endx = a[0].size() - 1;
	int endy = a.size() - 1;
	bool find = false;

	do 
	{		
		// from left->right first;

		int start = startx;
		int end = endx;
		int middle = (start + end) >> 1;

		while (start <= end)
		{
			middle = (start + end) >> 1;

			if (a[starty][middle] == number)
			{
				find = true;
				posx = middle;
				posy = starty;
				goto ENDCODE;
			}
			else if (a[starty][middle] > number)
			{
				end = middle-1;
			}
			else
			{
				start = middle +1;
			}
		}
		// not found here, then let's choose the max no more than number;
		if (start>endx)
		{
			// the biggest one is still less than number
		}
		else if (end<startx)
		{
			// less than smallest one
			goto ENDCODE;
		}
		else
		{
			if (a[starty][start]>number)
			{
				endx = start - 1;
			}
			else
			{
				endx = start;
			}
		}

		++ starty ;

		// top ->bottom

		start = starty;
		end = endy;
		middle = (start + end) >> 1;

		while (start <= end)
		{
			middle = (start + end) >> 1;

			if (a[middle][startx] == number)
			{
				find = true;
				posx = startx;
				posy = middle;
				goto ENDCODE;
			}
			else if (a[middle][startx] > number)
			{
				end = middle-1;
			}
			else
			{
				start = middle +1;
			}
		}
		// not found here, then let's choose the max no more than number;
		if (start>endy)
		{
			// the biggest one is still less than number
		}
		else if (end<starty)
		{
			// less than smallest one
			goto ENDCODE;
		}
		else
		{
			if (a[start][startx]>number)
			{
				endy = start - 1;
			}
			else
			{
				endy = start;
			}
		}

		++ startx ;
	}
	while (startx != endx || starty != endy);

ENDCODE:
	if (find)
	{
		return 0;
	}
	else 
	{
		return -1;
	}
}



int _tmain(int argc, _TCHAR* argv[])
{
	TwoDArray a(4, std::vector<unsigned int> (4));

	a[0][0] = 1;
	a[0][1] = 2;
	a[0][2] = 8;
	a[0][3] = 9;

	a[1][0] = 2;
	a[1][1] = 4;
	a[1][2] = 9;
	a[1][3] = 12;

	a[2][0] = 4;
	a[2][1] = 7;
	a[2][2] = 10;
	a[2][3] = 13;

	a[3][0] = 6;
	a[3][1] = 8;
	a[3][2] = 11;
	a[3][3] = 15;

	int posx = 0;
	int posy = 0;

	if ( 0 == FindNumber(a, 13, posx, posy))
	{
		std::cout << "Find Result x = " <<posx<<",y = "<<posy<<",in array = "<<a[posy][posx]<<std::endl;
	}
	else
	{
		std::cout << "404 not found." <<std::endl;
	}

	system("pause");
	return 0;
}

#50

主要的想法是每次2条边扫描 如果找到最佳答案最好 不然的话就可以过滤掉一部分数据

因为是两条边的扫描 可以让扫描后面的结果还是矩形， 就是里面重用的startx, endx, starty, endy.

扫描的过程用了折半 因为二维数组的缘故 写的有些乱