天津工程建设招标网站,网站建设框架构建,网站文件夹命名,aspnet网站开发案例看到这道题有些人很容易放弃#xff0c;其实这道题不是很难#xff0c;主要是题目长#xff0c;读的容易让人放弃#xff0c;但是
只要抓住一些性质就可以解决该问题。 本题中的定义放到图像里其实就是个金字塔#xff0c;下层的那部分比上一层的那部分#xff0c;长度加…
看到这道题有些人很容易放弃其实这道题不是很难主要是题目长读的容易让人放弃但是
只要抓住一些性质就可以解决该问题。 本题中的定义放到图像里其实就是个金字塔下层的那部分比上一层的那部分长度加2
并且该层那个长度区间内都是1才行。是个金字塔形状里都是1就行。 我们暴力的解法是什么呢其实就是遍历整个数组以每个数组下标为金子塔尖往下去统计有多少个金字塔那么这个的时间复杂度是1e8会超时所以我们得想别的方法去优化统计多少个金字塔这部分方面去想。那么我们再深入思考一下我们每次遍历的时候每次都要向下去统计金字塔那在统计的时候我们每次都要关注当前外层是否从上一层外层下来统计好之后我们怎么想呢目前已经知道我们的行数是确定的那么其实只要他的下面的外层可以延伸到金字塔尖的话我们就可以根据行数和外层可以延伸的长度那么我们就可以知道金字塔数量了
求每个塔尖的话都是可以这样的那么外层可以延伸的长度和行数我们怎么确定呢以正金字塔为例子一是预处理出来但是这样复杂度还是比较高那么我们是不是可以想一下从下往上遍历的话我们是不是就可以固定金字塔的高度了比如当前点是i,j那可以从i 2到i 1,i 1到i。那么高度我们已经确定好了怎么去确定可以延伸的长度呢
这个确实不好想我们目前推出来的只知道每一次长度相差为2只知道判断从左下角上来
从右下角上来但是不知道他中间那段能不能上来现在就是要确定中间那段如何让他上来
但是我们仔细想想的话根据前面的推导我们在向上推的话我们是不是只能推导到金字塔尖那么如果不是金子塔尖呢我们该怎么去推导呢其实到这里我们就已经知道了这是一个动态规划问题那么动态规划问题的本质是什么呢找子问题那么我们是不是可以想一下最顶上的金子塔尖是不是可以从下层的金字塔尖推上去是可以的我们只用知道左下角下方右下角上来就知道了去个min就可以了那么状态转移方程就是
f[i][j] min(f[i 1][j],min(f[i 1][j 1],f[i 1][j - 1])) 1;
class Solution {
public:int f[1100][1100];int countPyramids(vectorvectorint grid) {memset(f,0,sizeof(f));int n grid.size(),m grid[0].size();//i 1j//i 1,j - 1//i 1,j 1int ans 0;for(int i n - 1;i 0;i--){for(int j 0;j m;j){if(grid[i][j] 0) continue;if(j - 1 0 || j 1 m || i 1 n) continue;if(grid[i 1][j] 0 || grid[i 1][j - 1] 0 || grid[i 1][j 1] 0) continue;f[i][j] min(f[i 1][j],min(f[i 1][j 1],f[i 1][j - 1])) 1;ans f[i][j];}}//i - 1,j//i - 1,j - 1//i - 1,j 1memset(f,0,sizeof(f));for(int i 0;i n;i){for(int j 0;j m;j){if(grid[i][j] 0) continue;if(i - 1 0 || j 1 m || j - 1 0) continue;if(grid[i - 1][j] 0 || grid[i - 1][j - 1] 0 || grid[i - 1][j 1] 0) continue;f[i][j] min(f[i - 1][j],min(f[i - 1][j 1],f[i - 1][j - 1])) 1;ans f[i][j];}}return ans;}
};
