黑马程序员技术交流社区

标题: 这么一道算法题，放出来大伙思考思考。。。 [打印本页]
作者: 炎星辰    时间: 2014-4-28 12:55
标题: 这么一道算法题，放出来大伙思考思考。。。
本帖最后由 炎星辰 于 2014-4-29 19:20 编辑

给你一个二维数组（比如是M*N的），把他们放入M*N的方格中，每个数字代表该方格的高度，这样就俯视就会形成凹凸不平，如果用这个形状存储水，凹的地方会有积水，请问它能存储多少水？
例如二维数组为：
9 9 9 9
3 0 0 9
7 8 9 6
时，答案是中间的0,0位置可以存储3（因为其外面最低是3，即“木桶效应”）个单位的水，因此答案为3+3=6
作者: 龙健    时间: 2014-4-28 16:32
看起来有意思，其实也不是很难，下面是我的代码；

  1. package cn.itheima.luntan;

  3. public class Demo4 {

  5.         /**9 9 9 9
  6.        3 0 0 9
  7.        7 8 9 6
  8.        算出外围最小的数，在用这个最小的数去减外围之外内的数，为负数，说明该处的值比外围最小数大，是不能存水的，
  9.        直接跳过这块板，也就是认为它装水为0，为正则相加得到能装多少水，
  10.        这是我的理解
  11.          * @param args
  12.          */
  13.         public static void main(String[] args) {
  14.                 // TODO Auto-generated method stub
  15.                 int min=100000;
  16.                 int x=0;
  17.                 int y=0;
  18.                 int num[][]={{9,3,7},{9,0,8},{9,0,9},{9,9,6}};
  19.                 for(int i=0;i<num.length;i++){
  20.                         for(int j=0;j<num[0].length;j++){
  21.                                 if(i==0 || i==num.length-1){
  22.                                         while(num[i][j]<min){
  23.                                                 min=num[i][j];
  24.                                                
  25.                                         }
  26.                                 }else{
  27.                                         if(num[i][0]<min){
  28.                                                 min=num[i][0];
  29.                                         }
  30.                                         if(num[i][num[0].length-1]<min){
  31.                                                 min=num[i][num[0].length-1];
  32.                                         }
  33.                                 }
  34.                         }
  35.                        
  36.                 }
  37.                 for(int n=1;n<num.length-1;n++){
  38.                        
  39.                         for(int m=1;m<num[0].length-1;m++){
  40.                                 x+=min-num[n][m];
  41.                                 if(x<0){
  42.                                         x=0;
  43.                                 }
  44.                                
  45.                                 y+=x;
  46.                                 x=0;
  47.                                
  48.                        
  49.                         }
  50.                 }
  51.                
  52.                 System.out.println(min);
  53.                 System.out.println(y);
  54.         }

  56. }
复制代码


作者: ZHAOWEI    时间: 2014-4-29 01:28
刚开始学习数组，学习学习
作者: 炎星辰    时间: 2014-4-29 11:08
龙健 发表于 2014-4-28 16:32
看起来有意思，其实也不是很难，下面是我的代码；

你题目没理解清楚，不一定是外围最小
如果对于二维数组（记作：数组1）：
9 9 9 9 9
9 1 5 1 9
9 5 6 5 9
9 2 5 2 9
9 0 9 9 9
按照你的程序结果是0，但实际应该是11。
验证如下，上面每个数字可添加的值如下（记作：数组2）：
0 0 0 0 0
0 4 0 4 0
0 0 0 0 0
0 0 0 3 0
0 0 0 0 0
将 数组1 + 数组2 后形成 数组3：
9 9 9 9 9
9 5 5 5 9
9 5 6 5 9
9 2 5 5 9
9 0 9 9 9
因为数组3已经不能储存水，因此答案为11

备注：我个人感觉，我的求证过程貌似提供了一个解决题目的思路



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2