9.5 58同城笔试

1.分页算法 返回该页

vector<int> paginatePosts(vector<int>& posts, int page, int pageSize) {

// write code here

if (pageSize>posts.size()||page*pageSize> posts.size()) {

vector<int>a;

return a;

}

int r = posts.size();

int s = min(r, (page)*pageSize);

vector<int>n(posts.begin() + (page - 1) * pageSize, posts.begin() + s);

return n;

}

2.蜂窝状数组求两点路径（有障碍） bfs

部分代码

int bfs(int ex, int ey,int d, vector<vector<int>>& mp, vector<vector<int> >& Obstacles,deque<vector<int>>& dd) {

mp[dd.front()[0]][dd.front()[1]] = 1;

while (!dd.empty())

{

for (int i = -1; i < 2; i++)

{

for (int j = -1; j < 2; j++)

{

if (canmove(dd.front()[0], dd.front()[1], dd.front()[0] + i, dd.front()[1] + j, Obstacles))

{

if (mp[dd.front()[0] +i][dd.front()[1] +j] == 0)

{

mp[dd.front()[0] + i][dd.front()[1] + j] = 1;

vector<int>temp = { dd.front()[0] + i,dd.front()[1] + j,dd.front()[2] + 1 };

//cout << " ip ed" << endl;

dd.push_back(temp);

}

}

}

}

if (dd.front()[0]==ex&&dd.front()[1]==ey)

{

return dd.front()[2];

}

cout << dd.front()[0] << " " << dd.front()[1] << endl;

dd.pop_front();

}

return -1;

}

3.没看