每日计划-1028

1. 完成 215.数组中的第k个最大元素

#include <vector>
#include <algorithm> 
using namespace std;

class Solution {
public:
    // 调整堆的函数，将nums数组从start位置开始调整为最大堆
    void adjust(vector<int>& nums, int start, int end) {
        int fat = start; // fat代表父节点的索引
        int chi = 2 * fat + 1; // chi代表左子节点的索引
        while (chi <= end) { // 当左子节点存在时
            if (chi + 1 <= end && nums[chi + 1] < nums[chi]) { // 如果右子节点存在且值小于左子节点
                chi++; // 选择右子节点作为子节点
            }
            if (nums[fat] > nums[chi]) { // 如果父节点的值大于子节点的值
                swap(nums[fat], nums[chi]); // 交换父节点和子节点的值
                fat = chi; // 更新fat为当前子节点
                chi = 2 * fat + 1; // 更新chi为新的子节点
            } else {
                break; // 如果父节点的值不大于子节点的值，结束循环
            }
        }
    }

    // 查找数组中第k大的元素
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size(); // 获取数组的大小
        // 从数组的一半开始，向下调整堆，确保每个父节点都大于其子节点
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjust(nums, i, n - 1);
        }
        // 从数组的最后一个元素开始，每次将最大的元素放到数组的开头，然后调整堆
        for (int j = n - 1; j >= 1; j--) {
            swap(nums[0], nums[j]); // 将最大的元素放到数组的开头
            adjust(nums, 0, j - 1); // 调整堆
        }
        return nums[k - 1]; // 返回第k大的元素
    }
};

 利用堆排序解决问题，用空间换时间。

2. 八股部分

1）递归函数的特点和使用场景是什么？

特点：

1. 自我引用：递归函数在其定义中直接或间接地调用自身。
2. 基线条件（Base Case）：递归函数必须有一个或多个基线条件，以防止无限递归。基线条件是递归停止的点，通常是最简单的情况，可以直接解决而不需要进一步递归。
3. 递归步骤：除了基线条件外，递归函数还必须有递归步骤，即函数调用自身并逐渐接近基线条件。
4. 状态的累积：递归函数通过参数传递来累积状态，每次递归调用都会更新这些参数，直到达到基线条件。
5. 空间复杂度：递归函数可能会占用更多的内存空间，因为每次函数调用都需要在调用栈上保存状态信息。
6. 简洁性：递归函数通常可以用更简洁的代码来表达复杂的算法，尤其是那些具有自然分层或分治结构的问题。

使用场景：

1. 分治算法：递归是实现分治算法的自然选择，如归并排序、快速排序等。
2. 树和图的遍历：在树结构（如二叉树）和图结构中，递归可以用来实现深度优先搜索（DFS）。
3. 动态规划问题：许多动态规划问题可以通过递归加记忆化（memoization）来解决，如斐波那契数列、背包问题等。
4. 回溯算法：在解决组合问题时，如八皇后问题、数独等，递归可以用来探索所有可能的解决方案。
5. 数学和逻辑问题：递归非常适合解决那些具有自相似性的问题，如计算阶乘、幂运算等。
6. 文件系统遍历：在处理文件和目录时，递归可以用来遍历整个文件系统，处理每个文件和子目录。
7. 递归数据结构：对于递归定义的数据结构，如链表、树等，递归是处理这些结构的自然方式。

2）什么是回调函数？有什么特点？

回调函数是一种以函数作为参数并在某个事件或条件满足时被调用的函数。它是编程中常用的一种设计模式，尤其在异步编程和事件驱动编程中非常常见。以下是回调函数的特点：

1. 高阶函数：回调函数允许将函数作为参数传递给其他函数，或者从其他函数返回函数，这是高阶函数的一个特征。

2. 异步操作：在异步编程中，回调函数常用于处理完成某个操作后的结果，比如网络请求、文件读写等。

3. 事件处理：在事件驱动的编程模型中，回调函数用于定义当特定事件发生时应该执行的操作。

4. 非阻塞：在某些场景下，回调函数允许程序在等待异步操作完成时继续执行其他任务，从而实现非阻塞操作。

5. 灵活性：回调函数提供了一种灵活的方式来定义和扩展程序的行为，因为它们允许用户自定义操作。

6. 链式调用：回调函数可以被链式调用，即一个回调函数的执行结果可以作为另一个回调函数的输入。

7. 闭包：回调函数经常与闭包一起使用，闭包允许回调函数访问定义它们的上下文中的变量。

8. 错误处理：在异步操作中，回调函数通常需要处理错误，因此它们经常包含错误处理逻辑。

9. 回调地狱：如果回调函数嵌套过深，会导致所谓的“回调地狱”（Callback Hell），这会使代码难以阅读和维护。

10. 性能考虑：过度使用回调函数可能会导致性能问题，尤其是在大量并发异步操作时。

11. 代码可读性：虽然回调函数提供了灵活性，但不当使用可能会导致代码难以理解，尤其是在多个回调函数嵌套时。