554. 砖墙

曾经终败给现在 2023-10-04 09:03 38阅读 0赞

你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条**自顶向下**的、穿过**最少**砖块的垂线。

砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。

如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。

**你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。**

**示例：**

输入: [[1,2,2,1],
          [3,1,2],
          [1,3,2],
          [2,4],
          [3,1,2],
          [1,3,1,1]]
    
    输出: 2
    
    解释:

**提示：**

1.  每一行砖块的宽度之和应该相等，并且不能超过 INT\_MAX。
2.  每一行砖块的数量在 \[1,10,000\] 范围内， 墙的高度在 \[1,10,000\] 范围内， 总的砖块数量不超过 20,000。

package Solution554;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map.Entry;
    
    class Solution {
    	public int leastBricks(List<List<Integer>> wall) {
    		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    		for (int i = 0; i < wall.size(); i++) {
    			int sum = 0;
    			for (int j = 0; j < wall.get(i).size(); j++) {
    				sum = sum + wall.get(i).get(j);
    				if (hm.containsKey(sum)) {
    					hm.put(sum, hm.get(sum) + 1);
    
    				} else {
    					hm.put(sum, 1);
    				}
    			}
    		}
    		int[] out = new int[hm.size()];
    		int index = 0;
    		for (Entry<Integer, Integer> set : hm.entrySet()) {
    			out[index] = set.getValue();
    			index++;
    		}
    		Arrays.sort(out);
    		if (out.length == 1) {
    			return wall.size();
    		}
    		return wall.size() - out[out.length - 2];
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		int[][] arrwall = new int[][] { { 1 }, { 1 }, { 1 } };
    
    		ArrayList<List<Integer>> wall = new ArrayList<List<Integer>>();
    		for (int i = 0; i < arrwall.length; i++) {
    
    			ArrayList<Integer> rowlist = new ArrayList<Integer>();
    
    			for (int j = 0; j < arrwall[i].length; j++) {
    
    				rowlist.add(arrwall[i][j]);
    			}
    			wall.add(rowlist);
    		}
    		System.out.println(sol.leastBricks(wall));
    
    	}
    
    }