华为OD机试统一考试D卷 - 分配土地

题目描述

从前有个村庄,村民们喜欢在各种田地上插上小旗子,旗子上标识了各种不同的数字。

某天集体村民决定将覆盖相同数字的最小矩阵形的土地分配给村里做出巨大贡献的村民,请问此次分配土地,做出贡献的村民种最大会分配多大面积?

输入描述

第一行输入 m 和 n,

  • m 代表村子的土地的长
  • n 代表土地的宽

第二行开始输入地图上的具体标识

输出描述

此次分配土地,做出贡献的村民种最大会分配多大面积

备注

旗子上的数字为1~500,土地边长不超过500

未插旗子的土地用0标识

用例1

输入

3 3
1 0 1
0 0 0
0 1 0

输出

9

说明

土地上的旗子为1,其坐标分别为(0,0),(2,1)以及(0,2),为了覆盖所有旗子,矩阵需要覆盖的横坐标为0和2,纵坐标为0和2,所以面积为9,即(2-0+1)*(2-0+1)= 9

用例2

输入

3 3
1 0 2
0 0 0
0 3 4


输出

1


说明

由于不存在成对的小旗子,故而返回1,即一块土地的面积。

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 土地的长和宽
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // 二维数组存储土地上的标识
        int[][] land = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                land[i][j] = scanner.nextInt();
            }
        }

        // 哈希表存储每个数字的最小和最大位置
        Map<Integer, int[]> minPos = new HashMap<>();
        Map<Integer, int[]> maxPos = new HashMap<>();

        // 遍历每块土地,更新每个数字的最小和最大位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = land[i][j];
                if (num != 0) {
                    if (!minPos.containsKey(num)) {
                        minPos.put(num, new int[]{i, j});
                        maxPos.put(num, new int[]{i, j});
                    } else {
                        minPos.get(num)[0] = Math.min(minPos.get(num)[0], i);
                        minPos.get(num)[1] = Math.min(minPos.get(num)[1], j);
                        maxPos.get(num)[0] = Math.max(maxPos.get(num)[0], i);
                        maxPos.get(num)[1] = Math.max(maxPos.get(num)[1], j);
                    }
                }
            }
        }

        // 初始化
        int maxArea = 0;

        // 遍历每个数字,计算其对应的面积,并更新最大面积
        for (Integer num : minPos.keySet()) {
            int[] min = minPos.get(num);
            int[] max = maxPos.get(num);
            int area = (max[0] - min[0] + 1) * (max[1] - min[1] + 1);
            maxArea = Math.max(maxArea, area);
        }

        // 打印最大面积
        System.out.println(maxArea);
        scanner.close();
    }
}

C++贪心

#include<bits/stdc++.h>
using namespace std;

struct ST{
	int x_l = -1;
	int x_r = 501;
	int y_h = 501;
	int y_l = -1;
	int cnt;
};

int main(){
	int m,n;
	cin>>m>>n;
	
	vector<vector<int>> mp(m,vector<int>(n));
	map<int,ST> dic;
	
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>mp[i][j];
			if(mp[i][j] == 0) continue;
			dic[mp[i][j]].cnt++;
			if(i>dic[mp[i][j]].x_r || dic[mp[i][j]].x_r == 501) dic[mp[i][j]].x_r = i;
			if(i<dic[mp[i][j]].x_l || dic[mp[i][j]].x_l == -1) dic[mp[i][j]].x_l = i;
			if(j>dic[mp[i][j]].y_h || dic[mp[i][j]].y_h == 501) dic[mp[i][j]].y_h = j;
			if(j<dic[mp[i][j]].y_l || dic[mp[i][j]].y_l == -1) dic[mp[i][j]].y_l = j;
		}
	}

	int res = 0;
	
	for(auto x:dic){
		if(x.second.cnt == 1){
			res = max(res,1);
			continue;
		}
		int chang = (x.second.x_r - x.second.x_l+1);
		int kuan = (x.second.y_h - x.second.y_l+1);
		res = max(res,chang*kuan);
	}
	cout<<res<<endl;
} 

#华为od##算法题解#
每日算法题 文章被收录于专栏

Leetcode算法题 小米 华为 算法题库讲解

全部评论
求点赞 收藏 关注哈 更多算法题更新中
点赞 回复 分享
发布于 2024-06-21 16:15 北京
大佬
点赞 回复 分享
发布于 2024-06-21 11:47 北京

