在自己电脑建设网站,全网热搜关键词排行榜,专业vi设计哪家好,社交网站开发用到的技术文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目
标题和出处
标题#xff1a;砖墙
出处#xff1a;554. 砖墙
难度
5 级
题目描述
要求
你的面前有一堵矩形的、由 n\texttt{n}n 行砖块组成的砖墙。这些砖块高度相同#xff08…
文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目
标题和出处
标题砖墙
出处554. 砖墙
难度
5 级
题目描述
要求
你的面前有一堵矩形的、由 n\texttt{n}n 行砖块组成的砖墙。这些砖块高度相同也就是一个单位高但是宽度不同。每一行砖块的宽度之和相等。
你现在要画一条自顶向下的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线这样显然是没有穿过一块砖的。
给你一个二维数组 wall\texttt{wall}wall该数组包含这堵墙的相关信息。其中wall[i]\texttt{wall[i]}wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线穿过的砖块数量最少并且返回穿过的砖块数量。
示例
示例 1 输入wall[[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]\texttt{wall [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]}wall [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]] 输出2\texttt{2}2
示例 2
输入wall[[1],[1],[1]]\texttt{wall [[1],[1],[1]]}wall [[1],[1],[1]] 输出3\texttt{3}3
数据范围
nwall.length\texttt{n} \texttt{wall.length}nwall.length1≤n≤104\texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{4}1≤n≤1041≤wall[i].length≤104\texttt{1} \le \texttt{wall[i].length} \le \texttt{10}^\texttt{4}1≤wall[i].length≤1041≤sum(wall[i].length)≤2×104\texttt{1} \le \texttt{sum(wall[i].length)} \le \texttt{2} \times \texttt{10}^\texttt{4}1≤sum(wall[i].length)≤2×104对于每一行 i\texttt{i}isum(wall[i])\texttt{sum(wall[i])}sum(wall[i]) 是相同的1≤wall[i][j]≤231−1\texttt{1} \le \texttt{wall[i][j]} \le \texttt{2}^\texttt{31} - \texttt{1}1≤wall[i][j]≤231−1
解法
思路和算法
任意一条垂线在每一行都是穿过砖块或者从砖块的边缘经过且穿过砖块的数量与从砖块的边缘经过的数量之和一定等于砖墙的行数 nnn。为了找到穿过最少砖块的垂线应该找到经过最多的砖块边缘的垂线砖墙的行数与该垂线经过的砖块边缘的数量之差即为穿过的砖块数量的最小值。
为了找到经过最多的砖块边缘的垂线需要统计从砖墙左端开始的所有不同距离的砖块边缘的数量并用哈希表记录所有距离对应的砖块边缘的数量。
对于砖墙的每一行从左到右遍历每一块砖并维护砖块宽度之和砖块宽度之和即为当前砖块的右边缘与砖墙左端的距离。对于每一块砖将其宽度加到砖块宽度之和中并将更新后的砖块宽度之和在哈希表中的次数加 111。由于不能沿着墙的两个垂直边缘之一画线因此每一行的最后一块砖不用遍历。
由于题目没有要求得到画线的位置只要求得到穿过的砖块数量的最小值因此在遍历结束砖墙的全部行之后只需要从哈希表中得到砖块边缘数量的最大值不需要得到砖块边缘与砖墙左端的距离。得到砖块边缘数量的最大值之后计算砖墙的行数与砖块边缘数量的最大值之差即为穿过的砖块数量的最小值。
代码
class Solution {public int leastBricks(ListListInteger wall) {int n wall.size();MapLong, Integer map new HashMapLong, Integer();for (ListInteger row : wall) {long sum 0;int bricks row.size();for (int i 0; i bricks - 1; i) {sum row.get(i);map.put(sum, map.getOrDefault(sum, 0) 1);}}int maxCount 0;SetMap.EntryLong, Integer entries map.entrySet();for (Map.EntryLong, Integer entry : entries) {int count entry.getValue();maxCount Math.max(maxCount, count);}return n - maxCount;}
}复杂度分析 时间复杂度O(mn)O(mn)O(mn)其中 mmm 是砖墙每一行的平均砖块数量nnn 是砖墙的行数。需要遍历砖墙中的每一行的除了最后一块砖的每块砖并用哈希表记录每块砖的右边缘与砖墙左端的距离和次数。 空间复杂度O(mn)O(mn)O(mn)其中 mmm 是砖墙每一行的平均砖块数量nnn 是砖墙的行数。需要使用哈希表记录每一行的除了最后一块砖的每块砖的右边缘与砖墙左端的距离和次数。
