首页 > 其他分享 >记录一道面试题(哈希表 稀疏矩阵)

记录一道面试题(哈希表 稀疏矩阵)

时间:2024-10-10 10:43:32浏览次数:7  
标签:面试题 int 矩阵 地图 哈希 空气 沙子 方块

题目:

有一个游戏中的三维地图,是由i,j,k三个轴组成的三维网络。每个立方体由不同的种类代表,比如空气,水,沙子,泥土。
地图上方的空气方块,不会经常变动且数量占大多数,下方是各种类型的方块,会经常相互转换(水变沙子,沙子变泥土等)。

问题:请你实现一个存储该地图的方案(地图方块和对应类型)。
要求:尽量减少内存空间占用,要支持高频查询。

思路:

1.首先要有整体意识,地图是一个三维坐标系,有三个轴。应该要想到用矩阵或者多维数组。

2.要注意要求中的“尽量减少内存空间占用”,由于空气多且不易变动,可以采用稀疏矩阵来存。相当于没数据的时候就是空气。

3.要支持高频查询,哈希表应该是最快的。

上代码:

blockmap.h

#ifndef BLOCKMAP_H
#define BLOCKMAP_H


#include <unordered_map>

/*
有一个游戏中的三维地图,是由ijk三个轴组成的三维网络。每个立方体由不同的种类代表,比如空气,水,沙子,泥土。
地图上方的空气方块,不会经常变动且数量占大多数,下方是各种类型的方块,会经常相互转换(水变沙子,沙子变泥土等)。

问题:请你实现一个存储该地图的方案(地图方块和对应类型)。
要求:尽量减少内存空间占用,要支持高频查询。

关键思路:
1.由于空气变动少且占用多,可以采用稀疏矩阵存储,节省内存资源。
2.用哈希表存储非空气块,方便快速查询。
*/

// 方块类型:实际项目应该还会存储别的成员。比如颜色之类的。也可以用枚举定义类型
struct Block
{
    int type = 0; // 0-空气 1-水 2-泥土 3-沙子 4-树
};

class BlockMap
{
private:
    std::unordered_map<long long, Block> blockMap; // 用哈希表存储非空气块,方便快速查询。
    const int airType = 0; // 空气类型为0
    long long encodeKey(const int& i, const int& j,const int& k) // 为了生成唯一的key,合并成一个long long
    {
        return (static_cast<long long>(i) << 40) | (static_cast<long long>(j) << 20) | k;
    }
public:
    BlockMap(){}
    //获取方块类型
    int getBlockType(const int& i, const int& j,const int& k)
    {
        long long key = encodeKey(i,j,k);
        if(blockMap.find(key) != blockMap.end())
        {
            return blockMap[key].type;
        }
        else{
            return airType; // 找不到的时候,默认就是空气。
        }
    }

    // 设置方块类型
    void setBlockType(const int& i, const int& j,const int& k, const int& type)
    {
        auto key = encodeKey(i,j,k);
        if(type == airType)
        {
            return; // 不存空气。节省内存空间。
        }
        else
        {
            Block newbk;
            newbk.type = type;
            blockMap[key] = newbk;
        }
    }
};

void BlockMapTest(); // 测试程序

#endif // BLOCKMAP_H

测试:

#include "blockmap.h"
#include <qDebug> // Qt平台的头文件。非C++标准库

void BlockMapTest()
{
    BlockMap mapTest;
    mapTest.setBlockType(1,1,1,1);
    mapTest.setBlockType(2,2,2,2);
    mapTest.setBlockType(3,3,3,3);

    qDebug() << "1,1,1 类型为:" << mapTest.getBlockType(1,1,1);
    qDebug() << "2,2,2 类型为:" << mapTest.getBlockType(2,2,2);
    qDebug() << "3,3,3 类型为:" << mapTest.getBlockType(3,3,3);
    qDebug() << "1,0,1 类型为:" << mapTest.getBlockType(1,0,1);
}

执行效果:

总结:

数据结构还是要多熟悉,自己写不出来的话要会选择最合适的。

标签:面试题,int,矩阵,地图,哈希,空气,沙子,方块
From: https://www.cnblogs.com/xcywt/p/18455858

