[算法分析与设计]|[算法分析与设计] leetcode 每周一题: 554. Brick Wall [算法分析与设计]leetcode每周一

题目链接:
554. Brick Wall

题目大意:
( 注: leetcode 的原题页面有示例及示意图 )
给定一堵墙 wall, wall 分若干行, 每一行等高, 但每行可能由不同数量, 不同宽度的 brick(s) 组成 ; 求出自墙顶向下的一条垂直的路径, 使路径经过的 brick 尽可能少, 其中, 若路径经过两块 brick 之间 (故墙的左右两条边不算), 则视为其穿透而过, 即此时路径经过的 brick 数为 0 ;
wall 用二维数组表示, 其中 wall 的元素表示各行, 各行的元素表示行内的 brick (从左往右) 各自的宽度 ; 返回最理想的路径所经过的 brick 的数目 ;
( 具体还是看原题所附的示例 )

解题过程:
【[算法分析与设计]|[算法分析与设计] leetcode 每周一题: 554. Brick Wall】(1) 一开始我直接对每一条可能的路径记录其所经过的砖块的数量, 也即, 以半块砖为步进, 忽略两砖之间的夹缝, 不断将每一列 +1, 从而最后找出值最小的那一列即可 ;
(2) 显然, 当存在宽度很大的砖块时, 会做极多的重复劳动, 最后超时 ... ;
(3) 然后打算以段(segment) 的方式作记录, 最后作相应统计处理, 但实现到一半发现会有点麻烦, 转而考虑其他思路 ;
(4) 然后可以发现, 可以反过来记录夹缝的位置和数量 (而非要经过的砖块), 因为只有位于同一列的夹缝可以同时被该列对应的路径利用 ;
(5) 而最后的结果则显然就只需要用墙的行数减去夹缝最多的某一列上的夹缝数即可 ;

(*) 为确定 "列" 的位置, 可以先将各砖块的位置固定下来 (如: 用各砖块离墙左端的距离而不是其各自的顺序和宽度来统一区分) ;

代码如下:

class Solution { public: int leastBricks(vector>& wall) { auto rows = wall; unordered_map< size_t, int > goodCols; for (auto & row : rows) { for (size_t i = 1; i < row.size(); i++) { goodCols[ row[i-1] ]++; row[i] += row[i-1]; } }if (goodCols.empty()) { return rows.size(); } auto most = max_element( goodCols.begin(), goodCols.end(), [&](pair a, pair b) { return a.second < b.second; } )->second; auto ret = rows.size() - most; return ret; } };

(*) max/min_element 函数在输入的容器为空时返回的是 end迭代器 ... ;

Runtime: 42 ms

题目链接:
554. Brick Wall

题目大意:
( 注: leetcode 的原题页面有示例及示意图 )
给定一堵墙 wall, wall 分若干行, 每一行等高, 但每行可能由不同数量, 不同宽度的 brick(s) 组成 ; 求出自墙顶向下的一条垂直的路径, 使路径经过的 brick 尽可能少, 其中, 若路径经过两块 brick 之间 (故墙的左右两条边不算), 则视为其穿透而过, 即此时路径经过的 brick 数为 0 ;
wall 用二维数组表示, 其中 wall 的元素表示各行, 各行的元素表示行内的 brick (从左往右) 各自的宽度 ; 返回最理想的路径所经过的 brick 的数目 ;
( 具体还是看原题所附的示例 )

解题过程:
(1) 一开始我直接对每一条可能的路径记录其所经过的砖块的数量, 也即, 以半块砖为步进, 忽略两砖之间的夹缝, 不断将每一列 +1, 从而最后找出值最小的那一列即可 ;
(2) 显然, 当存在宽度很大的砖块时, 会做极多的重复劳动, 最后超时 ... ;
(3) 然后打算以段(segment) 的方式作记录, 最后作相应统计处理, 但实现到一半发现会有点麻烦, 转而考虑其他思路 ;
(4) 然后可以发现, 可以反过来记录夹缝的位置和数量 (而非要经过的砖块), 因为只有位于同一列的夹缝可以同时被该列对应的路径利用 ;
(5) 而最后的结果则显然就只需要用墙的行数减去夹缝最多的某一列上的夹缝数即可 ;

(*) 为确定 "列" 的位置, 可以先将各砖块的位置固定下来 (如: 用各砖块离墙左端的距离而不是其各自的顺序和宽度来统一区分) ;

代码如下:

class Solution { public: int leastBricks(vector>& wall) { auto rows = wall; unordered_map< size_t, int > goodCols; for (auto & row : rows) { for (size_t i = 1; i < row.size(); i++) { goodCols[ row[i-1] ]++; row[i] += row[i-1]; } }if (goodCols.empty()) { return rows.size(); } auto most = max_element( goodCols.begin(), goodCols.end(), [&](pair a, pair b) { return a.second < b.second; } )->second; auto ret = rows.size() - most; return ret; } };

(*) max/min_element 函数在输入的容器为空时返回的是 end迭代器 ... ;

Runtime: 42 ms