最长滑道问题(非递归,C++)

这是爱奇艺的一道算法题。

题目描述请参考博客http://blog.csdn.net/sinat_30186009/article/details/52356053,在此表示感谢。

基本思路参考了以上文章,但是上面文章中的算法是java版,这是次要的,主要的问题是算法用的是原始递归思想,这样会造成计算量及其大,时间复杂度为O(n^2)。

本文旨在用C++语言解决上述问题,并且在递归的基础上进行改进,使得时间复杂度降为O(n)。其中n为高度矩阵的元素个数即row*col。

代码说明:

 输入:

  高度矩阵行数: row

  高度矩阵列数: col

  高度矩阵     : dots

 输出:

  最长滑道值:LargestSlideValue

  滑道长度矩阵:dotsLength,该矩阵最大值到最小值的路径即为最长滑道路径

函数findLargestSlide()调用次数:Call_Of_findLargestSlide()

  1 #include <iostream>
  2 #include <vector>
  3 #include <iomanip>
  4 
  5 using namespace std;
  6 
  7 //减少寻找过程(前面几种算法都会重复计算,本算法记录每个点的最大路径,下次寻找到该点时直接加即可!降低时间复杂度关键思想)
  8 int countfindLargestSlide=0;//用于计录函数findLargestSlide调用次数
  9 //寻找最长滑道路径(前后两点不等高)
 10 int findLargestSlide(int x,int y,const vector<vector<int> >& dots,vector<vector<int> >& dotsLength)
 11 {
 12     countfindLargestSlide++;
 13 
 14     int left=y-1;
 15     int right=y+1;
 16     int up=x-1;
 17     int down=x+1;
 18 
 19     int left_value=0;
 20     int right_value=0;
 21     int up_value=0;
 22     int down_value=0;
 23 
 24     if(left>=0&&dots[x][left]<dots[x][y]){
 25         if(0==dotsLength[x][left])//如果为0,表示该点没有被计算过,因此需要调用findLargestSlide来寻找基于该点的最长滑道
 26             dotsLength[x][left]=left_value=findLargestSlide(x,left,dots,dotsLength);
 27         else  //如果不为0,表示该点已经被计算过,不用重新计算,下同(降低时间复杂度关键代码)
 28             left_value=dotsLength[x][left];
 29     }
 30 
 31     if(right<=(int)dots[0].size()-1&&dots[x][right]<dots[x][y]){
 32         if(0==dotsLength[x][right])
 33             dotsLength[x][right]=right_value=findLargestSlide(x,right,dots,dotsLength);
 34         else
 35             right_value=dotsLength[x][right];
 36     }
 37 
 38     if(up>=0&&dots[up][y]<dots[x][y]){
 39         if(0==dotsLength[up][y])
 40             dotsLength[up][y]=up_value=findLargestSlide(up,y,dots,dotsLength);
 41         else
 42             up_value= dotsLength[up][y];
 43     }
 44 
 45     if(down<=(int)dots.size()-1&&dots[down][y]<dots[x][y]){
 46         if(0==dotsLength[down][y])
 47             dotsLength[down][y]=down_value=findLargestSlide(down,y,dots,dotsLength);
 48         else
 49             down_value= dotsLength[down][y];
 50     }
 51 
 52     int max1=left_value>=right_value?left_value:right_value;
 53     int max2=up_value>=down_value?up_value:down_value;
 54     int max=max1>=max2?max1:max2;
 55 
 56     dotsLength[x][y]=max+1;//加上寻找点自身的路径长度1
 57 
 58     return dotsLength[x][y];
 59 }
 60 
 61 
 62 int main()
 63 {
 64     //行和列
 65     int row,col=0;
 66     cout<<"please input row and col: ";
 67     cin>>row>>col;
 68     cout << "row= "<<row<<" "<<"col= "<<col << endl;
 69     cout<<"please input dotsMatrix:"<<endl;
 70     //矩阵(每点代表一个高度)
 71     vector<vector<int> > dots(row,vector<int>(col,0));
 72     //输入矩阵
 73     for(vector<int>& valrow:dots)
 74         for(int & valcol:valrow)
 75             cin>>valcol;
 76 
 77     //矩阵,记录每个点对应的滑道长度
 78     vector<vector<int> > dotsLength(row,vector<int>(col,0));
 79     cout<<"--------------------"<<endl;
 80     //输出矩阵以验证矩阵确实输入正确
 81     cout<<"dots:"<<endl;
 82     for(int i=0;i<row;i++)
 83     {
 84         for(int j=0;j<col;j++)
 85             cout<<setw(4)<<dots[i][j];
 86         cout<<endl;
 87     }
 88 
 89     int max_value=0;
 90     for(int i=0;i<row;i++)
 91     {
 92         for(int j=0;j<col;j++)
 93         {
 94             int current_value=findLargestSlide(i,j,dots,dotsLength);
 95             if(current_value>max_value)
 96             {
 97                 max_value=current_value;
 98             }
 99         }
100     }
101 
102     cout<<"--------------------"<<endl;
103     cout<<"LargestSlideValue= "<<max_value<<endl;
104     cout<<"--------------------"<<endl;
105     //输出dotsLength,从该矩阵中可以方便直观地看出滑动路线(可能有多条,从最大值到最小值)
106     cout<<"dotsLength:"<<endl;
107     for(int i=0;i<row;i++)
108     {
109         for(int j=0;j<col;j++)
110             cout<<setw(4)<<dotsLength[i][j];
111         cout<<endl;
112     }
113     cout<<"--------------------"<<endl;
114     //输出调用findLargestSlide函数的次数,本程序时间复杂度为线性复杂度:O(n)
115     cout<<"Call_Of_findLargestSlide(): "<<countfindLargestSlide<<endl;
116 
117     return 0;
118 }

