小R的二叉树探险 | 模拟

问题描述

在一个神奇的二叉树中,结构非常独特:

每层的节点值赋值方向是交替的,第一层从左到右,第二层从右到左,以此类推,且该二叉树有无穷多层。
小R对这个二叉树充满了好奇,她想知道,在二叉树中两个节点之间x, y的路径长度是多少。

graph TD1((1));2((2));3((3));4((4));5((5));6((6));7((7));8((8));9((9));10((10));11((11));1---3;1---2;3---4;3---5;2---6;2---7;6---11;6---10;7---9;7---8;

测试样例

示例 1:

输入:x = 11, y = 4
输出:5

示例 1:

输入:x = 2, y = 5
输出:3

示例 1:

输入:x = 7, y = 7
输出:0

题解:

        因为每层的个数都是上一层乘二,同时是2^{n}个,n为层数。所以\log _{2}n就是x,y所在的层数。接着通过层高的奇偶性判断排列的顺序,再与x,y相减便可得到所在的位置。最后一层一层向上找相同的根即可得到路程。

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;int countplace(int dx,int x){int i,cnt=0;if(dx%2==1){return pow(2,dx)-(x-pow(2,dx));}else{return x-pow(2,dx)+1;}
}int solution(int x, int y) {// write code hereif(x<y){int tt=x;x=y;y=tt;}int i,j,k,t=max(x,y),maxi=0;int dx=0,dy=0,px=0,py=0,lx=0,ly=0;dx=log2(x);dy=log2(y);cout << dx << " " << dy << "\n";px=countplace(dx,x);py=countplace(dy,y);/*if(dx==dy){return abs(px-py);}*/while(dx!=dy){if(px%2!=0){px++;}px/=2;dx-=1;lx++;}while(px!=py){if(px%2!=0){px++;}if(py%2!=0){py++;}px/=2;dx-=1;lx++;py/=2;dy-=1;ly++;}//cout << lx+ly << "\n";return lx+ly;
}int main() {std::cout << (solution(11, 4) == 5) << std::endl;std::cout << (solution(2, 5) == 3) << std::endl;std::cout << (solution(7, 7) == 0) << std::endl;std::cout << (solution(383786261, 653995378)==57) << std::endl;std::cout << (solution(997295150, 889335947)==56) << std::endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/477392.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

高精度计算题目合集

高精度计算题目合集 1168&#xff1a;大整数加法 1168&#xff1a;大整数加法 1168&#xff1a;大整数加法 高精度加法原理&#xff1a; a&#xff0c;b&#xff0c;c 都可以用数组表示。这些都是基于c语言的算术运算符形成的运算。 c 3 ( c 1 c 2 ) % 10 c_3(c_1c_2)\%1…

【2024APMCM亚太赛A题】完整参考论文与代码分享

A题 一、问题重述二、问题分析问题一&#xff1a;水下图像分类问题二&#xff1a;退化原因建模问题三&#xff1a;针对单一退化的图像增强方法问题四&#xff1a;复杂场景的综合增强模型问题五&#xff1a;针对性增强与综合增强的比较 三、问题假设退化特征独立性假设物理模型普…

VMware虚拟机(Ubuntu或centOS)共享宿主机网络资源

VMware虚拟机(Ubuntu或centOS)共享宿主机网络资源 由于需要在 Linux 环境下进行一些测试工作&#xff0c;于是决定使用 VMware 虚拟化软件来安装 Ubuntu 24.04 .1操作系统。考虑到测试过程中需要访问 Github &#xff0c;要使用Docker拉去镜像等外部网络资源&#xff0c;因此产…

C0030.Clion中运行提示Process finished with exit code -1073741515 (0xC0000135)解决办法

1.错误提示 2.解决办法 添加环境变量完成之后&#xff0c;重启Clion软件&#xff0c;然后就可以正常调用由mingw编译的opencv库了。

每日计划-1123

1. 完成 15. 三数之和 class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());// 待返回的三元组vector<vector<int>> triples;for(int i 0; i < nums.size(); i){// 检测重复的 n…

汇编语言基础

目录 基本套路 头部&#xff1a; 段&#xff1a; 函数&#xff1a; 导入masm32库 输入输出 加法指令 常见数据类型 定义数据类型 数据传达指令&#xff08;mov&#xff09; 加减法 常用伪指令 间接寻址 JMP和LOOP 堆栈操作 定义函数(ret,call) 位运算 jcc(跳…

React (三)

文章目录 项目地址十二、性能优化12.1 使用useMemo避免不必要的计算12.2 使用memo缓存组件,防止过度渲染12.3 useCallBack缓存函数12.4 useCallBack里访问之前的状态(没懂)十三、Styled-Components13.1 安装13.2给普通html元素添加样式13.3 继承和覆盖样式13.4 给react组件添…

MD5算法的学习

