砖墙的垂线

[编程题]砖墙的垂线

热度指数：283 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一堵砖墙，墙上有 n 行砖块，所有砖的高度都是一样的，尽管整面墙的宽度是一样，但是每块砖的宽度可能不一样。你要在这堵墙上放置一条平行于砖墙垂直于地面的垂线，请问这个垂线最少需要经过几块砖。如果你画的线只是从砖块边缘经过则不算是经过。

数据范围： $1 \le n \le 1000 \$ ，整面墙的宽度满足 $1 \le val \le 1000 \$

示例1

输入

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

输出

算法知识视频讲解

小谷围做题家

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
}

发表于 2023-03-16 23:44:02 回复(0)