简单对比一下改进前后的效果:

测试样例:

改进前:

改进后:

可以看出,最长滑道长度为17,改进前,函数findLargestSlide()调用841次,改进后为54次,因此我们用递归算法时一定要考虑是否可以优化。

滑道长度矩阵dotsLength中的每个值代表从该点开始滑下,可获得的滑道最长值。长度为17的最长滑道标注如下图:

意即从高度为23的顶端(dotsLength中17对应的点)沿着图中蓝线一直滑到高度为1的底部(dotsLength中1对应的点)。当然还有其他长度的滑道,可以从图中方便地找出来。

最后,关于时间复杂度的具体数值,时间复杂度在改进前后分别为O(n^2)和O(n),但需要注意的是,即使同样维度的矩阵,数值不同的时候函数findLargestSlide()的调用次数可能不同,但时间复杂度量级是相同的。

时间复杂度简要分析:

  改进前:粗略计算应为30*30,但是不可能每个点都会讲所有点递归计算一遍,因此最终的结果841要小于30*30=900。

  改进后:时间复杂度应该为30呀?为啥这里比30大呢?因为在main()函数内,每个元素均要计算基于它的最长滑道,均要调用一次findLargestSlide()函数,总共30个点,因此调用30次。但是要注意的是,主函数计算基于每个值的最长滑道时,并不知道这个值之前有没有被计算过,它只有按照main()函数的流程再次调用findLargestSlide()函数,进入之后才知道是否被计算过,因此要加上前面计算其他点时递归计算过该点的次数(每个点最多一次,可能0次),因此所以就比30大了,但绝对不会超过30*2-1=59(这种情况发生在计算每个点的最长滑道时都发现之前被递归计算过,除了第一个点)。因此精确的时间复杂度为:最好时为n次,最坏时为2n-1次。

举例:

测试数据(一种最坏情况):

另一种最坏情况:

以第一种最坏情况为例(都是一样的),第一次计算30对应的最长滑道时,已经递归计算了其他点的最长滑道(总共计算了30次),然而main()函数并不知道这一点呀,因此继续计算29对应的最长滑道,进去发现,哎呀!已经计算过了那太好了(但是记得从main()函数调用findLargestSlide()也要计数,加1次),同样,28,27,26,...,3,2,1,直到计算完毕,总共调用findLargestSlide()函数的次数为30+29*1=59次。

测试数据(一种最好情况):

在上面的最好情况下,每次只计算一个点对应的最长滑道,不会出现递归计算,总共调用findLargestSlide()函数的次数为30次(均为main()函数调用)。

就到这里啦,有不足的地方敬请指正,欢迎交流。

