题目:
有一个游戏中的三维地图,是由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