当前位置:网站首页>完全二叉树问题
完全二叉树问题
2022-08-03 22:41:00 【chengqiuming】
一 原问题描述
BST - POJ 2309 - Virtual Judgehttps://vjudge.net/problem/POJ-2309
二 输入和输出
1 输入
第 1 行包含一个整数 N,表示查询的数量。在接下来的 N 行中,每行都包含一个数字,表示根号为 X 的子树。
2 输出
共 N 行,其中第 i 行包含第 i 个查询的答案。
三 输入和输出样例
1 输入样例
2
8
10
2 输出样例
1 15
9 11
四 分析
本问题规律可循,若 n 是奇数,那么必然是叶子节点,最大数和最小数都是它自己。否则求 n 所在的层次(倒数的层数,底层为 0),它的层数就是 n 的二进制表示中从低位开始第1个1所在的位置 i(最后一个非0位),例如 6 的二级制为110,从低位开始第1个1的位置是1,因此 6在第1层;12的二进制是1100,从低位开始第1个1的位置是2,因此12在第2层,如下图所示。
i 的值即为层数,可得到 n 的左右子树各有 k = 2^i-1个节点,那么最小数是 n-k,最大数是n+k,那么怎么求 2^i呢?
实际上,想得到最后一个非 0 位,只需先将原数取反后加1,此时除了最后一个非 0 位,其他位均与原数相反,直接与原数按位与运算即可得到最后一个非0位。
五 算法设计
1 求解logbit(n)=n&(-n)。
2 让 看= lowbit(n)-1,输出最小数 n-k,最大数 n+k。
六 代码
package poj2309;
import java.util.Scanner;
public class Poj2309 {
static int lowbit(int n) {
return n & (-n);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T, n, k;
T = scanner.nextInt();
while (T-- > 0) {
n = scanner.nextInt();
k = lowbit(n) - 1;
System.out.println((n - k) + " " + (n + k));
}
}
}
七 测试
绿色为输入,白色为输出
边栏推荐
猜你喜欢
Lift, Splat, Shoot: Encoding Images from Arbitrary Camera Rigs by Implicitly Unprojecting to 3D 论文笔记
电商秒杀系统
override学习(父类和子类)
for循环练习题
LabVIEW code generation error 61056
嵌入式系统:概述
Bytebase数据库 Schema 变更管理工具
113. Teach a Man how to fish - How to query the documentation and technical implementation details of any SAP UI5 control property by yourself
亿流量大考(2):开发一套高容错分布式系统
21天打卡挑战学习MySQL——《Window下安装MySql》第一周 第三篇
随机推荐
Why do we need callbacks
云平台建设解决方案
HDU 5655 CA Loves Stick
UVa 1025 - A Spy in the Metro (White Book)
Research status of target detection at home and abroad
静态文件快速建站
2022-08-02 mysql/stonedb慢SQL-Q18-内存使用暴涨分析
21天打卡挑战学习MySQL—Day第一周 第一篇
CAS:153162-70-0_N-BOC-6-Biotinamidohexylamine
物联网新零售模式,引领购物新潮流
Cloud platform construction solutions
override learning (parent and child)
Causes of Mysql Disk Holes and Several Ways to Rebuild Tables
如何创建一个Web项目
for loop exercises
PowerMockup 4.3.4::::Crack
Boss: There are too many systems in the company, can you realize account interoperability?
Codeup brushing notes - simple simulation
HDU 5655 CA Loves Stick
优化查询(工作中)