今天刷leetcode碰到了这题，题目如下:

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:
Input:

[[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]

Output: 2
Explanation:

题目大意

题目的大概意思是给我们一堵墙的砖块组成，用二维的List或者说数组表示，每一层的宽度是一样的，数组中的每个数字代表砖块的宽度，如上图所示。题目要求我们找出垂直划线的情况下所穿越的最小砖块数，当然，墙最左端和最右端是不在思考范围内的，因为两边所穿越的砖块数必然是0手动滑稽。

思路

大概阅读了题目之后，受到之前Leetcode上计算汉明距离那题的影响，我首先想到的是从左到右遍历，因为墙的宽度一致，而且砖宽度都是整数，因此对于每一层，我们计算出每一层当前位置往左的总长度，之后在垂直方向以步长为一，逐步计算每根线画下来穿过的砖块数，同时记录最小穿过的砖块数，即可达到目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int leastBricks(List<List<Integer>> wall) {
    if (wall.size() == 0) {
        return 0;
    }
    int sum = 0, min = Integer.MAX_VALUE;;
    for (int i = 0; i < wall.size(); i++) {
        List<Integer> list = wall.get(i);
        for (int j = 1; j < list.size(); j++) {
            list.set(j, list.get(j - 1) + list.get(j));
        }
        sum = list.get(list.size() - 1);
    }
    for (double i = 0.5; i < sum; i += 0.5) {
        int temp = 0;
        for (int j = 0; j < wall.size(); j++) {
            int k = wall.get(j).size() - 1;
            while (k >= 0 && wall.get(j).get(k--) > i);
            if (wall.get(j).get(k + 1) != i){
                temp ++;
            }
        }
        if (temp < min) {
            min = temp;
        }
    }
    return min;
}

将此代码提交之后以后结果超时，看了一下超时测例是[[1000000],[10000000],[10000000]]，根据我的思路当然会超时，因为要迭代10000000次，如果碰上数值更大的则耗时更久。

参考了一下别人已经AC的答案，比较好的思路应该是用HashMap（特意选Tag是HashMap的题目来做，结果自己根本就没用上…）记录。对于墙的各层，如果一个完整的砖块以左（包含自己）长度相等，那么从此长度往下划线的时候就不会穿过此砖块，因此，我们只需要记录同一个长度出现的次数，最终，如果以出现次数最多的长度往下划线，穿过的砖块数就越少。代码重写如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int leastBricks(List<List<Integer>> wall) {
     if (wall.size() == 0) return 0;
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();
     int max = 0;
     for (List<Integer> list : wall) {
         int length = 0;
         for (int i = 0; i < list.size() - 1; i++) {
             length += list.get(i);
             int times;
             if (map.containsKey(length)) {
                 times = map.get(length) + 1;
             } else {
                 times = 1;
             }
             map.put(length, times);
             max = max < times ? times : max;
         }
     }
     return wall.size() - max;
 }

总结

写完总结一下，其实自己的思路已经很接近正确的思路了，计算每一层完整砖块左边的长度总和，之后进行比较即可，不过自己依然没有想到用HashMap记录来比较能更高效求的结果。这一类的题目其实都有套路，熟能生巧，做的多了，也就会了。