当前位置:网站首页>[daily problem insight] prefix and -- count the number of fertile pyramids in the farm
[daily problem insight] prefix and -- count the number of fertile pyramids in the farm
2022-07-07 00:26:00 【Code Fox】
️ Winter vacation xinkeng —— Code Fox's daily notes
The winter vacation is about to expire
2088. Count the number of fertile pyramids in the farm -Hard( Prefix and quick detection array )- The first 66 Biweekly competition question 4
There is one Rectangular grid A shapeless farm , Divided into m
That's ok n
Cell of column . Each grid is either Fertile ( use 1
Express ), Or poor Of ( use 0
Express ). All and grids outside the grid are considered barren .
On the farm The pyramid The area is defined as follows :
- Number of grids in the area Greater than
1
And all the grids are Fertile . - The pyramid Apex It's this pyramid The top Lattice of . The height of the pyramid is the number of rows it covers . Make
(r, c)
It is the top of the pyramid and its height ish
, Then any grid contained in the pyramid area(i, j)
Need to meetr <= i <= r + h - 1
Andc - (i - r) <= j <= c + (i - r)
.
One Inverted Pyramid Similar definitions are as follows :
- Number of grids in the area Greater than
1
And all the grids are Fertile . - Inverted pyramid Apex It's the inverted pyramid At the bottom Lattice of . The height of the inverted pyramid is the number of rows it covers . Make
(r, c)
It is the top of the pyramid and its height ish
, Then any grid contained in the pyramid area(i, j)
Need to meetr - h + 1 <= i <= r
Andc - (r - i) <= j <= c + (r - i)
.
class Solution {
public int countPyramids(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
for(int i=0;i<m;i++){
for(int k=0;k<n;k++){
if(k!=0){
grid[i][k]+=grid[i][k-1];
}
}
}
int ans=0;
for(int x=0;x<m;x++){
for(int y=0;y<n;y++){
int h=1;
if(y==0&&grid[x][y]==0){
continue;
}
if(y!=0&&grid[x][y]-grid[x][y-1]==0){
continue;
}
while(x+h<m&&y+h<n&&y-h>=0){
int sum=0;
if(y-h==0){
sum=grid[x+h][y+h];
}
else{
sum=grid[x+h][y+h]-grid[x+h][y-h-1];
}
if(sum==2*h+1){
ans++;
h++;
}
else{
break;
}
}
h=1;
while(x-h>=0&&y+h<n&&y-h>=0){
int sum=0;
if(y-h==0){
sum=grid[x-h][y+h];
}
else{
sum=grid[x-h][y+h]-grid[x-h][y-h-1];
}
if(sum==2*h+1){
ans++;
h++;
}
else{
break;
}
}
}
}
return ans;
}
}
ending
Title source : Power button (LeetCode) link :https://leetcode-cn.com/problems
️ Focus on the author , Take you to brush the questions , Learn the most commonly used algorithm skills from simple algorithm problems ( Winter vacation every day )
️ Pay attention to the author's questions —— Simple to advanced , Let you unknowingly become a ruthless problem brushing machine , If you have any questions, please send a private letter
边栏推荐
猜你喜欢
Racher integrates LDAP to realize unified account login
St table
基于SSM框架的文章管理系统
Jenkins' user credentials plug-in installation
@TableId can‘t more than one in Class: “com.example.CloseContactSearcher.entity.Activity“.
How engineers treat open source -- the heartfelt words of an old engineer
X.509 certificate based on go language
How can computers ensure data security in the quantum era? The United States announced four alternative encryption algorithms
2022/2/11 summary
37頁數字鄉村振興智慧農業整體規劃建設方案
随机推荐
2021 SASE integration strategic roadmap (I)
C语言输入/输出流和文件操作【二】
Leecode brush question record sword finger offer 58 - ii Rotate string left
数据运营平台-数据采集[通俗易懂]
JWT signature does not match locally computed signature. JWT validity cannot be asserted and should
Pytest multi process / multi thread execution test case
pytest多进程/多线程执行测试用例
智能运维应用之道,告别企业数字化转型危机
A way of writing SQL, update when matching, or insert
量子时代计算机怎么保证数据安全?美国公布四项备选加密算法
GPIO简介
TypeScript增量编译
Leecode brush question record sword finger offer 56 - ii Number of occurrences of numbers in the array II
DAY ONE
Quickly use various versions of PostgreSQL database in docker
app通用功能測試用例
Three application characteristics of immersive projection in offline display
St table
Automatic test tool katalon (WEB) test operation instructions
Jenkins' user credentials plug-in installation