第一題

題目描述

截圖了，問題是后面又沒了
大概
有個數列
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);
        }
    }
}

第二題

題目描述

有陣列，按二叉排序樹插入，根節點坐標 ( 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