MD5_百度百科 MD5信息摘要算法&#xff08;Message-Digest Algorithm&#xff09;,一种被广泛使用的密码散列函数&#xff0c;可以产生出一个128位的&#xff08;16字节&#xff09;的散列值&#xff08;hash value&#xff09;&#xff0c;用于确保信息传输完整一致。MD5由美…

【虚拟机】VMWare的CentOS虚拟机断电或强制关机出现问题

VMware 虚拟机因为笔记本突然断电故障了&#xff0c;开机提示“Entering emergency mode. Exit the shell to continue.”&#xff0c;如下图所示&#xff1a; 解决方法&#xff1a;输入命令&#xff1a; xfs_repair -v -L /dev/dm-0 注&#xff1a;报 no such file or direct…

【论文阅读】WGSR

0. 摘要 0.1. 问题提出 1.超分辨率(SR)是一个不适定逆问题&#xff0c;可行解众多。 2.超分辨率(SR)算法在可行解中寻找一个在保真度和感知质量之间取得平衡的“良好”解。 3.现有的方法重建高频细节时会产生伪影和幻觉&#xff0c;模型区分图像细节与伪影仍是难题。 0.2. …

解决 Android 单元测试 No tests found for given includes:

问题 报错&#xff1a; Execution failed for task :testDebugUnitTest. > No tests found for given includes: 解决方案 1、一开始以为是没有给测试类加public修饰 2、然后替换 Test 注解的包可以解决&#xff0c;将 org.junit.jupiter.api.Test 修改为 org.junit.Tes…

服务机器人三甲坎德拉:用智能化开启售后服务新篇章

随着市场需求快速增长&#xff0c;专注自动驾驶服务机器人研发的坎德拉近年来实现了快速发展&#xff0c;并且通过技术创新与优质服务收获了良好口碑。为了不断提升售后服务质量和客户服务水平&#xff0c;坎德拉与新一代智能客户服务解决方案提供商售后宝共同打造智能化的售后…

3D建筑模型的 LOD 规范

LOD&#xff08;细节层次&#xff09; 是3D城市建模中用于表示建筑模型精细程度的标准化描述不同的LOD适用于不同的应用场景 LOD是3D建模中重要的分级标准&#xff0c;不同层级适合不同精度和用途的需求。 从LOD0到LOD4&#xff0c;细节逐渐丰富&#xff0c;复杂性和精度也逐…

递归------深度优先搜索

深度优先搜索&#xff08;Depth-First Search&#xff0c;简称DFS&#xff09;是一种用于遍历或搜索树或图的算法。它从一个顶点开始&#xff0c;尽可能深地搜索树的分支。深度优先搜索沿着一条路径深入&#xff0c;直到无法继续为止&#xff0c;然后回溯并尝试其他路径。这种搜…

蓝桥杯c++算法学习【5】之枚举与模拟(卡片、回文日期、赢球票、既约分数:::非常典型的比刷例题!!!)

别忘了请点个赞收藏关注支持一下博主喵&#xff01;&#xff01;&#xff01;! ! ! &#xff01;&#xff01;&#xff01; 关注博主&#xff0c;更多蓝桥杯nice题目静待更新:) 枚举与模拟 一、卡片&#xff1a; 【问题描述】 小蓝有很多数字卡片&#xff0c;每张卡片上都…

相机网卡开启巨型帧和关闭节能模式方法

2022 年 8 月 2 日 Tank 阅读次数&#xff08;ip/1年&#xff09;: 26,796 win10为例子 首先在开始菜单搜索&#xff1a;网络连接 对想要设置的网络右键&#xff1a;属性 点 配置 高级里面找到这三个选项&#xff0c;参考下图设置&#xff0c;螃蟹网卡建议关掉所有节能有关的…

Windows server2016设置多用户界面——保姆级教程

在 Windows Server 2016 服务器中&#xff0c;通常默认情况下能够支持两个用户进行远程登录。而通过在服务器上安装远程桌面服务中的远程桌面会话主机和远程桌面授权&#xff0c;并对其进行相应配置&#xff0c;便可以实现多用户远程登录。 远程桌面服务是一种由若干角色服务所…

第一个autogen与docker项目

前提条件&#xff1a;在windows上安装docker 代码如下&#xff1a; import os import autogen from autogen import AssistantAgent, UserProxyAgentllm_config {"config_list": [{"model": "GLM-4-Plus","api_key": "your api…

后端开发详细学习框架与路线

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端开发 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 为帮助你合理安排时间&#xff0c;以下是结合上述学习内容的阶段划分与时间分配建议。时间安排灵活&a…

【Isaac Sim】相关问题汇总

目录 一、安装点击Install时报错二、启动时报 Failed to create any GPU devices三、加载Isaac Sim自带模型或示例时报 Isaac Sim is not responding 一、安装点击Install时报错 报错&#xff1a; request to https://asset.launcher.omniverse.nvidia.com/… failed, reason:…