行业知识
【独家OD2023C卷真题】20天拿下华为OD笔试【贪心】2023C-分配土地最大面积【欧弟算法】全网注释最详细分类最全的华为OD真题题解
文章目录
- 题目描述与示例
- 题目描述
- 输入描述
- 输出描述
- 备注
- 示例一
- 输入
- 输出
- 说明
- 示例二
- 输入
- 输出
- 说明
- 解题思路
- 单种颜色的最小覆盖面积
- 多种颜色的最小覆盖面积
- 代码
- Python
- Java
- C++
- 时空复杂度
- 华为OD���法/大厂面试高频题算法练习冲刺训练
题目描述与示例
题目描述
从前有个村庄,村民们喜欢在各种田地上插上小旗子,旗子上标识了各种不同的数字。某天集体村民决定将覆盖相同数字的最小矩阵形的土地的分配给为村里做出巨大贡献的村民,请问,此次分配土地,做出贡献的村民中最大会分配多大面积?
()输入描述
第一行输入 m 和 n,m 代表村子的土地的长,n 代表土地的宽
第二行开始输入地图上的具体标识
()输出描述
输出需要分配的土地面积,即包含相同数字旗子的最小矩阵中的最大面积。
备注
旗子上的数字为 1-500,土地边长不超过 500 未插旗子的土地用 0 标识
示例一
输入
3 31 0 10 0 00 1 0
输出
9
说明
土地上的旗子为 1,其坐标分别为(0,0),(2,1)以及(0,2),为了覆盖所有旗子,矩阵需要覆盖的横坐标为 0 和 2,纵坐标为 0 和 2,所以面积为 9,即(2-0+1)*(2-0+1)=9。
示例二
输入
3 31 0 20 0 00 3 4
输出
1
说明
由于不存在成对的小旗子,故而返回 1,即一块土地的面积。
解题思路
这道题乍一看可能没有思路。因为不同颜色的最小覆盖面积的计算是没有关联的,所以本题应该分为两个大步骤思考这个题目:
- 如何计算单种颜色的最小覆盖面积
- 求出所有颜色的最小覆盖面积中的最大值
单种颜色的最小覆盖面积
一个矩形的面积取决于四条边的位置。以示例一为例,如果要覆盖所有包含1的旗子,矩阵的上、下、左、右必须分别位于0,3,0,3的位置。故此时矩形的最小覆盖面积为(3-0)*(3-0) = 9
而矩形的四条边的位置则取决于同色旗子位于位于最上边的点、位于最下边的点、最左边的点、位于最右边的点。因此我们只需要记录同种颜色的点的四个最值即可很方便地求出覆盖某种颜色的矩形的最小面积。
对于同种颜色可以用一个长度为4的列表[top, bottom, left, right]来记录这四个最值信息。对于该颜色某一个点的坐标(x, y)
- 考虑上下方向,若
- 这个点比之前记录过的最上边的点更加偏上,即x
- 这个点比之前记录过的最下边的点更加偏下,即x > bottom,则更新bottom = x
- 考虑左右方向,若
- 这个点比之前记录过的最左边的点更加偏左,即y
- 这个点比之前记录过的最下边的点更加偏下,即y > right,则更新right = y
这样只需遍历一次grid数组,对所有同种颜色的点都进行上述过程,就可以求出该种颜色的最小覆盖面积了。
上述分析过程,本质上也是一种贪心思想的体现,因为四个最值所围成的矩形,就一定能够覆盖插有同色旗子的所有点了。
多种颜色的最小覆盖面积
由于颜色最多有500种,我们自然不希望循环考虑500次不同的颜色,每一次都遍历grid数组。
我们希望只需一次遍历grid数组,就能够将所有颜色的最值信息都得到。考虑如何储存不同颜色的长度为4的最值信息列表,那么答案很显而易见——使用哈希表。
其中哈希表的key为不同的颜色,value为上一小节所述的长度为4的最值信息列表。
代码
Python
# 题目:【贪心】2023C-分配土地最大面积# 分值:100# 作者:闭着眼睛学数理化# 算法:贪心# 代码看不懂的地方,请直接在群上提问from collections import defaultdictfrom math import inf# 输入二维矩阵的长、宽m, n = map(int, input().split())grid = list()# 循环m行,每次输入长度为n的一维数组for _ in range(m): grid.append(list(map(int, input().split())))# 构建哈希表dic,其中# key为表示某种颜色的数字# value为该种颜色对应的长度为4最值列表[top, bottom, left, right]# 初始化top和left为正无穷(或者500,因为边长最大为500),# 初始化,bottom和right为负无穷(或者-1)dic = defaultdict(lambda : [inf, -inf, inf, -inf])# 遍历整个二维矩阵gridfor x in range(m): for y in range(n): # 获得该种颜色 color = grid[x][y] # 如果没有插旗子,则直接跳过 if color == 0: continue # 考虑上下方向 # 如果比最上边的点更靠上,更新top,即dic[color][0] if x dic[color][1]: dic[color][1] = x # 考虑左右方向 # 如果比最左边的点更靠左,更新left,即dic[color][2] if y dic[color][3]: dic[color][3] = y# 计算所有颜色中,最小覆盖面积的最大值print(max((r-l+1)*(b-t+1) for t, b, l, r in dic.values()))
Java
import java.util.*;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int m = scanner.nextInt(); int n = scanner.nextInt(); int[][] grid = new int[m][n]; for (int i = 0; i boundaries[1]) { boundaries[1] = x; } if (y boundaries[3]) { boundaries[3] = y; } } } int maxArea = 0; for (int[] boundary : dic.values()) { int top = boundary[0]; int bottom = boundary[1]; int left = boundary[2]; int right = boundary[3]; int area = (bottom - top + 1) * (right - left + 1); maxArea = Math.max(maxArea, area); } System.out.println(maxArea); }}C++
#include #include #include #include #include int main() { int m, n; std::cin >> m >> n; std::vector grid(m, std::vector(n)); for (int i = 0; i > grid[i][j]; } } std::unordered_map dic; for (int x = 0; x boundaries[1]) { boundaries[1] = x; } if (y boundaries[3]) { boundaries[3] = y; } } } int maxArea = 0; for (auto& boundary : dic) { auto& boundaries = boundary.second; int top = boundaries[0]; int bottom = boundaries[1]; int left = boundaries[2]; int right = boundaries[3]; int area = (bottom - top + 1) * (right - left + 1); maxArea = std::max(maxArea, area); } std::cout
上一篇:饥荒怎么进入自己的服务器?
下一篇:解决SVG彩色难题的秘诀与技巧