地平线编译器研发一面

首先跟我介绍了下，然后问了一下实习经历，最后就只问了三个题目
第一题：a+b不用四则运算实现

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf=1e9+7;
const int N=1e6+5;

int main()
{
    int a, b;
    cin >> a >> b;
    int sum=a^b;
    b=(a&b)<<1;
    while(b)
    {
        int tmp=sum;
        sum=sum^b;
        b=(tmp&b)<<1;
    }
    cout << sum << endl;
    return 0;
}

第二题：矩阵的转置，空间复杂度为O（1）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf=1e9+7;
const int N=1e6+5;

int GetPre(int i,int n,int m)
{
    return (i%n)*m+i/n;
}

int GetNext(int i,int n,int m)
{
    return (i%m)*n+i/m;
}

bool check(int i,int n,int m,int v)
{
    i=GetNext(i,n,m);
    while(i!=v)
    {
        if(i<v)
        {
            return false;
        }
        i=GetNext(i,n,m);
    }
    return true;
}

void Loop(int * a,int i,int n,int m,int v)
{
    int tmp=a[i];
    while(GetPre(i,n,m)!=v)
    {
        a[i]=a[GetPre(i,n,m)];
        i=GetPre(i,n,m);
    }
    a[i]=tmp;
}

void ZhuanZhi(int* a,int n,int m)
{
    for(int i=0;i<n*m;i++)
    {
        if(check(i,n,m,i))
        {
            Loop(a,i,n,m,i);
        }
    }
}

int a[N];

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&a[i*m+j]);
        }
    }
    ZhuanZhi(a,n,m);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%d%c",a[i*n+j],j+1==n?'\n':' ');
        }
    }
    return 0;
}

第三题：实现Lca
大体框架，建树感觉有点麻烦

struct TreeNode
{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode():val(0),left(NULL),right(NULL){};
    TreeNode(int x):val(x),left(NULL),right(NULL){};
};

struct Tree
{
    TreeNode* root_;
    map<TreeNode*,TreeNode*> pa_;
    map<TreeNode*,int> dep_;
    Tree():root_(NULL){};
    void Dfs(TreeNode *v,TreeNode* f,int dep)
    {
        pa_[v]=f;
        dep_[v]=dep;
        if(v->left!=NULL)
        {
            Dfs(v->left,v,dep+1);
        }
        if(v->right!=NULL)
        {
            Dfs(v->right,v,dep+1);
        }
    }
    TreeNode * Lca(TreeNode *u,TreeNode *v)
    {
        while(dep_[u]>dep_[v])
        {
            u=pa_[u];
        }
        while(dep_[v]>dep_[u])
        {
            v=pa_[v];
        }
        if(u==v)
        {
            return u;
        }
        while(pa_[u]!=pa_[v])
        {
            u=pa_[u];
            v=pa_[v];
        }
        return pa_[u];
    }
};