阿里巴巴2021实习生笔试题20210608

「爱情、让人受尽委屈。」 2022-10-05 11:00 157阅读 0赞

# 第一题 #

## 题目描述 ##

截图了，问题是后面又没了  
大概  
有个数列  
 1 1 1  
 1   2   1 1\\ 2\\ 1 1 2 1  
 1   2   1   3   1   2   1 1\\ 2\\ 1\\ 3\\ 1\\ 2\\ 1 1 2 1 3 1 2 1  
 1   2   1   3   1   2   1   4   1   2   1   3   1   2   1 1\\ 2\\ 1\\ 3\\ 1\\ 2\\ 1\\ 4\\ 1\\ 2\\ 1\\ 3\\ 1\\ 2\\ 1 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1  
求第n行第k个数

## 解决方案 ##

笔试中瞎写版本

#include <iostream>
    using namespace std;
    
    long pow(int n,int p){ 
        long res= 1;
        for(int i=1;i<=p;i++){ 
            res=res*n;
        }
        return res;
    }
    int func(int n,long k){ 
        long mid = pow(2,n-1);
        if(mid==k){ 
            return n;
        }else if(k>mid){ 
            return func(n-1,k-mid);
        }else{ 
            return func(n-1,k);
        }
    }
    
    int main(){ 
        int n;
        long k;
        cin>>n>>k;
        cout<<func(n,k)<<endl;
    }

事后，JAVA版本

public class Exam2021060801 { 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            long k = in.nextLong();
            System.out.println(func(n, k));
        }
    
        public static int func(int n, long k) { 
            long mid = (long) Math.pow(2, n - 1);
            if (mid == k) { 
                return n;
            } else if (k > mid) { 
                return func(n - 1, k - mid);
            } else { 
                return func(n - 1, k);
            }
        }
    }

# 第二题 #

## 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3Mjc4MQ_size_16_color_FFFFFF_t_70]

有数组，按二叉排序树插入，根节点坐标 ( 0 , 0 ) (0,0) (0,0)，任一节点坐标 ( x , y ) (x,y) (x,y)，两个子节点 ( x + 1 , y − 1 ) (x+1,y-1) (x\+1,y−1)， ( x + 1 , y + 1 ) (x+1,y+1) (x\+1,y\+1)  
求俯视图数组（题目给例图了，大概就是任一y坐标相同时，x坐标最大节点的值），如果坐标相同，取最大值

## 解决方案 ##

瞎写，未过版本（太久没写算法题，下标和值搞混了）

#include <iostream>
    using namespace std;
    int a[200001];
    int l[200001];
    int r[200001];
    int res[200001];
    void  insert(int now,int index,int x,int y){ 
        if(a[now]>a[index]){ 
            if(l[now]!=0){ 
                insert(l[now], index,x+1,y-1);
            }else{ 
                l[now]=a[index];
                if(res[y+100000]>a[index]){ 
                res[y+100000] = a[index];
                }
                
            }
        }else if(a[now]<a[index]){ 
             if(r[now]!=0){ 
                insert(r[now], index,x+1,y+1);
            }else{ 
                r[now]=a[index];
                  if(res[y+100000]>a[index]){ 
                        res[y+100000] = a[index];
                }
                
            }
        }
    }
    
    
    int main(){ 
        int n;
        for(int i=0;i<=200000;i++){ 
        	a[i]=0;
        	l[i]=0;
        	r[i]=0;
        	res[i]=0;
    	}
        cin>>n;
        for(int i=1;i<=n;i++){ 
            cin>>a[i];
        }
        for(int i=2;i<=n;i++){ 
            insert(1,i,0,0);
        }
        res[100000]=a[1] 
        for(int i=0;i<=200000;i++){ 
        if(res[i]!=0){ 
        cout<<res[i];
        }
        }
    }

可能会过版本

#include <iostream>
    using namespace std;
    int a[200001];
    int l[200001];
    int r[200001];
    int res[200001];
    void  insert(int now,int index,int x,int y){ 
        if(a[now]>a[index]){ 
            if(l[now]!=0){ 
                insert(l[now], index,x+1,y-1);
            }else{ 
                l[now]=index;
                if(res[y+100000]<a[index]){ 
                res[y+100000-1] = a[index];
                }
                
            }
        }else if(a[now]<a[index]){ 
             if(r[now]!=0){ 
                insert(r[now], index,x+1,y+1);
            }else{ 
                r[now]=index;
                  if(res[y+100000]<a[index]){ 
                        res[y+100000+1] = a[index];
                }
                
            }
        }
    }
    
    
    int main(){ 
        int n;
        for(int i=0;i<=200000;i++){ 
        	a[i]=0;
        	l[i]=0;
        	r[i]=0;
        	res[i]=0;
    	}
        cin>>n;
        for(int i=1;i<=n;i++){ 
            cin>>a[i];
        }
        for(int i=2;i<=n;i++){ 
            insert(1,i,0,0);
        }
        res[100000]=a[1] ; 
        for(int i=0;i<=200000;i++){ 
        if(res[i]!=0){ 
        cout<<res[i];
        }
        }
    }

# Git仓库 #

https://gitee.com/shentuzhigang/mini-project/tree/master/exam-alibaba/exam-alibaba-20210608

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3Mjc4MQ_size_16_color_FFFFFF_t_70]: /images/20221005/491c29bdbc01471983dd3a4e145aacfb.png