相关推荐

面试官人很好,态度和蔼可亲,没答出来时也会引导你去思考。由于是晚上面的,导致我白天一天都有点紧张,面的时候状态也不是很好,正常可能面试官提问完应该思考几秒再答,而我就像抢答一样一口气把所有会的都说出来,这样就导致逻辑比较混乱,东一句西一句的。首先是自我介绍,先把会的技术大致讲一下,由于我八股背的多所以着重讲了一下,Java,go,jvm,MySQL,Redis,计网,操作系统这些,然后一小部分闲聊,然后先问了一下项目,面试官问我这个项目是否落实之类的,直接坦言说是写的练手的,包括之前也写过IM通讯,外卖之类的。然后面试官就把提问的重点放在了八股上。先问了Java:类加载器(答:3种+自定义类加载器、tomcat、原因+双亲委派+好处)JVM参数(答:xmx,xms,newsize这些,问我是如何设定的,我回答是把内存分一半给堆,再把堆分一半给新生代,这方面确实不太了解)然后问了一下并发相关的:线程池(答:线程池的7个参数(忘了线程工厂和阻塞时间了),3个重要参数,还有线程如何启用,为什么要设计最大线程数之类的,提到Java栈默认分配1MB运行时不可以更改)AQS(答:先讲clh是自旋锁+list,然后是AQS在这个基础上做的两个优化,然后举了一下reentrantlock根据state如何获取资源)CAS(答:使用三个字段,aba问题,然后将通常搭配自旋锁实现,面试官问通常会自旋多少次,这个不太了解,答的100,然后问100次大概多少秒,回答微秒级,然后面试官讲了一下怎么做资源可能没用完,意识到可能还需要进行阻塞操作)然后考虑一下Linux命令(top,ps,如何使用管道符过滤线程和使用Linux启动线程没答出来)然后问Redis:持久化机制(答:三种aof,rdb,混合,aof的三个参数刷盘策略,rdb以快照保存,使用bgsave会使用子线程来保存不会阻塞,而aof虽然会阻塞但是只在写完数据后追加一条命令,不会太影响,然后是他俩的优缺点,还有混合是怎么保存数据的)集群模式(答:三种,主从复制到缺点再到哨兵机制,正常使用三个哨兵互相监督,主节点挂了投票选主哨兵然后选主节点,然后额外讲一下脑裂的问题,主节点进行数据更新然后把命令写入aof来同步从节点,最后cluster集群,如何实现,使用16383个哈希槽(艹答成16384了),先根据哈希码取余,再根据节点数取余决定放在哪个节点上,然后问了一下我会怎么选集群模式,首先是cluster的问题,会让管道操作之类的失效,然后哨兵会导致整个集群结构变得复杂,使用小项目可能会考虑哨兵,大的考虑cluster,然后考了一下cluster如果一个节点挂了怎么办,根据节点数重新取余然后数据转移,面试官说这么转移比较慢,有没有别的办法,我隐约记得使用一个类似环形数组的方式,想不起来了)然后考了一下MySQL的b+树(这方面的知识点太多了,导致我什么都想讲逻辑就比较乱,讲了一下聚簇索引,树的叶子节点对应着一张页16KB,MySQL有一个区的概念,把这些页放在同一个区中,这样叶子节点的双向链表遍历时速度更快,然后b+树的扇出比较大(非常二,说成扇度之类的,面试官以为说的是扇区)这样层数就比较小,一行1kb数据的话3层可以放心2000w数据)其他的暂时想不起来了算法是lru,面试官问要不要提示,我说写个,然后写了10分钟左右,说大概写好了,但是面试官指出了2个小错误,第一个马上就改回来了,第二个一直没看出来(大脑这时候已经停止工作了)反问:问学习建议,说根据实际的项目进行深入,考虑应该怎么做,还问了一下组里面是做Java的吗?面试官说他是做go的,组里什么语言都有,语言影响不大,连忙补充了一句我对go的底层有深入源码的学习)结束。总体感觉答得不太好,没有太体现出深度,细节也不够全面。
下一个更好呗:佬,我投完云智一直没消息,多久约的一面啊
查看14道真题和解析
点赞 评论 收藏
分享
白火同学:大二有这水平很牛了,可以适当对关键信息加粗一点,比如关键技术、性能指标之类的。
点赞 评论 收藏
分享
评论
2
4
分享

创作者周榜

更多
牛客网
牛客企业服务