相关文章

  • MyBatis的常见面试题
    MyBatis1、什么是MyBatisMyBatis是一款优秀的半自动化的持久层框架。支持自定义SQL、存储过程以及高级映射。2、MyBatis的特点?简单、灵活、解耦、丰富的标签3、MyBatis的核心组件全局配置文件:MyBatis的一些全局信息,包含数据库链接信息和MyBatis运行时所需要的各种特性,以及......
  • 【JS】哈希法解决两数之和
    思路使用哈希法:需要快速查询一个元素是否出现过,或者一个元素是否在集合里时本题需要一个集合来存放我们遍历过的元素,然后在遍历数组的时候去询问这个集合,符合要求的某元素是否遍历过,也就是是否出现在这个集合。因为要返回下标,所以使用Map集合,key存放元素值,value存放元素下......
  • [SpringBoot] 苍穹外卖--面试题总结--上
    前言     1--苍穹外卖-SpringBoot项目介绍及环境搭建详解-CSDN博客2--苍穹外卖-SpringBoot项目中员工管理详解(一)-CSDN博客3--苍穹外卖-SpringBoot项目中员工管理详解(二)-CSDN博客4--苍穹外码-SpringBoot项目中分类管理详解-CSDN博客5--苍穹外卖-SpringBoot项目......
  • 【模板】树哈希
    https://peehs-moorhsum.blog.uoj.ac/blog/7891题目描述对一棵树求hash值,以判断两棵树是否同构。有有根树和无根树两个版本。solution找一个随机函数\(f\)(可以选xor-shift),然后每个点的子树的哈希值如下计算:\[h_u=1+\sum_{v}f(h_v)\]这是有根树的情况,对于无根树,1.可以换......
  • vue2面试题
    vue2生命周期系统自带:beforeCreatecreatedbeforeMountmountedbeforeUpdateupdatedbeforeDestroydestroyed2.一旦进入到页面或者组件,会执行哪些生命周期,顺序。beforeCreatecreatedbeforeMountmounted3.在哪个阶段有$el,在哪个......
  • 洛谷 P7469 [NOI Online 2021 提高组] 积木小赛(字符串哈希)
    题目传送门解题思路读题后,我们可以发现,字母串  只能从两边删除,于是我们可以枚举一个区间 ,然后在字母串  中匹配(可以用指针来进行匹配),同时可以做字符串哈希去重。注意如果怕被卡,可以用双模哈希;记得开longlong代码#include<bits/stdc++.h>usingnamespacestd;......
  • python3常用库之哈希hashlib和hmac使用
    hashlibimporthashlib#MD5是最常见的哈希算法,速度很快,生成结果是固定的128bit/16字节,通常用一个32位的16进制字符串表示。md5=hashlib.md5()md5.update("hello".encode())print(md5.hexdigest())#5d41402abc4b2a76b9719d911017c592#数据量很大时分块多次调用up......
  • 短视频矩阵SaaS系统源代码开发部署步及技术解析
    短视频矩阵源码开发部署一般包括以下步骤:安装开发环境:根据具体的短视频矩阵源码开发语言和框架,需要安装相应的开发环境,例如Python、Node.js、Django、React等。下载短视频矩阵源码:从源码存储库或官方网站下载最新的短视频矩阵源码。配置数据库:根据短视频矩阵源码的需求,选......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点、19.删除链表的倒数第N个节点
    24.两两交换链表中的节点力扣题目链接(opensnewwindow)给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。输入:head=[1,2,3,4]输出:[2,1,4,3]示例2:输入:head=[]输出:[]示例3:输入:head=[1]......
  • 为什么张雪峰推荐普通人家的孩子考研考计算机?从阿里一面面试题说起:剑指 offer - 159:库
    张雪峰推荐普通人考研考计算机相关专业,主要是因为计算机技术在现代社会中薪资水平相对较高。另一方面,也是计算机专业在平时就学习了数据结构等课程,在招聘前冲刺复习的时候比像我这样的非科班选手要省下不少精力。拿我经历过的阿里巴巴C++后端一面来说,面试官考察了最基本的......