This is the 8th day of my participation in the More text Challenge. For details, see more text Challenge
Brick Wall (Question No. 554)
The title
In front of you is a rectangular brick wall made up of n rows of bricks. The bricks are of the same height (i.e., one unit height) but of different widths. The width of each row of bricks should add up to the same.
You will now draw a vertical line from the top down through the least number of bricks. If you draw a line that just goes through the edge of the brick, it doesn’t go through the brick. You can’t draw a line along one of the two vertical edges of the wall, which obviously doesn’t go through a brick.
You are given a two-dimensional array wall that contains information about the wall. Where wall[I] is an array representing the width of each brick from left to right. You need to figure out how to draw a line that minimizes the number of bricks it crosses and returns the number of bricks it crosses.
Example 1:
Input: wall = [,2,2,1 [1], [3,1,2], 31 [1], [2, 4], [3,1,2], [1,3,1,1]] output: 2Copy the codeExample 2:
Input: WALL = [[1],[1],[1]] Output: 3Copy the codeTip:
n == wall.length1 <= n <= 1041 <= wall[i].length <= 1041 <= sum(wall[i].length) <= 2 * 104- For each row
i，sum(wall[i])It should be the same 1 <= wall[i][j] <= 231 - 1
link
Leetcode-cn.com/problems/br…
explain
This problem, this problem is mainly the idea.
It’s a little hard to think about it, to get the final sum first, because the fixed length of each row is the same, so the final number must be in this interval, so I’m going to have to find it hard.
And since the lines can’t be on either side of the wall, to get rid of both boundary conditions, you have to get rid of both the zero and the maximum. So you start at 1 and you work your way to the second to last.
But this simply times out, because many numbers don’t make sense, such as a use case like 👇 :
[[99] 1999, 98 [2999], [3999] 97, 96 [4999], [5999] 95, 94 [6999], [7999] 93, 92 [8999], [91] 9999]Copy the codeIn fact, only the 18 numbers between 1 and 9 and 99991 and 99999 are valid, but we started from 1 and found 99999, which is nearly 10W more invalid searches, which is a waste of time and performance.
Is there a better way? Method, the author came up with another kind of violence is the solution to the optimization of a little bit about the 👆, not digital range one by one to find, but according to the start of the elements in an array traversal, above the 🌰, from 1 to 99999, down to 1 ~ 9 and 18 the number between 99991 ~ 99999, this save a lot of time, And you don’t need to count the total.
Is there an easier way? Yes, you can use an object, that is, a hash table to store the number of occurrences of each value, so it can be more convenient to draw a conclusion, the specific in the answer to explain, please be patient to see below.
Your own answer (forcible violence)
This is the first kind of solution 👆 said, forced violence, statistics of the wall how long, and then a brick a brick of statistics, has been trying to the last piece can be concluded.
var leastBricks = function(wall) {
var sum = wall[0].reduce((total, item) => item + total, 0)
var min = wall.length
for (let i = 1; i < sum; i++) {
var tmp = 0
for (const item of wall) {
var res = 0
for (let j = 0; j < item.length; j++) {
res += item[j]
if (res === i) {
break
} else if (res < i) {
continue
} else {
tmp++
break
}
}
}
min = Math.min(tmp, min)
}
return min
};
Copy the codeUnfortunately, we ran out of time on the 79th use case, which was:
[[99] 1999, 98 [2999], [3999] 97,... [998, 99002], [999, 99001], [1000, 99000]]Copy the codeBy 10W, it’s GG. Very reasonable.
Your own answer (normal violence)
Normal violence is simpler, a whole brick is searched to find the number of bricks that need to be crossed from the current position, and the minimum value can be obtained by counting each time. At the same time, we need to pay attention to the boundary conditions.
var leastBricks = function(wall) { var min = wall.length for (const item of wall) { var res = 0 for (let i = 0; i < item.length; i++) { var tmp = 0 if (i === item.length - 1) break res += item[i] for (const item2 of wall) { var tmpRes = 0 for (let j = 0; j < item2.length; j++) { tmpRes += item2[j] if (tmpRes === res) { break } else if (tmpRes < res) { continue } else { tmp++ break } } } min = Math.min(min, tmp) } } return min }Copy the codeLooking at these 4 layers of for loops is a bit cumbersome and requires a lot of code, but it consumes less memory because there are no extra variables added:
It can be inferred from this one thing, the amount of code is very big, but the memory footprint has been 100%, this shows one thing, other solution must be added a variable, and is not a small variables, takes up more memory, it can provide a direction for next, need to use a variable to store some things.
Your own answer (hash table)
We need something to store the data in order to make it easier to call it later.
-
The first thing is again to go through all the elements and get their gaps.
Take a row of bricks like this:
[1, 2, 2, 4] Copy the codeSo his gap is 1,3,5. If you look at it that way, it’s a lot more obvious.
Yeah, just count the gaps.
-
In the process of statistics, if there is this gap before, +1 will be added to the gap; if there is no gap, a new gap will be created with an initial value of 1, which means that this gap only appears once.
-
Finally, take the values of all the gaps, find the largest one, and then use the overall height of the wall, which is how many rows there are. Subtract the maximum gap from the number of rows to get the minimum number of blocks to cross.
If you don’t understand it, you can see here, for example, 🌰.
The wall could look like this 👇 :
[[1, 2, 2, 1], [3, 1, 2], [1, 3, 2], [2, 4], [3, 1, 2], [1, 3, 1, 1]]Copy the codeSo our so-called number of gaps is like this 👇 :
{1: 3, 2: 1, 3: 3, 4: 4, 5: 2,}Copy the codeSo the simple answer is, in the gap of length one brick there are three gaps in the entire wall, which means if you draw a line here, you have to go through six minus three bricks, which is three bricks, and the rest of the answer is the same.
Finally find the maximum 4, subtract the total height, you can get the minimum number of bricks to pass through is 2.
What if the use case looks like this?
[[1], [1], [1]Copy the codeDue to subject limit, cannot in the left side of the wall boundary line, so the line must be in the middle of the brick, so the line here can only through the three brick, if it is concluded that the number of cracks will be in accordance with the above method is an empty array, it is obviously unreasonable, so need to crack the number of objects, namely the hash table with a maximum value, also is the need to through all the brick, 0.
So you need to add an extra data in the gap table to prevent the gap table from being empty.
So the final code looks like this 👇 :
var leastBricks = function(wall) { var obj = { max: 0 } for (const line of wall) { var res = 0 for (let i = 0; i < line.length - 1; i++) { res += line[i] obj[res] = obj[res] ? obj[res] + 1 : 1 } } return wall.length - Math.max(... Object.values(obj)) }Copy the codeThe value of the hash table is the value of the hash table. The value of the hash table is the value of the hash table. The value of the hash table is the value of the hash table, and the value of the hash table is the value of the hash table. Unlike objects, you can use math.max () directly to compare all values.
Attached operation efficiency:
A better way
There is no
PS: To view past articles and titles, click on the link below:
Here’s 👇 by date
Front Brush path – Directory (Date classification)
After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇
Front brush problem path – Catalogue (Question type classification)
Those who are interested can also check out my personal homepage 👇
Here is RZ