首页 > 阿里笔试8月2日题解
头像
saipubw
编辑于 2021-08-03 23:44
+ 关注

阿里笔试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;
}

全部评论

(9) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