LCA：Lowest Common Ancestor

也就是在一棵二叉树中寻找给定的两个节点的最近公共节点

首先给定几个条件：

• (1) 结点中的数值域都是唯一的
• (2) p结点和q结点一定在树中
• (3) 非空结点与空结点的LCA是该非空结点

实际开发中经常会有需要对当前的数据结构进行排序的场景，最方便的情况是直接调用#include <algorithm>中的sort方法。但是大部分情况下使用的都不是默认的数据结构，直接在上面调用sort很难达到理想的效果。

同时最近刷题的时候也经常碰到需要在排好序的数据上做下一步算法的情况。所以针对C/C++中自定义排序的各种实用的方法在在这边进行一下简单的汇总。

最近在考虑做一下CMU15445提升一下工程项目的水平，同时也学习一下现代C++的coding schema与代码style。project的课程网站上有一个推荐的C++新特性的学习项目BootCamp，简单看了一下写的还是很不错的，从代码加注释的方式解释新特性，而且代码整体也比较贴合现代C++。

这边简单汇总一下这个项目的内容，学习一下，也方便自己后面回顾复习。

项目地址：https://github.com/cmu-db/15445-bootcamp

之前配置neovim的c++ language server的时候接触到了clang，感觉现代的C++项目还是跟自己本科学的东西完全不一样。特别是现在这种像前端那边的各种formatter工具也能用在C++里面确实是非常方便。

指针常量#

1

int *const ptr = nullptr;

const 修饰的是指针 ptr 的值，ptr 本身不能被修改，所以指针常量必须初始化，同时我们无法对 ptr 的值进行修改。

1
2
3

int a = 10;
int *const ptr = &a;
ptr = nullptr; // error

指针常量的应用场景#
例如：需要编写一个函数，实现使用传参指针的形式交换两个整形的值。

由于Linux/Unix环境下的C++开发，特别是涉及到多模块的编译时，完全离不开Makefile，所以简单了解一下后在这边做个记录。

2045. 到达目的地的第二短时间

题目描述

城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。

每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都 同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点 信号灯是绿色时 才能离开。如果信号灯是 绿色 ，你 不能 在节点等待，必须离开。

第二小的值 是 严格大于 最小值的所有值中最小的值。

例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。
给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。

注意：

你可以 任意次 穿过任意顶点，包括 1 和 n 。
你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。

示例 1：

Memberwise Initialization

在默认情况下，当以某个class object作为另一个object的初值时，会发生成员逐一初始化，

1
2

Example E1(8);
Example E2 = E1;

class data member会被依次复制，即对象中的每个成员都会被复制到另一个对象的相应成员上。

对于这种情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Matrix {
public:
  Matrix(int row, int col) : _row(row), _col(col)
  {
    _pmat = new double[row * col];
  }
  ~Matrix()
  {
    delete [] _pmat;
  }
private:
  int _row, _col;
  double *_pmat;
};


// in this case

Matrix mat(4, 4);
//此处constructor发生作用
{
  Matrix mat2 = mat;
  // 此处进行了default memberwise initialization
  // ...
  // 此处，mat2的destructor发生作用。
}

根据默认的成员逐一初始化，mat2._pmat = mat._pmat，所以这两个指针指向了同一个堆内存空间内的数组，当mat2的析构函数发生作用时，该内存空间便被释放，但是mat的指针还是指同一空间，此时再使用这个指针就会产生严重错误。

2021年年初的时候学习算法时做的一些PTA上的题，一直放在电脑里不舍得删但看着麻烦也怕丢失就放到了github的仓库里。

https://github.com/yydrowz3/somePTAProblemsCode

具体的题号没有写明，文件的名字是由题目的标题变化而来，如果真的想找到原题的话可以用对应的文件名搜一下题。

由于实在是间隔甚远再加上当时偷懒没做好标记，无力单独分开汇总。或许哪天有空了再说。

都是能AC的代码，也不求能帮到别人，只是想记录一下当时敲过的这些东西。

大概是一个月前，实在是闲的没事，在图书馆想找点C++的书学习学习这个我一直没深入的语言。本来是奔着Essential C++去的，结果找了一圈只有英文版的而且还是旧版，想想就还是算了吧，这种技术肯定是要看新标准的更好。最后只找到了这本C++ Primer，虽然我内心对这种大部头的书比较抗拒，但是要想学好一门技术，这种权威的书籍是最好的。

看看这包浆的封面和书页，这块大砖也肯定帮到过不少人吧。