线段树编号问题

[编程题]线段树编号问题

热度指数：875 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一段线段树构造代码，按如下方式构造线段树。

定义变量ans，初始ans=0

定义函数build(x,y,z)，意义如下

/////////////////////////

start build

赋值 ans=x

判断若(y=z) 则 end build

定义变量mid

赋值 mid=(y+z)/2 {此处除法为下取整}
运行 build(x*2,y,mid)
运行 build(x*2+1,mid+1,z)

end build

/////////////////////////

你的任务是，对于T组询问，每个询问给出n，求对于每个n，运行build(1,1,n)后，输出ans。对于每个n，询问相互独立，即ans在上一个询问结束后归零。

输入时T单独给出，每个n会存储在数组a中给出。

示例1

输入

2,[4,5]

输出

[7,9]

说明

当n=4时，构造出的线段树的区间编号及其对应的区间为
1[1,4],2[1,2],3[3,4],4[1,1],5[2,2],6[3,3],7[4,4]
当n=5时，构造出的线段树的区间编号及其对应的区间为
1[1,5],2[1,3],3[4,5],4[1,2],5[3,3],6[4,4],7[5,5],8[1,1],9[2,2]
其中[]外的是编号，[]内表示区间的起始位置和终末位置。
可知，当n=4时编号最大为7，当n=5时编号最大为9

备注:

T<=100000
0<n<=10^8

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param T int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> wwork(int T, int* a, int aLen) {
        vector<int> v;
        for(int i=0;i<T;i++){
            int s=1, n=a[i], l, r;
            while(n!=1){
                l = n/2;
                r = n-l;
                if(((l&(-l))==l) && r>l){
                    n = r;
                    s *= 2;
                }else{
                    n = l;
                    s = 2*s + 1;
                }
            }
            v.push_back(s);
        }
        return v;
    }
};

发表于 2020-07-09 00:35:46 回复(0)

Python

ajc327

class Solution:
    def wwork(self , T , a ):
        # write code here
        mylist = a
        for i in range(len(a)):
            item = a[i]
            x= 1
            y= 1
            z=item
            while y!= z:
                mid = (z+y)//2
                l = mid-y
                r = z - mid -1
                if (l & (l-1) == 0) and l != 0 and l>r:
                    x = x*2
                    z = mid
                else:
                    x = x*2+1
                    y = mid+1
            mylist[i] = x
        return mylist

不知道要怎么优化才能不超时了

发表于 2020-09-02 20:46:24 回复(0)