C++刷LeetCode（554. 砖墙）【map】

糖逗

题目描述：

1. 你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。
   
2. 
   
3. 你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
   
4. 
   
5. 给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
    
13. 输出：2
    
14. 示例 2：
    
15. 
    
16. 输入：wall = [[1],[1],[1]]
    
17. 输出：3
    
18.  
    
19. 提示：
    
20. 
    
21. n == wall.length
    
22. 1 <= n <= 104
    
23. 1 <= wall[i].length <= 104
    
24. 1 <= sum(wall[i].length) <= 2 * 104
    
25. 对于每一行 i ，sum(wall[i]) 应当是相同的
    
26. 1 <= wall[i][j] <= 231 - 1
    
27. 
    
28. 来源：力扣（LeetCode）
    
29. 链接：https://leetcode-cn.com/problems/brick-wall
    
30. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int leastBricks(vector<vector<int>>& wall) {
   
4.         //map
   
5.         map<int, int>store;
   
6.         int len = wall.size();
   
7.         int temp = -1;
   
8.         for(int i = 0; i < len; i++){
   
9.             for(int j = 0; j < wall[i].size(); j++){
   
10.                 if(j >= 1){
    
11.                     wall[i][j] += wall[i][j-1];
    
12.                 }
    
13.                 if(j < wall[i].size()-1){
    
14.                     store[wall[i][j]]++;
    
15.                     temp = max(temp, store[wall[i][j]]);
    
16.                 }
    
17.             }
    
18.         }
    
19.         if(temp == -1)return len;
    
20.         return len - temp;
    
21.     }
    
22. };

复制代码

糖逗