当前位置:网站首页>807. Maintain the urban skyline
807. Maintain the urban skyline
2022-07-06 16:08:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/
subject :
Give you a seat by n x n A city of blocks , Each block contains a cube building . I'll give you a subscript from 0 At the beginning n x n Integer matrix grid , among grid[r][c] Located in r That's ok c Of a row of buildings Height .
The city's The skyline When you look at the city from a distance , The external contour formed by all buildings . From the East 、 south 、 In the west 、 Observed in the four main directions of the North The skyline It may be different .
We are allowed to Any number of buildings Increase the height of Any increment ( The increment of different buildings may be different ) . The height is 0 The height of buildings can also be increased . However , Increased building height Can not affect Looking at the city from any major direction The skyline .
stay Don't change Cities observed from any major direction The skyline Under the premise of , Return to the building can add The sum of the maximum height increments .
Example 1:
Input :grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] Output :35 explain : The height of the building is shown in the center of the figure above . Draw the skyline in red from different directions . Without affecting the skyline , Increase the height of the building : gridNew = [ [8, 4, 8, 7], [7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3, 3] ] |
Example 2:
Input :grid = [[0,0,0],[0,0,0],[0,0,0]] Output :0 explain : Increasing the height of any building will change the skyline . |
Tips :
n == grid.length n == grid[r].length 2 <= n <= 50 0 <= grid[r][c] <= 100 |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
The title is more abstract , It took a little time to understand the picture ; Take a little more time to understand what to do
As shown in the figure , Explain the relationship between matrix and graph in one direction
It is equivalent to the building style that human eyes can see in front , Each color corresponds to a building height
Such a building height produces a waveform , The topic requirement is to fix the waveform to find the number of building heights that can be increased
Let's take a look at the expected new building height matrix :
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
The highest floor in each row of the original matrix , The highest floor of each column is :
The increase of floors is limited by rows , Column maximum value , So the new building height should be its min( That's ok , Column )
Like the first line , That's ok :8, Compare the columns separately :9,4,8,7, Minimum value
8,4,87
The second line , That's ok :7, Compare the columns separately :9,4,8,7, Minimum value
7,4,7,7
The following is the same , When we find this “ The formula ” after , Code implementation is easy
Method 1 、 Compare the maximum row and column values and take the minimum value
Use a one-dimensional array to store the maximum value of each row ; The maximum value of each column
structure min ( That's ok , Column ) The new matrix of
New matrix elements - Old matrix elements , Cumulative summation is the total increase in height
#define min(a,b) ( (a) < (b) ? (a) : (b) )
void dispRow(int *row, int col)
{
for(int i=0; i<col; i++)
printf("disp...row[%d]=%d\n", i, row[i]);
}
void fillMaxrowNum(int *maxrowNum, int **grid, int row, int col)
{
int max = 0;
for(int i=0; i<row; i++)
{
for(int j=0; j<col; j++)
{
if(max < grid[i][j])
max = grid[i][j];
}
maxrowNum[i] = max;
max = 0;
}
}
void fillMaxcolNum(int *maxcolNum, int **grid, int row, int col)
{
int max = 0;
for(int j=0; j<col; j++)
{
for(int i=0; i<row; i++)
{
if(max < grid[i][j])
max = grid[i][j];
}
maxcolNum[j] = max;
max = 0;
}
}
void fillgridNew(int **gridNew, int row, int col, int *maxrowNum, int *maxcolNum)
{
for(int i=0; i<row; i++)
{
for(int j=0; j<col; j++)
{
//printf("maxrowNum[%d]=%d, maxcolNum[%d]=%d\n", i, maxrowNum[i], j, maxcolNum[j]);
gridNew[i][j] = min(maxrowNum[i], maxcolNum[j]);
}
}
}
int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize){
int num = 0;
int row = gridSize;
int col = gridColSize[0];
int **gridNew = (int **)malloc(sizeof(int *) * row);
int i, j;
for(i=0; i<row; i++)
{
gridNew[i] = (int *)malloc(sizeof(int) * col);
}
int *maxrowNum = (int *)malloc(sizeof(int) * col);
int *maxcolNum = (int *)malloc(sizeof(int) * row);
fillMaxrowNum(maxrowNum, grid, row, col);
fillMaxcolNum(maxcolNum, grid, row, col);
// for(i=0; i<col; i++)
// {
// printf("maxrowNum[%d]=%d\n", i, maxrowNum[i]);
// }
// for(i=0; i<row; i++)
// {
// printf("maxcolNum[%d]=%d\n", i, maxcolNum[i]);
// }
fillgridNew(gridNew, row, col, maxrowNum, maxcolNum);
// for(i=0; i<row; i++)
// {
// for(j=0; j<col; j++)
// {
// printf("gridNew[%d][%d]=%d\n", i, j, gridNew[i][j]);
// }
// }
for(i=0; i<row; i++)
{
for(j=0; j<col; j++)
{
num += gridNew[i][j] - grid[i][j];
}
}
free(maxrowNum);
free(maxcolNum);
for(i=0; i<row; i++)
free(gridNew[i]);
free(gridNew);
return num;
}
边栏推荐
- E. Breaking the Wall
- Opencv learning log 12 binarization of Otsu method
- 想应聘程序员,您的简历就该这样写【精华总结】
- Quick to typescript Guide
- TCP's three handshakes and four waves
- Common configuration files of SSM framework
- Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
- B - Code Party (girls' competition)
- Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
- 最全编程语言在线 API 文档
猜你喜欢
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
【练习-7】Crossword Answers
PySide6 信号、槽
1005. Maximized array sum after K negations
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
Essai de pénétration (1) - - outils nécessaires, navigation
Information security - threat detection engine - common rule engine base performance comparison
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
C language is the watershed between low-level and high-level
随机推荐
信息安全-安全编排自动化与响应 (SOAR) 技术解析
Socket communication
Web based photo digital printing website
7-1 understand everything (20 points)
MySQL授予用户指定内容的操作权限
Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
Penetration test (7) -- vulnerability scanning tool Nessus
Raspberry pie csi/usb camera uses mjpg to realize web camera monitoring
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
Opencv learning log 15 count the number of solder joints and output
Research Report on market supply and demand and strategy of China's earth drilling industry
[exercise-3] (UVA 442) matrix chain multiplication
Gartner: five suggestions on best practices for zero trust network access
Opencv learning log 24 -- Hough transform 2 (maximum interval and minimum length can be limited)
If you want to apply for a programmer, your resume should be written like this [essence summary]
Borg Maze (BFS+最小生成树)(解题报告)
Find 3-friendly Integers
JS调用摄像头
【高老师软件需求分析】20级云班课习题答案合集
Opencv learning log 32 edge extraction