current position:Home>[algorithm learning] 807 Maintain the city skyline (Java / C / C + + / Python / go / trust)
[algorithm learning] 807 Maintain the city skyline (Java / C / C + + / Python / go / trust)
2022-01-30 13:40:02 【White hat of the second leader】
- This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .
Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~
807. Keep the city skyline :
In a two-dimensional array grid in ,grid[i][j] Represents the height of a building located somewhere . We are allowed to increase any amount ( The number of different buildings may be different ) The height of the building . Height 0 It's also considered a building .
Last , From all four directions of the new array ( That's the top , Bottom , Left and right ) Watched “ The skyline ” Must be the same as the skyline of the original array . The skyline of the city is when viewed from a distance , The outer contour of a rectangle formed by all buildings . Please see the following example .
What is the maximum sum of the height of the building that can be increased ?
Examples 1
Input :
grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output :
35
explain :
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
From the vertical direction of the array ( That's the top , Bottom ) see “ The skyline ” yes :[9, 4, 8, 7]
From the horizontal ( On the left , On the right side ) see “ The skyline ” yes :[8, 7, 9, 3]
After heightening the building without affecting the skyline , The new array is as follows :
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
Copy code
Tips
- 1 < grid.length = grid[0].length <= 50.
- grid[i][j] The height range of is : [0, 100].
- A building occupies one grid[i][j]: In other words , They are 1 x 1 x grid[i][j] The cuboid of .
analysis
- First, understand what the skyline is : The skyline of the city is when viewed from a distance , The outer contour of a rectangle formed by all buildings . What affects the outline is the direction you look , The height of the tallest building in each row or column .
- So we raise the lower building in the direction we see to exactly the same height as the highest building , Without affecting the skyline , The maximum height that a building can increase .
- But the skyline in four directions can't affect , Think about it and you'll know up and down , The left and right skylines are consistent . Then we just need to increase the height of the building , Consider at the same time 2 Just a skyline , And we can only increase to a lower height without affecting .
- There are two steps , The first step is to calculate the skyline , The second step is to count the results .
Answer key
java
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int n = grid.length;
// Figure out the skyline
int[] rowMaxes = new int[n];
int[] colMaxes = new int[n];
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
rowMaxes[r] = Math.max(rowMaxes[r], grid[r][c]);
colMaxes[c] = Math.max(colMaxes[c], grid[r][c]);
}
}
int ans = 0;
// The result of the calculation is
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
ans += Math.min(rowMaxes[r], colMaxes[c]) - grid[r][c];
}
}
return ans;
}
}
Copy code
c
int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize){
// Figure out the skyline
int rowMaxes[gridSize];
int colMaxes[*gridColSize];
memset(rowMaxes, 0, sizeof(rowMaxes));
memset(colMaxes, 0, sizeof(colMaxes));
for (int r = 0; r < gridSize; ++r) {
for (int c = 0; c < *gridColSize; ++c) {
rowMaxes[r] = fmax(rowMaxes[r], grid[r][c]);
colMaxes[c] = fmax(colMaxes[c], grid[r][c]);
}
}
int ans = 0;
// The result of the calculation is
for (int r = 0; r < gridSize; ++r) {
for (int c = 0; c < *gridColSize; ++c) {
ans += fmin(rowMaxes[r], colMaxes[c]) - grid[r][c];
}
}
return ans;
}
Copy code
c++
class Solution {
public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
int n = grid.size();
// Figure out the skyline
vector<int> rowMaxes(n, 0);
vector<int> colMaxes(n, 0);
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
rowMaxes[r] = max(rowMaxes[r], grid[r][c]);
colMaxes[c] = max(colMaxes[c], grid[r][c]);
}
}
int ans = 0;
// The result of the calculation is
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c];
}
}
return ans;
}
};
Copy code
python
class Solution:
def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
n = len(grid)
# Figure out the skyline
rowMaxes = [0] * n
colMaxes = [0] * n
for r in range(n):
for c in range(n):
rowMaxes[r] = max(rowMaxes[r], grid[r][c])
colMaxes[c] = max(colMaxes[c], grid[r][c])
ans = 0
# The result of the calculation is
for r in range(n):
for c in range(n):
ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
return ans
Copy code
go
func maxIncreaseKeepingSkyline(grid [][]int) int {
n := len(grid)
// Figure out the skyline
rowMaxes := make([]int, n)
colMaxes := make([]int, n)
for r := 0; r < n; r++ {
for c := 0; c < n; c++ {
rowMaxes[r] = max(rowMaxes[r], grid[r][c])
colMaxes[c] = max(colMaxes[c], grid[r][c])
}
}
ans := 0
// The result of the calculation is
for r := 0; r < n; r++ {
for c := 0; c < n; c++ {
ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
}
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
Copy code
rust
impl Solution {
pub fn max_increase_keeping_skyline(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
// Figure out the skyline
let mut rowMaxes = vec![0; n];
let mut colMaxes = vec![0; n];
for r in 0..n {
for c in 0..n {
rowMaxes[r] = rowMaxes[r].max(grid[r][c]);
colMaxes[c] = colMaxes[c].max(grid[r][c]);
}
}
let mut ans = 0;
// The result of the calculation is
for r in 0..n {
for c in 0..n {
ans += rowMaxes[r].min(colMaxes[c]) - grid[r][c];
}
}
return ans;
}
}
Copy code
Original title transmission gate :https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/
Welcome to discuss in the comment area , Nuggets officials will be in Digging force Star Program After the event , Draw... In the comment area 100 Around the Nuggets , For details of the lucky draw, see the activity article
copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201301340005817.html
The sidebar is recommended
- Python code reading (Part 44): find the location of qualified elements
- Elegant implementation of Django model field encryption
- 40 Python entry applet
- Pandas comprehensive application
- Chapter 2: Fundamentals of python-3 character string
- Python pyplot draws a parallel histogram, and the x-axis value is displayed in the center of the two histograms
- [Python crawler] detailed explanation of selenium from introduction to actual combat [1]
- Curl to Python self use version
- Python visualization - 3D drawing solutions pyecharts, Matplotlib, openpyxl
- Use python, opencv's meanshift and CAMSHIFT algorithms to find and track objects in video
guess what you like
-
Using python, opencv obtains and changes pixels, modifies image channels, and trims ROI
-
[Python data collection] university ranking data collection
-
[Python data collection] stock information collection
-
Python game development, pyGame module, python takes you to realize a magic tower game from scratch (2)
-
Python solves the problem of suspending execution after clicking the mouse in CMD window (fast editing mode is prohibited)
-
[Python from introduction to mastery] (II) how to run Python? What are the good development tools (pycharm)
-
Python type hints from introduction to practice
-
Python notes (IX): basic operation of dictionary
-
Python notes (8): basic operations of collections
-
Python notes (VII): definition and use of tuples
Random recommended
- Python notes (6): definition and use of lists
- Python notes (V): string operation
- Python notes (IV): use of functions and modules
- Python notes (3): conditional statements and circular statements
- Python notes (II): lexical structure
- Notes on python (I): getting to know Python
- [Python data structure series] - tree and binary tree - basic knowledge - knowledge point explanation + code implementation
- [Python daily homework] Day7: how to combine two dictionaries in an expression?
- How to implement a custom list or dictionary in Python
- 15 advanced Python tips for experienced programmers
- Python string method tutorial - how to use the find() and replace() functions on Python strings
- Python computer network basics
- Python crawler series: crawling global airport information
- Python crawler series: crawling global port information
- How to calculate unique values using pandas groupby
- Application of built-in distribution of Monte Carlo simulation SciPy with Python
- Gradient lifting method and its implementation in Python
- Pandas: how to group and calculate by index
- Can you create an empty pandas data frame and fill it in?
- Python basic exercises teaching! can't? (practice makes perfect)
- Exploratory data analysis (EDA) in Python using SQL and Seaborn (SNS).
- Turn audio into shareable video with Python and ffmpeg
- Using rbind in python (equivalent to R)
- Pandas: how to create an empty data frame with column names
- Talk about quantifying investment using Python
- Python, image restoration in opencv - CV2 inpaint
- Python notes (14): advanced technologies such as object-oriented programming
- Python notes (13): operations such as object-oriented programming
- Python notes (12): inheritance such as object-oriented programming
- Chapter 2: Fundamentals of python-5 Boolean
- Python notes (11): encapsulation such as object-oriented programming
- Python notes (10): concepts such as object-oriented programming
- Gradient lifting method and its implementation in Python
- Van * Python | simple crawling of a site course
- Chapter 1 preliminary knowledge of pandas (list derivation and conditional assignment, anonymous function and map method, zip object and enumerate method, NP basis)
- Nanny tutorial! Build VIM into an IDE (Python)
- Fourier transform of Python OpenCV image processing, lesson 52
- Introduction to python (III) network request and analysis
- China Merchants Bank credit card number recognition project (Part I), python OpenCV image processing journey, Part 53
- Python practice - capture 58 rental information and store it in MySQL database