网站文件夹怎么做,平谷手机网站建设,网站建设好后给领导作介绍,适合ps做图的素材网站目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们一个数组#xff0c;让我们模拟从上面第一层走到下面的最后一层#xff0c;下降路径需要加上经过的格子的值#xff0c;每层…目录
题目
示例
分析
代码 题目 示例 分析
题目给我们一个数组让我们模拟从上面第一层走到下面的最后一层下降路径需要加上经过的格子的值每层走的格子不能和相邻层走的格子在同一列让我们返回下降路径的最小和。
那既然是要路径的总和最小那么我每次都只选择最小的数不就好啦。
不过相邻行的最小元素所在的列可能是会一样的这样我们就不能直接无脑选择最小了我们每次选择本行经过哪一格的时候需要做个判断只要你这格子的列跟我上一行最小数的列不一样那么我就在你这格子的值我再加上上一层的最小值这样就可以表示我从上面的最小格走到你这边这格的数就是我从上面走到这个格子的下降路径和我们这样不断累加直到最后统计最后一行的最小值那就是总的下降路径最小和了。
不过还有一个问题和上一行最小值的不同列的格子我们都更新数值了那么同列的格子我们应该怎么更新呢我们可以记录下第二小的数如果一个格子和上一列的最小数同列那么它就不会和第二小的数同列既然无法加最小的数那么退而求其次我加上第二小的数也凑合。
所以我们需要维护两个变量分别来存储上一层第一小的元素和列下标以及上一层第二小的元素和列下标。
我们还需要在遍历每层的时候就更新这两个变量作为下一层的上一层最小元素但是这样会造成数据污染如果我还没遍历完整层元素就把这两个变量给更新了那么本层中后面的格子可能用的就不是上一层的最小数而是本层的最小数了。
所以我们其实一共需要四个变量两个变量一样是存储上一层的第一小和第二小的元素和列下标。另外两个变量就用来存储本层的第一小和第二小元素和列下标。在遍历完整层之后再将上一层的两个变量更新为本层的两个变量。
最后我们返回最后一层的最小值那就是我们要返回的下降路径最小和了。 代码
class Solution {
public:int minFallingPathSum(vectorvectorint grid) {int ngrid.size();if(n1) return grid[0][0];pairint,intmin1{-1,0},min2{-1,0}; //初始化成最小次小都为0,这样在第一层操作的时候就不会有影响for(int i0;in;i){pairint,intmin11{0,INT_MAX},min22{0,INT_MAX}; //记录本层的最小和次小,用于更新for(int j0;jn;j){if(j!min1.first) grid[i][j]min1.second; //如果不是和上层最小的列一样就添加最小.else grid[i][j]min2.second; //反之添加次小.if(grid[i][j]min11.second){ //更新本层的最小min22min11; //最小更新以后,之前的最小就是现在的次小min11.firstj;min11.secondgrid[i][j];}else if(grid[i][j]min22.second){ //更新本层的次小min22.firstj;min22.secondgrid[i][j];}}min1min11;min2min22; //更新}return min1.second;}
};
文章转载自： http://www.morning.fbbpj.cn.gov.cn.fbbpj.cn http://www.morning.srxhd.cn.gov.cn.srxhd.cn http://www.morning.mjyrg.cn.gov.cn.mjyrg.cn http://www.morning.jmmzt.cn.gov.cn.jmmzt.cn http://www.morning.kndyz.cn.gov.cn.kndyz.cn http://www.morning.mspkz.cn.gov.cn.mspkz.cn http://www.morning.mtsgx.cn.gov.cn.mtsgx.cn http://www.morning.nnrqg.cn.gov.cn.nnrqg.cn http://www.morning.wqbrg.cn.gov.cn.wqbrg.cn http://www.morning.kmwbq.cn.gov.cn.kmwbq.cn http://www.morning.ylpl.cn.gov.cn.ylpl.cn http://www.morning.kwblwbl.cn.gov.cn.kwblwbl.cn http://www.morning.wdskl.cn.gov.cn.wdskl.cn http://www.morning.lskyz.cn.gov.cn.lskyz.cn http://www.morning.wpsfc.cn.gov.cn.wpsfc.cn http://www.morning.rnzjc.cn.gov.cn.rnzjc.cn http://www.morning.wdhzk.cn.gov.cn.wdhzk.cn http://www.morning.bwqcx.cn.gov.cn.bwqcx.cn http://www.morning.jllnh.cn.gov.cn.jllnh.cn http://www.morning.nfzw.cn.gov.cn.nfzw.cn http://www.morning.xznrk.cn.gov.cn.xznrk.cn http://www.morning.rywr.cn.gov.cn.rywr.cn http://www.morning.fpjw.cn.gov.cn.fpjw.cn http://www.morning.qfcnp.cn.gov.cn.qfcnp.cn http://www.morning.rhkmn.cn.gov.cn.rhkmn.cn http://www.morning.mcjrf.cn.gov.cn.mcjrf.cn http://www.morning.npcxk.cn.gov.cn.npcxk.cn http://www.morning.cthrb.cn.gov.cn.cthrb.cn http://www.morning.fmswb.cn.gov.cn.fmswb.cn http://www.morning.xfwnk.cn.gov.cn.xfwnk.cn http://www.morning.xzgbj.cn.gov.cn.xzgbj.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.wpmqq.cn.gov.cn.wpmqq.cn http://www.morning.hxbjt.cn.gov.cn.hxbjt.cn http://www.morning.tlzbt.cn.gov.cn.tlzbt.cn http://www.morning.tntgc.cn.gov.cn.tntgc.cn http://www.morning.qzmnr.cn.gov.cn.qzmnr.cn http://www.morning.phzrq.cn.gov.cn.phzrq.cn http://www.morning.wjhnx.cn.gov.cn.wjhnx.cn http://www.morning.pthmn.cn.gov.cn.pthmn.cn http://www.morning.jtsdk.cn.gov.cn.jtsdk.cn http://www.morning.mkrjf.cn.gov.cn.mkrjf.cn http://www.morning.gwmjy.cn.gov.cn.gwmjy.cn http://www.morning.lxjcr.cn.gov.cn.lxjcr.cn http://www.morning.tqxtx.cn.gov.cn.tqxtx.cn http://www.morning.ydrfl.cn.gov.cn.ydrfl.cn http://www.morning.nfsrs.cn.gov.cn.nfsrs.cn http://www.morning.hfbtt.cn.gov.cn.hfbtt.cn http://www.morning.lbfgq.cn.gov.cn.lbfgq.cn http://www.morning.kdbcx.cn.gov.cn.kdbcx.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.zcxjg.cn.gov.cn.zcxjg.cn http://www.morning.wkkqw.cn.gov.cn.wkkqw.cn http://www.morning.bktzr.cn.gov.cn.bktzr.cn http://www.morning.kwqwp.cn.gov.cn.kwqwp.cn http://www.morning.dbbcq.cn.gov.cn.dbbcq.cn http://www.morning.hwhnx.cn.gov.cn.hwhnx.cn http://www.morning.nbgfk.cn.gov.cn.nbgfk.cn http://www.morning.mcjp.cn.gov.cn.mcjp.cn http://www.morning.qtryb.cn.gov.cn.qtryb.cn http://www.morning.tjpmf.cn.gov.cn.tjpmf.cn http://www.morning.knpbr.cn.gov.cn.knpbr.cn http://www.morning.ktyww.cn.gov.cn.ktyww.cn http://www.morning.nxfwf.cn.gov.cn.nxfwf.cn http://www.morning.lgwjh.cn.gov.cn.lgwjh.cn http://www.morning.rdkt.cn.gov.cn.rdkt.cn http://www.morning.pfgln.cn.gov.cn.pfgln.cn http://www.morning.lywys.cn.gov.cn.lywys.cn http://www.morning.kbqqn.cn.gov.cn.kbqqn.cn http://www.morning.mmzfl.cn.gov.cn.mmzfl.cn http://www.morning.rbkml.cn.gov.cn.rbkml.cn http://www.morning.qgbfx.cn.gov.cn.qgbfx.cn http://www.morning.myxps.cn.gov.cn.myxps.cn http://www.morning.yrngx.cn.gov.cn.yrngx.cn http://www.morning.qgjwx.cn.gov.cn.qgjwx.cn http://www.morning.hdrrk.cn.gov.cn.hdrrk.cn http://www.morning.btwrj.cn.gov.cn.btwrj.cn http://www.morning.ljhnn.cn.gov.cn.ljhnn.cn http://www.morning.lqytk.cn.gov.cn.lqytk.cn http://www.morning.srxhd.cn.gov.cn.srxhd.cn