附注(文章https://blog.csdn.net/sinat_30186009/article/details/52356053内容)

1.题目描述 Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子  1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。 输入输出: Input 输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。 Output 输出最长区域的长度。 Sample Input 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 Sample Output 25 2.思路分析 这道题实际上就是要求从最大值到最小值所能经过的最长路径,那么我们可以这么考虑,对于每一个坐标点,它到最小值的必定有一个最长路径len,那么我们只要找出所有坐标点到最小值的最长路径,然后再从中找到最大值即为所求答案。这样,我们的问题就只剩下如何求一个坐标点到最小值的最大长度len,很快我们发现每个坐标点的len必定是其上下左右坐标的len+1,这样我们就可以使用递归来解决这个问题了,详细看代码。 3.代码实现 1 import java.util.Scanner; 2 3 public class Main { 4 public static void main(String[] args) { 5 Scanner sc=new Scanner(System.in); 6 String line=sc.nextLine(); 7 String[] str=line.split(" "); 8 int row=Integer.parseInt(str[0]); 9 int column=Integer.parseInt(str[1]); 10 int[][] matrix=new int[row][column]; 11 for(int i=0;imax_value){ 12 max_value=current_value; 13 } 14 } 15 } 16 17 System.out.println(max_value); 18 } 19 20 private static int maxLength(int x,int y,int[][] matrix) { 21 22 int left=y-1; 23 int right=y+1; 24 int up=x-1; 25 int down=x+1; 26 int left_value=0; 27 int right_value=0; 28 int up_value=0; 29 int down_value=0; 30 if(left>=0&&matrix[x][left]=0&&matrix[up][y]right_value?left_value:right_value; 31 int max2=up_value>down_value?up_value:down_value; 32 33 return (max1>max2?max1:max2)+1; 34 } 35 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

算法模板——线段树6(二维线段树:区域加法+区域求和)(求助phile)

实现功能——对于一个N×M的方格,1:输入一个区域,将此区域全部值作加法;2:输入一个区域,求此区域全部值的和 其实和一维线段树同理,只是不知道为什么速度比想象...

48850
来自专栏zingpLiu

机器学习之线性代数

  完整内容已上传到github:https://github.com/ZingP/machine-learning/tree/master/linear_al...

20310
来自专栏祥子的故事

tensorflow | 重新学习 | 了解graph 和 Session

38180
来自专栏xingoo, 一个梦想做发明家的程序员

动态规划基本要素

动态规划性质: 1  最优子结构性质  2 子问题重叠性质 ----->该问题可用动态规划算法求解的基本要素 1 最优子结构 当问题的最优解包含了其子问题的最优...

223100
来自专栏机器之心

教程 | 在Python和TensorFlow上构建Word2Vec词嵌入模型

选自adventuresinmachinelearning 机器之心编译 参与:李诗萌、刘晓坤 本文详细介绍了 word2vector 模型的模型架构,以及 T...

49670
来自专栏每日一篇技术文章

OpenGL ES _ 着色器_纹理图像

玩过游戏的同学们,都知道在游戏人物身上穿的那个叫皮肤,专业点将那个就叫做纹理图像。GLSL 支持在顶点和片段着色器使用纹理图像。

22330
来自专栏CVer

TensorFlow从入门到精通 | 01 简单线性模型(上篇)

[TensorFlow从入门到精通] 01 简单线性模型(上)介绍了TensorFlow如何加载MNIST、定义数据维度、TensorFlow图、占位符变量和O...

11120
来自专栏决胜机器学习

有趣的算法(一)——n阶层尾部有几个0

有趣的算法(一)——n阶层尾部有几个0 (原创内容,转载请注明来源,谢谢) 最近在网上看到好几次这个题目,觉得挺有意思,则准备用PHP进行实现。 1、题目 ...

38560
来自专栏祥子的故事

tensorflow | 维度转换

42350
来自专栏深度学习之tensorflow实战篇

tensorflow之tf.placeholder 与 tf.Variable区别对比

二者的主要区别在于 Variable:主要是用于训练变量之类的。比如我们经常使用的网络权重,偏置。 值得注意的是Variable在声明是必须赋予初始值。在训...

34040

扫码关注云+社区

领取腾讯云代金券