代码编织梦想

二叉树
题目描述
如上所示,由正整数1,2,3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是,结点m所在的子树中一共包括多少个结点。
在这里插入图片描述
比如,n = 12,m = 3那么上图中的结点13,14,15以及后面的结点都是不存在的,结点m所在子树中包括的结点有3,6,7,12,因此结点m的所在子树中共有4个结点。

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

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

样例输入
3 7
142 6574
2 754
0 0
样例输出
3
63
498
【一开始想复杂了,还想用创建树和遍历树来做,又因为n太大导致栈溢出而一筹莫展,最后才知道原来利用的就是二叉树的一些规律】

#include<bits/stdc++.h>
using namespace std;
//二叉树
int number;
int search(int m,int n){
	//如果对于m所在的结点来说,乘2是左孩子,乘2加1是右孩子
	//只要左右孩子在n的范围之内就计数
	if(m*2<=n){
		number++;
		search(m*2,n);
	}
	if(m*2+1<=n){
		number++;
		search(m*2+1,n);
	}
	return number;
}
int main(){
	int m,n;
	while(cin>>m>>n){
		number=1;
		if(m==0 && n==0){
			break;
		}
		int counter=search(m,n);
		cout<<counter<<endl;
	}
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_50512050/article/details/129670230

没有关系的话,那就去建立关系吧-爱代码爱编程

        今天给大家分享一道链表的好题--链表的深度拷贝,学会这道题,你的链表就可以达到优秀的水平了。力扣          先来理解一下题目意思,即建立一个新的单向链表,里面每个结点的值与对应的原链表相同,并且random指针也要指向新链表中与原链表对应的那个相对位置。(即假设原链表中的第一个结点的random指向原链表的最后一个结点,那么新

一种具有o(1)复杂度的lfu算法实现(java 实现)-爱代码爱编程

最近在做一些数据缓存方面的工作。研究了LRU算法和LFU算法。 LRU有成熟的O(1)复杂度算法:参考:https://juejin.cn/post/7055600927671058469LFU最佳实现方法是O(log n

codeforces 1042b vitamins-爱代码爱编程

Codeforces 1042B Vitamins 链接: https://codeforces.com/contest/1042/problem/B 题目描述 Berland shop sells n kinds o

[牛客算法总结]:重建二叉树-爱代码爱编程

   标签: 二叉树、DFS、先序遍历、中序遍历、递归   题目: 给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中

使用pid进行恒温控制-爱代码爱编程

1. PID三个环节的作用 PID三个环节各自的主要作用和效应: 比例环节:起主要控制作用,使控制量向目标值靠拢,但可能导致振荡积分环节:消除稳态误差,但会增加超调量微分环节:产生阻尼效果,抑制振荡和超调,但会降低响应速度 2. 比例系数与积分时间的大小对曲线的影响关系 1. 比例环节         成比例地反映控制系统的偏差信号e(t),偏差

变分模态信号分解-爱代码爱编程

%% 1.生产仿真信号 fs = 1e3; t = 0:1/fs:1-1/fs;   x = 6*t.^2 + cos(4*pi*t+10*pi*t.^2) + ...     [cos(60*pi*(t(t<=0.5))) cos(100*pi*(t(t>0.5)-10*pi))];   figure('color','w') tiledla

[python]数据类(dataclass)简介-爱代码爱编程

文章目录 数据类定义装饰器field初始化数据比较后处理 dataclasses方法 Python3.7引入了dataclass。dataclass装饰器可以声明Python类为数据类;数据类适合用来存

【刷题版】掌握算法的一揽子计划——深度优先搜索和回溯-爱代码爱编程

文章目录 深搜和回溯总结基本概念常见例题自然数的拆分排列型枚举全排列 I全排列 II 组合型枚举组合 I组合 II N皇后问题一些简单的树和图上的问题二叉树的遍历二叉树的所有路径岛屿的最大面积

leetcode - 1616. split two strings to make palindrome-爱代码爱编程

Description You are given two strings a and b of the same length. Choose an index and split both strings at the

java virtual machine的结构 4-爱代码爱编程

1 Run-Time Data Areas 2 Frames 2.1 Local Variables 每个frame框包含一个被称之为本地变量的数组,数组的长度在编译期确定而以二进制的表现方式跟随类或者接口的与frame框对应的方法代码。一个本地变量赋予的值类型包括boolean、byte、char、short、int、float、reference

数模笔记——论文写作-爱代码爱编程

论文写作 各模块写作要点 数学建模论文的重要性 数学建模论文的写作是数学建模中重要的一个环节。数学建模的论文是参赛队工作的全面总结,也是评委评价建模成绩的主要依据一篇好的论文应该逻辑清晰,在语言表述上清楚,数学符号标记

动态规划算法-爱代码爱编程

一、前言 动态规划是一种常用的算法,在算法领域十分重要,但对于新手来说,理解起来有一定的挑战性,这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用。 二、解析动态规划算法 1.特点 ①把原来的问题分解成了【要点相同】的子问题(这个要点可以和后面讲的状态联系起来理解) ②所有问题都只需要解决一次(解决一次就是只需要由后面所说

-爱代码爱编程

文章目录 跳表设计跳表search()insert()RandomLevel() erase() skiplist跟平衡搜索树和哈希表的对比代码 跳表 什么是跳表-skiplist ski

代码随想录训练营第四十八天|198.打家劫舍,213.打家劫舍ii,337.打家劫舍iii-爱代码爱编程

198.打家劫舍 题目链接:https://leetcode.cn/problems/house-robber/submissions/ 代码: class Solution { public: int rob(vector<int>& nums) { int n = nums.size();

什么是分布式任务调度?怎样实现任务调度-爱代码爱编程

通常任务调度的程序是集成在应用中的,比如:优惠卷服务中包括了定时发放优惠卷的的调度程序,结算服务中包括了定期生成报表的任务调度程序,由于采用分布式架构,一个服务往往会部署多个冗余实例来运行我们的业务,在这种分布式系统环境下运

go map-爱代码爱编程

map是无序,非线程安全的,若想使用线程安全的map,使用sync.Map 一、map使用 1. 初始化 直接初始化 var m = map[int]int{} m[1] = 1 fmt.Println(m[1]) 使用make初始化(常用)   m := make(map[int]int) m[1] = 1 fmt.Println

c - candy machine 二分-爱代码爱编程

传送门 题意 JB非常喜欢糖果。 有一天,他发现了一台糖果机,里面有 N里面有糖果。看完机器的说明书后,他知道他可以选择一个子集 N糖果。每颗糖果都有一个甜味价值。JB 选择子集后,假设所选糖果的平均甜度值为 X,

考研复试——离散数学-爱代码爱编程

三年疫情都没有笔试,今年恢复,大概率会有笔试。 2023年3月19号,广州那边计算机学院发布的复试通知好像没有笔试,准备了这么久,有点可惜了,部分没有整理完。因为是跨考的,其实还有有笔试比较友好,不然的话笔试的100分就会

leetcode-爱代码爱编程

题目描述: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针