This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 554 on LeetCode. Brick wall.

Tag: Hash table

You have a rectangular brick wall with n rows of bricks in front of you.

The bricks are the same height (i.e. one unit high) but have different widths. The sum of the width of each row of bricks is equal.

You now want to draw a vertical line from the top down through the fewest bricks.

If you draw a line that only goes along 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 the line in such a way as to minimize the number of bricks it crosses and return 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 code

Example 2:

Input: wall = [[1],[1],[1] output: 3Copy the code

Tip:

  • n == wall.length
  • 1 <= n <=
    1 0 4 10^4
  • 1 <= wall[i].length <=
    1 0 4 10^4
  • 1 <= sum(wall[i].length) <= 2 *
    1 0 4 10^4
  • For each row of I, sum(wall[I]) is the same
  • 1 < =wall[i][j]< =
    2 31 2 ^ {31}     – 1

Hash table

They want the least number of bricks to go through, which is equivalent to the most gaps.

We can use “hash table” to record the occurrence times of each gap, and finally calculate which gaps appear most in all rows. The answer is “total number of rows” minus “maximum number of gaps”.

How do you record the gaps? Just use the line prefix record.

For example, 🌰 :

  • The gap in row 1 is,3,5 [1]
  • The gap in line 2 is[3, 4]
  • There are gaps in line 3[1, 4]
  • There are gaps in line 4[2]
  • There are gaps in line 5[3, 4]
  • There are gaps in line 6].enlighened

After counting the gaps, traverse the “hash table” to find the gap 4 with the most frequent occurrence. According to the number of the same gap, the gap will only be counted once in a single row. The total number of rows is used to subtract the number of occurrences, that is, the “least number of bricks crossed” is obtained.

Code:

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int n = wall.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, sum = 0; i < n; i++, sum = 0) {
            for (int cur : wall.get(i)) {
                sum += cur;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
            map.remove(sum); // Can not pass through both sides, need to remove the last one
        }
        int ans = n;
        for (int u : map.keySet()) {
            int cnt = map.get(u);
            ans = Math.min(ans, n - cnt);
        }
        returnans; }}Copy the code
  • Time complexity: Write the number of bricks asnAll the bricks will be scanned. Complexity of
    O ( n ) O(n)
  • Space complexity: O(n)O(n)O(n)

A note on whether “overflow” needs to be considered

Similar problems, in the previous problem solution also said, here again

When a Java overflow occurs, it is processed directly as a negative number. So it does not affect the correctness of the problem.

This can be illustrated by the following example:

{
    System.out.println(Integer.MIN_VALUE); / / - 2147483648
    
    int a = Integer.MAX_VALUE;
    System.out.println(a); / / 2147483647
    a += 1;
    System.out.println(a); / / - 2147483648
    a -= 1;
    System.out.println(a); / / 2147483647
}
Copy the code

This means that Java does not need to use Long to ensure correctness if we only do “pure addition and subtraction” and not “multiply and divide”, “Max/min”, and “size judgment”, because overflow will eventually be converted back.

CPP itself does the same for int overflow.

However, when CPP overflow occurs on LC, it will not be handled as a negative number, but will throw an exception directly. Therefore, the same code cannot be executed properly on LC:

{
    cout << INT_MIN << endl; / / - 2147483648

    int a = INT_MAX; 
    cout << a << endl; / / 2147483647
    a += 1; // Overflow error
    cout << a << endl;
    a -= 1;
    cout << a << endl;
}
Copy the code

This is general, for the same problem in LC, Java does not need to deal with overflow, CPP needs to deal with the reason.

Actually, in this case, I’m not using “long, long,” because I guess the condition in “problem” is wrong:

1 <= sum(wall[i]) <= 2 * 10^4The wrong written1 <= sum(wall[i].length) <= 2 * 10^4
Copy the code

Because given the following two conditions:

1 <= n <= 10^4
1 <= wall[i].length <= 10^4
Copy the code

1 < = sum (wall [I] length) < = 2 ∗ 1041 < = sum (wall [I] length) 41 < < = 2 * 10 ^ = sum (wall [I] length) < = 2 ∗ 104 is redundant.

For counter examples:

[[2147483647.2147483647.2147483647.2147483647.1.2], 
    [2.2147483647.2147483647.2147483647.2147483647.1]]Copy the code

I use the official code and run 0, so if the official code is used as the evaluation standard, using long long is WA instead 🤣

The last

This is No.554 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.