关于碰到的一次二叉树的优化……

题目

题目描述

由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。

输入

输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。

输出

 对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。

样例输入

3 7
142 6574
2 754
0 0

样例输出

3
63
498

第一次代码,递归 内存:1092 耗时:1592

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int cnt, m, n;
 
void check(int x)
{
    if(x <= n)
        cnt++;
    int l = 2*x, r = 2*x+1;
    if(l <= n)
        check(l);
    if(r <= n)
        check(r);
}
 
int main()
{
    // freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &m, &n) == 2 && m && n)
    {
        cnt = 0;
        check(m);
        printf("%d\n", cnt);
    }
 
    return 0;
}

第二次代码,bfs 内存:32776 耗时:1026

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
 
int cnt, m, n;
 
void solve(int m, int n)
{
    int dm = log(m*1.0)/log(2.0);
    int dn = log(n*1.0)/log(2.0);
    int d = dn - dm;
    cnt = pow(2.0, d)-1;
    int start, end;
    int left = m, right = m;
    for(int i = 0; i < d; i++)
    {
        left *= 2;
        right = right*2+1;
    }//最左和最右的值
    if(right <= n)
        cnt += right - left + 1;
    else if(left <= n)
        cnt += n - left + 1;
}
 
int main()
{
    // freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &m, &n) == 2 && m && n)
    {
        cnt = 0;
        solve(m,n);
        printf("%d\n", cnt);
    }
 
    return 0;
}

第三次代码,数学 内存:1328 耗时:1

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
 
int cnt, m, n;
 
void solve(int m, int n)
{
    int dm = log(m*1.0)/log(2.0);
    int dn = log(n*1.0)/log(2.0);
    int d = dn - dm;
    cnt = pow(2.0, d)-1;
    int start, end;
    int left = m, right = m;
    for(int i = 0; i < d; i++)
    {
        left *= 2;
        right = right*2+1;
    }//最左和最右的值
    if(right <= n)
        cnt += right - left + 1;
    else if(left <= n)
        cnt += n - left + 1;
}
 
int main()
{
    // freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &m, &n) == 2 && m && n)
    {
        cnt = 0;
        solve(m,n);
        printf("%d\n", cnt);
    }
 
    return 0;
}

总结

1. 不要盲目使用队列、打表,易造成内存超限
2. 使用递归需要注意时间
3. 二叉树善用数学规律