阿里笔试8月2日题解
A. 给一个地图。可以上下左右走，每个点有一个超时时间，超过以后不能走了。问能否到达终点。
bfs模板题，唯一要注意的就是在队列中多存一个时间，然后走的时候判定下是不是已经超时不能走了。轻松拿下。
/*
* @Author: your name
* @Date: 2021-08-02 18:25:54
* @LastEditTime: 2021-08-02 19:24:07
* @LastEditors: Please set LastEditors
* @Description: In User Settings Edit
* @FilePath: \cpp\a.cpp
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 105
int tab[maxn][maxn],bx,by;
bool ispass[maxn][maxn];
int n,m;
bool islegal(int x,int y)
{
return 0<=x&&x<n&&0<=y&&y<m;
}
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct point
{
int x,y,time;
};
bool bfs(int bx,int by)
{
queue<point> que;
que.push({bx,by,0});
ispass[bx][by]=1;
while (que.size())
{
auto p=que.front();
if (p.x==n-1&&p.y==m-1)
{
return true;
}
for (auto &e:dir)
{
point p2={p.x+e[0],p.y+e[1],p.time+1};
if (islegal(p2.x,p2.y)&&tab[p2.x][p2.y]>=p2.time&&!ispass[p2.x][p2.y])
{
ispass[p2.x][p2.y]=true;
que.push(p2);
}
}
que.pop();
}
return false;
}
int main(void)
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
memset(ispass,0,sizeof(ispass));
for (int i=0;i<n;++i)
{
for (int j=0;j<m;++j)
{
scanf("%d",&tab[i][j]);
if (tab[i][j]==0)
{
bx=i,by=j;
}
}
}
auto ans=bfs(bx,by);
puts(ans?"YES":"NO");
}
return 0;
} B. 给一个数组，要求将其重排，使其重排后按顺序插入一个二叉排序树，插入完毕后能形成一颗完全二叉树。
考察对树的理解。对于完全二叉树，先从左到右，然后从上到下编号成1..n。如果按这个顺序插入，就能保证最后形成的一定是完全二叉树。
因此，我们只要保证，第i次插入的数字，刚好是完全二叉树中第i个数字即可。
我们首先将数字排序。然后对完全二叉树中序遍历，中序遍历的过程中记录当前点的标号是哪一个。由于中序遍历是从小到大，我们之前排序好的数字也是从小到大，因此可以利用这个关系，第i个中序遍历到的数字，就是数组排序后的第i个元素，其标号是j，那么设一个新的数组ar2，在中序遍历中执行ar2[j]=ar[i]的复制操作即可。
最后按顺序输出ar2中的数字即可。
/*
* @Author: your name
* @Date: 2021-08-02 18:25:54
* @LastEditTime: 2021-08-02 19:45:29
* @LastEditors: Please set LastEditors
* @Description: In User Settings Edit
* @FilePath: \cpp\b.cpp
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int ar[maxn],ar2[maxn];
vector<int> no;
void tree(int p,int n)
{
if (p>n)
return;
tree(2*p,n);
no.push_back(p);
tree(2*p+1,n);
}
int main(void)
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
no.clear();
scanf("%d",&n);
for (int i=0;i<n;++i)
{
scanf("%d",&ar[i]);
}
tree(1,n);
sort(ar,ar+n);
for (int i=0;i<n;++i)
{
ar2[no[i]-1]=ar[i];
}
for (int i=0;i<n;++i)
{
printf("%d ",ar2[i]);
}
puts("");
}
return 0;
} 