（每日一练c++）CC191 最近公共祖先

- 日理万妓 2023-10-04 18:06 24阅读 0赞

## 前言 ##

C++是一种计算机高级程序设计语言，由C语言扩展升级而产生 ，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。  
C++既可以进行C语言的过程化程序设计，又可以进行以抽象数据类型为特点的基于对象的程序设计，还可以进行以继承和多态为特点的面向对象的程序设计。C++擅长面向对象程序设计的同时，还可以进行基于过程的程序设计。  
C++拥有计算机运行的实用性特征，同时还致力于提高大规模程序的编程质量与程序设计语言的问题描述能力。

Java是一门面向对象的编程语言，不仅吸收了C++语言的各种优点，还摒弃了C++里难以理解的多继承、指针等概念，因此Java语言具有功能强大和简单易用两个特征。Java语言作为静态面向对象编程语言的代表，极好地实现了面向对象理论，允许程序员以优雅的思维方式进行复杂的编程 。  
Java具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点 。Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等 。

Python由荷兰数学和计算机科学研究学会的吉多·范罗苏姆 于1990 年代初设计，作为一门叫做ABC语言的替代品。Python提供了高效的高级数据结构，还能简单有效地面向对象编程。Python语法和动态类型，以及解释型语言的本质，使它成为多数平台上写脚本和快速开发应用的编程语言，随着版本的不断更新和语言新功能的添加，逐渐被用于独立的、大型项目的开发。  
Python解释器易于扩展，可以使用C语言或C++（或者其他可以通过C调用的语言）扩展新的功能和数据类型。Python 也可用于可定制化软件中的扩展程序语言。Python丰富的标准库，提供了适用于各个主要系统平台的源码或机器码。  
2021年10月，语言流行指数的编译器Tiobe将Python加冕为最受欢迎的编程语言，20年来首次将其置于Java、C和JavaScript之上。

### 描述 ###

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

测试样例：

2，3

返回：1

class LCA {
    public:
        string int2b(int x){
            string ans="";
            while(x){
                ans=(char)((x&1)+'0')+ans;
                x/=2;
            }
            return ans;
        }
        int getLCA(int a, int b) {
            string sa=int2b(a);
    		string sb=int2b(b);
            int ans=0;
            for(int i=0;i<sa.length()&&i<sb.length();i++){
    			if(sa[i]==sb[i]) ans=ans*2+(sa[i]-'0');
    			else break;
    		}
            return ans;
        }
    };

写在最后  
学习编程, 既要考虑诗和远方, 也要考虑眼前的苟且。

每年像你这样的学生不计其数，大一刚进校，一门C语言，学校发一本垃圾C语言教材，按时上课，老师在那里念念PPT，讲讲浮点型变量，malloc

啥的，你若认真听了，那你可能懂了，但是发现不会写，你若没听，玩手机了，你是既不懂，也不会写，上来上去，蒙在鼓里的人出不来，水平就一直这样，龟速增长。

有的学生学的一头雾水，开始怀疑自己，准备转专业，放弃计算机，有的学生学懂了，写程序一直报错，开始怀疑自己，有的学生觉得教材写得不好，去书店转了一圈，买了三四本C语言的书，但最后厚厚的灰尘盖在了书上，再也没翻过。

这三种学生，如果继续这样，最后都要凉凉。

马克思教给我们要具体问题具体分析，那我今天就来分析一下，计算机专业的学生，到底应该怎么学计算机，才能效果最好，进步最快。

如果你要学习物理，我推荐你顺着物理的发展史学习，先学习牛顿经典物理，再学习热力学

，电磁学这些不那么经典的，再学习相对论，量子力学这种彻底推翻经典物理的，再学习量子电动力学这种硬核的，比较前沿的，整个学习过程，是自底向上。

但是学习计算机，真的适合这样吗？

先学习电路，冯诺依曼结构，造一台计算机？然后再用汇编写个小操作系统？写个小编译器？最后一步一步往上走，最后开始用高级语言编程？

你要是这么学，必然爆炸。

计算机的学习最好应该是自顶向下。

这个顶，顶到什么程度？

有人说，C语言就是高级语言了，从C语言开始学就好了。

但是如果让我教计算机，我第一节课教学生们的，绝对不是C语言，而是教大家如何使用Github，Stackoverflow，告诉世界上正在发生什么，程序员之间是如何协作的，告诉你在这个大社区，你可以读到这个世界最牛逼的程序员写的代码。

我还要告诉大家如何使用云服务，告诉大家可以买一个一个月十块钱的学生服务器，自己做点有趣的事，我还要推荐大家去用Visual Studio Code，而不是简单粗暴的在机房装一个VC6，或者CodeBlocks，美其名曰，“我们当年用记事本还XXXX，现在的学生被惯坏了”这种话。

如果可以，我还会教同学们如何科学上网，让英文编程环境成为习惯，让遇到问题google，而不是百度成为习惯，让大家在第一节课上完，就能进入这个世界编程大社区，哪怕什么都不懂，你也能保证所在的社区，就是世界程序员的大家庭当你进入Github，看着各种有趣的项目的时候，相信我，你的视野就会在此为起点，快速打开，不断增长，进入一个良性循环。

而当刚上大一的学生第一次进入github时候，被眼前的各种没听过，没见过，但感觉很厉害的项目所吸引的时候，当他两眼冒光的时候，我就知道，他这四年，成了。

有人会这样说我：

“Github还用教？刚才你说的那些学生，如果能被C语言的困难打倒，那他也不适合做程序员，转行正好。”

像这种话，我想说，在很多时候，佛和魔仅在一念之间，你在最开始的时候点到了，给了他引导，他以后可能会马上进入一个正反馈

状态，如果你没点到，马上可能就负反馈了。

我一直觉得国内的计算机专业的学生很可怜。

当VScode表现越来越优异的时候，学生们还在机房用着VC6，看着密密麻麻的报错无可奈何。

当Google搜索可以精准定位你的问题的时候，学生们还在为百度搜索出来乱七八糟的搜索结果无可奈何。

你用百度，用中文搜索，你连stackoverflow都搜不出来。

但是你可以去问问，做一个调查，有多少大一结束的学生，没上过stackoverflow，不知道怎么在github里提交issue和pull request，你统计一下，看看这个比例有多大？

你再统计一下有多少比例的大一结束的学生没用过google，并且对其用不了的原因不太清楚？

视野打不开，一切都完了。