西安葡萄城校招一面面试题挺有意思

下面是好好范文网小编收集整理的西安葡萄城校招一面面试题挺有意思，仅供参考，欢迎大家阅读！

前几天参加西安葡萄城的校招面试，发挥挺拉跨的，但没想到一面还是过了，当时面试官问了我一个面试题，感觉挺有意思的，在这记录一下，并手动实现。

问题：

给n个窗口的打开顺序，然后每个窗口的左上角顶点的坐标，和宽高，还有一个光标的坐标。问光标所在位置是哪个窗口，并且这个窗口的可视面积?（窗口与窗口之间重叠后，后打开的窗口会把先打开的窗口覆盖）

问题一找到光标在哪一个窗口？

思路：

根据给定的打开顺序，从后向前遍历，光标是否在当前窗口。

第二个问题求某个窗口的可视面积？

对某个窗口中的数据处理成矩形，用扫描线来做

代码：

//makefilesrc = $(wildcard ./*.cpp)obj = $(patsubst %.cpp, %.o, $(src))target = appCC = g++  $(target): $(obj)	$(CC) $(obj) -o $(target)%.o: %.cpp	$(CC) -c $< -o $@.PHONY: cleanclean:	rm -rf $(obj) $(target)

#include<algorithm>#include<iostream>#include<memory>#include<unordered_map>#include<vector>#ifndef_VIEWARE_H_#define_VIEWARE_H_#defineLINT_MIN#defineRINT_MAXclassWindows;classLine;classGetFillArea;classSoultion;classWindows{public:Windows()Windows(int windowsNums):_windowsSize(windowsNums),_worldHeight(100),_worldWidth(100){    _worldIndex.first = _worldIndex.second =0;}~Windows()int _windowsSize;int _worldHeight;int _worldWidth;static std::vector<int> _coordinate;  std::pair<int,int> _worldIndex;//世界坐标原点  std::vector<std::vector<int>> _worldCoordinate;//世界坐标点voidsetWindowsSize(int size){this->_windowsSize = size;}voidsetWorldHeight(int heigth){this->_worldHeight = heigth;}voidsetWorldWidth(int width){this->_worldWidth = width;}voidinsertCoordinate(int x,int y,int width,int height);intfindWindows(int x,int y);voidbuildPartialData(int windowsIndex);//构造局部矩形内的数据voidprPartia();  std::vector<std::vector<int>> _partiaMatrix;};classLine{public:Line(int sx,int sty,int sdy,bool sfla):x(sx),ty(sty),dy(sdy),fla(sfla)int x, ty, dy;bool fla;booloperator<(const Line& a){return x < a.x;}};classGetFillArea{public:GetFillArea()  std::unordered_map<int,int> Len, Lazy, Rson, Lson;  std::vector<Line> line;  std::vector<int> _axis;voidprepareData(std::vector<std::vector<int>>& matrix);voidbuildTree(int k,int Ls,int Rs);voidupdateInterval(int k,int l,int r,int w);voidpushUp(int k);intgetFillArea();bool isfill =false;};classSoultion{public:Soultion();intgetViewArea(std::vector<std::vector<int>>& Matrix,int x,int y);};#endif

#include<iostream>#include<memory>#include"Viewarea.h"intmain(){  std::shared_ptr<Soultion> soultion = std::make_shared<Soultion>();/*测试数据*/  std::vector<std::vector<int>> Matrix ={{1,1,3,3},{1,1,1,1},{1,3,1,2},{3,2,2,2},{4,4,2,2},{2,2,5,5}};/*光标所在位置*/int gx, gy;  gx =4, gy =1;  std::cout <<"ViewArea: "<< soultion->getViewArea(Matrix, gx, gy)<< std::endl;return0;}