[题目](https://leetcode.cn/classic/problems/binary-tree-paths/description/)



简单的前序遍历
```cpp
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;  // 存储所有路径的结果数组
        string path;  // 当前路径的字符串
        dfs(root, path, paths);  // 深度优先搜索
        return paths;
    }
private:
    void dfs(TreeNode* node, string path, vector<string>& paths) {
        if (node == nullptr) return;  // 递归终止条件
        path += to_string(node->val);  // 将当前节点的值添加到路径字符串中
        if (node->left == nullptr && node->right == nullptr) {
            paths.push_back(path);  // 如果是叶子节点，将路径添加到结果数组中
        } else {
            path += "->";  // 如果不是叶子节点，在路径字符串中添加箭头符号
            dfs(node->left, path, paths);  // 递归遍历左子树
            dfs(node->right, path, paths);  // 递归遍历右子树
        }
    }
};
```

搜索1

[题目](https://leetcode.cn/classic/problems/longest-happy-string/description/)

这个问题可以使用贪心算法来解决。我们可以根据当前剩余字母的数量选择下一个要添加的字母，以尽可能长的方式构建快乐字符串。
首先，我们将字母'a'、'b'、'c'以及它们对应的数量放入一个优先队列（最大堆）中，以便每次选择剩余数量最多的字母。
然后，开始构建快乐字符串。从优先队列中选择剩余数量最多的字母，并将其添加到结果字符串中。添加字母后，将该字母的数量减1，并将其重新放回优先队列。重复这个过程，直到优先队列为空或无法继续添加字母。


```cpp
class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        // 创建一个最大堆，按剩余数量最多的字母排序
        priority_queue<pair<int, char>> pq;
        if (a > 0) pq.push({a, 'a'});  // 将字母'a'的剩余数量和字符'a'放入堆中
        if (b > 0) pq.push({b, 'b'});  // 将字母'b'的剩余数量和字符'b'放入堆中
        if (c > 0) pq.push({c, 'c'});  // 将字母'c'的剩余数量和字符'c'放入堆中
        string result = "";  // 保存结果的字符串

        while (!pq.empty()) {
            auto current = pq.top();  // 获取剩余数量最多的字母
            pq.pop();  // 弹出堆顶元素
            if (result.length() >= 2 && result.back() == current.second && result[result.length() - 2] == current.second) {
                // 如果结果字符串的长度大于等于2，并且最后两个字母与当前字母相同
                if (pq.empty()) break;  // 如果堆为空，跳出循环
                auto next = pq.top();  // 获取下一个剩余数量最多的字母
                pq.pop();  // 弹出堆顶元素
                result += next.second;  // 将下一个字母添加到结果字符串中
                next.first--;  // 剩余数量减1
                if (next.first > 0) pq.push(next);  // 如果剩余数量大于0，则将其重新放回堆中
                pq.push(current);  // 将当前字母重新放回堆中
            } else {
                result += current.second;  // 将当前字母添加到结果字符串中
                current.first--;  // 剩余数量减1
                if (current.first > 0) pq.push(current);  // 如果剩余数量大于0，则将其重新放回堆中
            }
        }

        return result;  // 返回结果字符串
    }
};
```

贪心3

[题目](https://leetcode.cn/classic/problems/minimum-subsequence-in-non-increasing-order/description/)




```cpp
class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend()); // 按非递增顺序排序
        int total = accumulate(nums.begin(), nums.end(), 0); // 计算数组的总和
        int sum = 0;
        vector<int> result;

        for (int num : nums) {
            sum += num;
            result.push_back(num);
            if (sum > total - sum) {
                break;
            }
        }

        return result;
    }
};
```

贪心2

AQS（AbstractQueuedSynchronizer）是Java中的一个抽象类，位于`java.util.concurrent.locks`包下，用于构建锁和同步器。它是实现大部分同步类（如Lock、Semaphore、ReentrantLock等）的基础。



## AQS的原理和作用
AQS提供了一种简单的框架，用于原子式管理同步状态、阻塞和唤醒线程的功能，以及队列模型。它的核心思想是，如果请求的共享资源空闲，就将当前请求资源的线程设置为有效的工作线程，并将共享资源设置为锁定状态；如果共享资源被占用，就需要一定的阻塞等待唤醒机制来保证线程的有序访问。

AQS的主要作用有：
- 提供了独占锁和共享锁的实现机制，可以用于构建各种类型的锁。
- 提供了阻塞和唤醒线程的功能，可以实现线程的等待和通知机制。
- 提供了队列模型，可以按照一定的规则管理等待获取锁的线程。

## AQS的使用方式
AQS的使用方式主要通过继承和重写AQS的方法来实现。一般情况下，我们会自定义一个同步器类，继承AQS，并重写以下方法：
- `tryAcquire(int arg)`：尝试获取锁，如果成功则返回true，否则返回false。
- `tryRelease(int arg)`：尝试释放锁，如果成功则返回true，否则返回false。
- `tryAcquireShared(int arg)`：尝试获取共享锁，如果成功则返回大于等于0的值，否则返回小于0的值。
- `tryReleaseShared(int arg)`：尝试释放共享锁，如果成功则返回true，否则返回false。

通过重写这些方法，我们可以实现自定义的同步器逻辑。

## AQS与ReentrantLock的关联
ReentrantLock是Java中常用的可重入锁，它的底层实现就是基于AQS的。ReentrantLock通过继承AQS，并重写AQS的方法来实现锁的功能。具体来说，ReentrantLock重写了AQS的`tryAcquire`和`tryRelease`方法，实现了独占锁的获取和释放逻辑。

## AQS的应用场景
AQS的应用场景非常广泛，它可以用于构建各种类型的锁和同步器。常见的应用场景包括：
- ReentrantLock：可重入锁，支持公平锁和非公平锁。
- Semaphore：信号量，用于控制同时访问某个资源的线程数。
- CountDownLatch：倒计时门闩，用于等待一组线程执行完毕再继续执行。
- CyclicBarrier：循环屏障，用于等待一组线程达到某个状态再继续执行。
- Condition：条件变量，用于线程间的等待和通知机制。

AQS是Java中一个重要的同步器框架，通过继承和重写AQS的方法，可以实现各种类型的锁和同步器，提供了线程的阻塞和唤醒机制，以及队列模型的支持。

---
Learn more:
1. [AQS 详解| JavaGuide(Java面试+ 学习指南)](https://javaguide.cn/java/concurrent/aqs.html)
2. [从ReentrantLock的实现看AQS的原理及应用 - 美团技术团队](https://tech.meituan.com/2019/12/05/aqs-theory-and-apply.html)
3. [你来讲讲AQS是什么吧？都是怎么用的？ - 纪莫 - 博客园](https://www.cnblogs.com/jimoer/p/13747291.html)
4. [什么是AQS](https://mp.weixin.qq.com/s/uXGYMcftCz0hK0se5S09vw)
5. [面试逼问](https://mp.weixin.qq.com/s/gprVWDjdESs95--cBOkifg)

Java中的AQS抽象类

## AOT编译
AOT（Ahead Of Time）是一种编译方式，也被称为提前编译。它是在程序运行之前将代码编译成机器码的过程，以便在运行时直接执行机器码，而不需要在运行时进行即时编译。与AOT相对的是JIT（Just-in-Time）编译，它是在程序运行时将代码逐行解释并编译成机器码。



AOT编译的优点是：
1. 启动时间快：由于代码已经提前编译成机器码，因此在程序启动时不需要再进行编译，可以直接执行机器码，从而加快启动速度。
2. 执行性能好：AOT编译可以对代码进行更深入的优化，生成更高效的机器码，因此在执行时可以获得更好的性能表现。

然而，AOT编译也有一些缺点：
1. 生成时间长：AOT编译需要在程序运行之前进行，因此会增加程序的安装时间。
2. 占用磁盘空间多：由于AOT编译会将代码提前编译成机器码并保存在程序中，会占用更多的磁盘空间。

AOT编译适用于对启动时间和执行性能有较高要求的场景，但需要权衡生成时间和磁盘空间的消耗。




## JIT编译

JIT（即时编译）是一种执行计算机代码的方法，它在程序执行过程中（在执行期）而不是在执行之前进行编译。它通常将源代码或字节码转换为机器码，然后直接执行。JIT编译器会不断地分析正在执行的代码，并确定可被即时编译加速的部分。通过编译或重新编译这些部分，JIT编译可以提高代码的执行性能，超过编译代码的开销[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译是传统的提前编译（AOT）和直译器的结合，结合了两者的优点和缺点。它结合了编译代码的速度和解释的灵活性。JIT编译是动态编译的一种形式，允许自适应优化，比如动态重编译和特定于微架构的加速。因此，在理论上，JIT编译比静态编译能够产生更快的执行速度。JIT编译特别适合于动态编程语言，因为运行时系统可以处理后期绑定的数据类型并实施安全保证[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译可以应用于某些程序和能力，特别是动态能力，如正则表达式。它可以将运行时提供的正则表达式编译成机器码，从而加快匹配速度。一些现代的运行时环境依赖JIT编译来实现高速代码执行，包括大多数Java实现和微软的.NET框架。JIT编译也用于一些模拟器中，以便将机器代码从一个CPU体系结构转换到另一个CPU体系结构[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译的常见实现方式是先进行AOT编译，将源代码编译成字节码（虚拟机代码），然后将其JIT编译为机器码。与解释相比，这提高了运行时性能，但代价是编译造成的延迟。JIT编译器会不断地进行翻译，并对编译后的代码进行缓存，以最大限度地减少在给定运行期间将来执行相同代码的延迟[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

在字节码编译的系统中，源代码被转换为中间表示形式称为字节码。JIT编译器会读取字节码，并将其动态编译成机器代码，以便程序能够更快地运行。JIT编译可以针对每个文件、每个函数甚至任意代码片段进行编译。代码可以在即将执行时进行编译，然后缓存并在以后重用，无需重新编译。相比之下，传统的解释型虚拟机只解释字节码，性能通常较低[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

使用JIT技术的一个共同目标是达到或超过静态编译的性能，同时保持字节码解释的优势。JIT编译可以针对目标CPU和应用程序运行的操作系统模型进行优化。它可以收集关于程序在其所在环境中实际运行情况的统计信息，并根据这些信息重新排列和重新编译以获得最佳性能。JIT编译还可以进行全局代码优化，同时保留动态链接的优点。此外，JIT编译可以更容易地重新排列执行的代码，以获得更好的缓存利用率[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

总结一下，JIT（即时编译）是一种在程序执行过程中将源代码或字节码转换为机器码的方法。它结合了编译代码JIT（即时编译）是一种执行计算机代码的方法，它在程序执行过程中（在执行期）而不是在执行之前进行编译。它将源代码或字节码转换为机器码，并直接执行。JIT编译器会不断地分析正在执行的代码，并确定可被即时编译加速的部分。通过编译或重新编译这些部分，JIT编译可以提高代码的执行性能，超过编译代码的开销[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译是传统的提前编译（AOT）和直译器的结合，结合了两者的优点和缺点。它结合了编译代码的速度和解释的灵活性。JIT编译是动态编译的一种形式，允许自适应优化，比如动态重编译和特定于微架构的加速[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。因此，理论上，JIT编译可以比静态编译产生更快的执行速度。JIT编译特别适合于动态编程语言，因为运行时系统可以处理后期绑定的数据类型并实施安全保证[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译可以应用于某些程序和某些能力，特别是动态能力，如正则表达式。它可以将运行时提供的正则表达式编译成机器码，从而加快匹配速度。一些现代的运行时环境依赖JIT编译来实现高速代码执行，包括大多数Java实现和微软的.NET框架。JIT编译也用于一些模拟器中，将机器代码从一个CPU体系结构转换到另一个CPU体系结构[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译的常见实现方式是先进行AOT编译，将源代码编译成字节码（虚拟机代码），然后将其JIT编译为机器码。与解释相比，这提高了运行时性能，但代价是编译造成的延迟。JIT编译器不断地进行翻译，并对编译后的代码进行缓存，以最大限度地减少在给定运行期间将来执行相同代码的延迟[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

在字节码编译的系统中，源代码被转换为称为字节码的中间表示形式。字节码不是任何特定计算机的机器代码，可以在不同计算机体系结构之间移植。JIT编译器会读取字节码，并将其动态编译成机器代码，以便程序能够更快地运行。JIT编译可以针对每个文件、每个函数甚至任意代码片段进行编译，代码可以在即将执行时进行编译，并在以后重用，无需重新编译[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译的优势包括：
- 可以针对目标CPU和应用程序运行的操作系统模型进行优化。
- 可以收集关于程序在其所在环境中实际运行情况的统计信息，并根据这些信息重新排列和重新编译以获得最佳性能。
- 可以进行全局代码优化，同时保留动态链接的优点。
- 可以更好地利用缓存，提高缓存利用率[[1]](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)。

JIT编译的性能通常优于解释器，有时甚至优于静态编译。它可以在运行时根据目标CPU和应用程序运行的操作系统模型进行优化，收集统计信息并进行全局代码优化。此外，JIT编译的代码是可移植的，可以在安全的沙箱中

---

1. [AOT,JIT区别，各自优劣，混合编译_aot jit-CSDN博客](https://blog.csdn.net/h1130189083/article/details/78302502)
2. [什么是 JIT 和 AOT - 简书](https://www.jianshu.com/p/10a9f664add6)
3. [Xamarin.Mac 提前编译 - Xamarin | Microsoft Learn](https://learn.microsoft.com/zh-cn/xamarin/mac/internals/aot)

1. [即时编译 - 维基百科，自由的百科全书](https://zh.wikipedia.org/zh-hans/%E5%8D%B3%E6%99%82%E7%B7%A8%E8%AD%AF)
2. [基本功 | Java即时编译器原理解析及实践 - 美团技术团队](https://tech.meituan.com/2020/10/22/java-jit-practice-in-meituan.html)
3. [JIT 编译器](https://www.ibm.com/docs/zh/sdk-java-technology/8?topic=reference-jit-compiler)
4. [JIT即时编译](https://mp.weixin.qq.com/s/ORAhMtuKuhX7V__YJf2fsA)