砖墙的垂线

package main
// import "math"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param wall int整型二维数组 
 * @return int整型
*/
func brickwall( wall [][]int ) int {
    cnt:=map[int]int{}
    for _,row:=range wall{
        pre:=0
        for _,x:=range row[:len(row)-1]{
            pre+=x
            cnt[pre]++
        }
    }
    max:=0
    for _,v:=range cnt{
        if v>max{
            max=v
        }
    }
    return len(wall)-max
}

# -*- coding: utf-8 -*-

import collections

class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4761ac466338487a97fc3b86c7d4e004?tpId=196&tqId=40519&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        https://leetcode.cn/problems/brick-wall/solution/zhuan-qiang-by-leetcode-solution-2kls/
    算法：
        题目要求：沿着墙的高度做一条垂线，使得穿过的砖块最少，返回穿过的砖块数量。
        问题转化：穿过砖块的数量，也就是墙的高度 - 经过砖块边缘的数量。
        显然，墙的高度是固定的, m = len(wall)，因此只需要计算砖块边缘。对于砖块边缘的计算，我们遍历砖墙的每一行，对于当前行，我们从左到右地扫描每一块砖，使用一个累加器记录当前砖的右侧边缘到砖墙的左边缘的距离，将除了最右侧的砖块以外的其他砖块的右边缘到砖墙的左边缘的距离加入到哈希表中。最后我们遍历该哈希表，找到出现次数最多的砖块边缘，这就是垂线经过的砖块边缘，而该垂线经过的砖块数量即为砖墙的高度减去该垂线经过的砖块边缘的数量。
    复杂度：
        时间复杂度：O(m * n)，其中 m 是砖墙的高度，n 是每行砖墙的砖的平均数量。
        空间复杂度：O(m * n)，其中 m 是砖墙的高度，n 是每行砖墙的砖的平均数量。我们需要将每行砖块中除了最右侧的砖块以外的每一块砖的右侧边缘到砖墙的左边缘的距离加入到哈希表中。
    """

    def brickwall(self , wall ):
        # write code here
        height, hashMap = len(wall), collections.defaultdict(int)

        for nums in wall:
            distance = 0
            n = len(nums)
            for i in range(n - 1):
                distance += nums[i]
                hashMap[distance] += 1

        maxEdge = 0
        for cnt in hashMap.values():
            maxEdge = max(maxEdge, cnt)

        return height - maxEdge



if __name__ == "__main__":
    sol = Solution()

    # wall = [[1, 2, 2, 1], [3, 1, 2], [1, 3, 2], [2, 4], [3, 1, 2], [1, 3, 1, 1]]

    # wall = [[1], [1], [1]]

    wall = [[1, 2, 2, 1], [2, 4], [3, 1, 2], [6], [3, 3]]

    res = sol.leastBricks(wall)

    print res

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param wall int整型vector<vector<>> 
     * @return int整型
     */
    int brickwall(vector<vector<int> >& wall) {
        // write code here
        //对于[1,2,2,1]的墙，不考虑边界，说明在1、3、5的位置上为每块砖分界线
        //对于[3,1,2]的墙，不考虑边界，说明在3、4的位置上为每块砖分界线
        //将分界线信息存入hash表，最后遍历
        map<int,int> mp;
        for(int i=0;i<wall.size();i++)
        {
            int cur=0;
            for(int j=0;j<wall[i].size()-1;j++)
            {
                cur+=wall[i][j];
                if(mp.find(cur)==mp.end())
                {
                    mp[cur]=1;
                }
                else
                {
                    mp[cur]++;
                }
            }
        }
        //遍历mp中存储的砖块边界，得到中垂线上最多经过的边界数
        int maxx=0;
        for(auto i:mp)
        {
            maxx=max(maxx,i.second);
        }
        return wall.size()-maxx;//砖块行数-最多经过边界数=最少经过砖数
    }
};