刚刚参加了实习生笔试,最后是很有趣的一个算法题,回来没事就把代码写出来了。
题目大概:
一个数组:A[10]每个值代表矩形的高度,求最大的矩形大小。
比如A[10]= { 1, 2 , 4, 6, 0 ,5, 3 ,0 ,2 ,2};
1表示横坐标为1的单元高度为1; 6就表示横坐标为4的单元高度为6;
很明显最大是4和6组成的矩形,面积为8
下面是我写的程序:(不好意思,这个有bug,看最后一个改好的程序)
-
#include <stdio.h>
-
-
int find_max(int A[],int left,int right);
-
-
//only one zero
-
int main(int argc,char *argv[])
-
{
-
int ret;
-
-
int A[10] = {6,7,9,1,13,12,2,4,20,4};
-
-
ret = find_max(A,0,9);
-
-
printf("%d\n",ret);
-
-
return 0;
-
}
-
-
void change(int A[],int left,int right,int d0)
-
{
-
int i;
-
for(i=left;i<=right;i++)
-
{
-
A[i] = A[i] - d0;
-
printf("%d ",A[i]);
-
}
-
printf("\n\n");
-
}
-
-
int which_max(int a,int b,int c)
-
{
-
int tmp;
-
if(a>b)
-
tmp = a;
-
else
-
tmp = b;
-
-
if(c>tmp)
-
return c;
-
else
-
return tmp;
-
}
-
-
void min_height(int A[],int left,int right,int *i0,int *d0)
-
{
-
int i;
-
-
*i0 = left;
-
*d0= A[left];
-
-
for(i=left+1;i<=right;i++)
-
{
-
if(A[i]<*d0)
-
{
-
*i0 = i;
-
*d0 = A[i];
-
}
-
}
-
}
-
-
-
int find_max(int A[],int left,int right)
-
{
-
int i0,d0;
-
int base_max;
-
int left_max;
-
int right_max;
-
int max;
-
-
min_height(A,left,right,&i0,&d0);
-
-
base_max = (right - left + 1)*d0;
-
-
printf("find base_max = %d int %d to %d,middle is %d ,height %d\n",
-
base_max,left,right,i0,d0);
-
-
change(A,left,right,d0);
-
-
-
if(left == i0)
-
left_max = 0;
-
else
-
{
-
left_max = find_max(A,left,i0-1);
-
left_max = left_max + (i0-left)*d0;
-
}
-
-
if(right == i0)
-
right_max = 0;
-
else
-
{
-
right_max = find_max(A,i0+1,right);
-
right_max = left_max + (right-i0)*d0;
-
}
-
-
-
max = which_max(base_max,left_max,right_max);
-
printf("base_max %d ,left_max %d ,right_max %d max %d\n\n",
-
base_max,left_max,right_max,max);
-
-
return max;
-
}
下面是运行结果:(错误程序运行结果,看下面正确程序的运行结果)
-
root@archer:/work/user-lib/test# ./tencent
-
find base_max = 10 int 0 to 9,middle is 3 ,height 1
-
5 6 8 0 12 11 1 3 19 3
-
-
find base_max = 15 int 0 to 2,middle is 0 ,height 5
-
0 1 3
-
-
find base_max = 2 int 1 to 2,middle is 1 ,height 1
-
0 2
-
-
find base_max = 2 int 2 to 2,middle is 2 ,height 2
-
0
-
-
base_max 2 ,left_max 0 ,right_max 0 max 2
-
-
base_max 2 ,left_max 0 ,right_max 1 max 2
-
-
base_max 15 ,left_max 0 ,right_max 10 max 15
-
-
find base_max = 6 int 4 to 9,middle is 6 ,height 1
-
11 10 0 2 18 2
-
-
find base_max = 20 int 4 to 5,middle is 5 ,height 10
-
1 0
-
-
find base_max = 1 int 4 to 4,middle is 4 ,height 1
-
0
-
-
base_max 1 ,left_max 0 ,right_max 0 max 1
-
-
base_max 20 ,left_max 11 ,right_max 0 max 20
-
-
find base_max = 6 int 7 to 9,middle is 7 ,height 2
-
0 16 0
-
-
find base_max = 0 int 8 to 9,middle is 9 ,height 0
-
16 0
-
-
find base_max = 16 int 8 to 8,middle is 8 ,height 16
-
0
-
-
base_max 16 ,left_max 0 ,right_max 0 max 16
-
-
base_max 0 ,left_max 16 ,right_max 0 max 16
-
-
base_max 6 ,left_max 0 ,right_max 4 max 6
-
-
base_max 6 ,left_max 22 ,right_max 25 max 25
-
-
base_max 10 ,left_max 18 ,right_max 24 max 24
-
-
24
说明最大面积是 24,很显然就是 12和13组成的矩形。
正确的程序:
-
#include <stdio.h>
-
-
int find_max(int A[],int left,int right);
-
-
-
int main(int argc,char *argv[])
-
{
-
int ret;
-
-
int A[10] = {6,7,0,0,13,12,2,2,20,3};
-
// int A[] = {2,18,1};
-
-
ret = find_max(A,0,9);
-
-
printf("%d\n",ret);
-
-
return 0;
-
}
-
-
void change(int A[],int left,int right,int d0)
-
{
-
int i;
-
for(i=left;i<=right;i++)
-
{
-
A[i] = A[i] - d0;
-
printf("%d ",A[i]);
-
}
-
printf("\n");
-
}
-
-
int which_max(int a,int b,int c)
-
{
-
int tmp;
-
if(a>b)
-
tmp = a;
-
else
-
tmp = b;
-
-
if(c>tmp)
-
return c;
-
else
-
return tmp;
-
}
-
-
void min_height(int A[],int left,int right,int *i0,int *d0)
-
{
-
int i;
-
-
*i0 = left;
-
*d0= A[left];
-
-
for(i=left+1;i<=right;i++)
-
{
-
if(A[i]<*d0)
-
{
-
*i0 = i;
-
*d0 = A[i];
-
}
-
}
-
}
-
-
-
int find_max(int A[],int left,int right)
-
{
-
int i0,d0;
-
int base_max;
-
int left_max;
-
int right_max;
-
int max;
-
-
if(right == left)
-
{
-
printf("%d \n",A[left]);
-
return A[left];
-
}
-
-
min_height(A,left,right,&i0,&d0);
-
-
base_max = (right - left + 1)*d0;
-
-
change(A,left,right,0);
-
-
printf("find base_max = %d int %d to %d,middle is %d ,height %d\n",
-
base_max,left,right,i0,d0);
-
-
// change(A,left,right,d0);
-
-
-
if(left == i0)
-
left_max = d0;
-
else
-
{
-
left_max = find_max(A,left,i0-1);
-
// left_max = left_max + (i0-left)*d0;
-
}
-
-
if(right == i0)
-
right_max = d0;
-
else
-
{
-
right_max = find_max(A,i0+1,right);
-
// right_max = right_max + (right-i0)*d0;
-
}
-
-
-
max = which_max(base_max,left_max,right_max);
-
printf("base_max %d ,left_max %d ,right_max %d max %d\n\n",
-
base_max,left_max,right_max,max);
-
-
return max;
-
}
正确的运行结果如下:
root@archer:/work/user-lib/test# ./tencent
6 7 0 0 13 12 2 2 20 3
find base_max = 0 int 0 to 9,middle is 2 ,height 0
6 7
find base_max = 12 int 0 to 1,middle is 0 ,height 6
7
base_max 12 ,left_max 6 ,right_max 7 max 12
0 13 12 2 2 20 3
find base_max = 0 int 3 to 9,middle is 3 ,height 0
13 12 2 2 20 3
find base_max = 12 int 4 to 9,middle is 6 ,height 2
13 12
find base_max = 24 int 4 to 5,middle is 5 ,height 12
13
base_max 24 ,left_max 13 ,right_max 12 max 24
2 20 3
find base_max = 6 int 7 to 9,middle is 7 ,height 2
20 3
find base_max = 6 int 8 to 9,middle is 9 ,height 3
20
base_max 6 ,left_max 20 ,right_max 3 max 20
base_max 6 ,left_max 2 ,right_max 20 max 20
base_max 12 ,left_max 24 ,right_max 20 max 24
base_max 0 ,left_max 0 ,right_max 24 max 24
base_max 0 ,left_max 12 ,right_max 24 max 24
24
阅读(2796) | 评论(0) | 转发(0) |