NOTEBOOK one

NOTEBOOK
1.动态规划和贪心算法
  解决最优化问题的算法
  I.确定最优子结构
    每一个可以使用这两种算法中的一个最优化问题都有一个最优子结构———即一个问题的最优解包含其子问题的最优解。
    我们需要做的就是要递归地定义该问题的解。
    递归的求解其更小的子问题。为了缩小其时间复杂度，设置备忘机制、自底向上的搜索。当遇到相同的子问题时避免重复搜索。
    无论使用哪一种算法，都是利用了最优子结构的性质。只不过两种算法做出的选择和考虑的维度不同。
  II.贪心选择
    我们需要知道，并不是每一个最优解问题都满足贪心选择的性质。0-1背包问题和分数背包问题。我们是通过做出局部最优解的选择来构造全局最优解。
    这种选择和动态规划中的每次都是先求解子问题不同，贪心选择每次做出选择之后并不求解任何一个子问题，他是自顶向下的，一次一次地使问题规模变小而不是利用更小的子问题的解。
    贪心选择是安全的：做出贪心选择原问题最优解总是存在。
    做出贪心选择之后，子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解。
    贪心算法通常适用于一些可以分割、可以取舍的问题，而不适用于需要满足特定约束条件的问题。

   动态规划的算法利用了最优子结构的成立的条件，是从底向上解决问题。而贪心算法是在最优子结构和贪心选择成立下，（既然每一次的选择都是子问题的最优解，直接选择当前的最优）从顶向下。
   贪心算法更加简单，但是并不是所有问题都适用。时常它只能得到一个问题的近似解。贪心算法之上必有一个更复杂的动态规划算法。
2.红黑二叉树
  I.满足条件
  节点是红色或黑色：每个节点要么是红色，要么是黑色。
  根节点是黑色：根节点必须是黑色的。
  叶子节点（NIL节点，即空节点）是黑色：叶子节点是指树中不存在的节点，用NIL节点表示。叶子节点被认为是黑色的。
  红色节点的子节点都是黑色：红色节点的子节点不能为红色。也就是说，在红黑二叉树中，不存在两个相连的红色节点。
  从任一节点到其每个叶子节点的简单路径上，包含相同数量的黑色节点：简单路径是指从该节点到叶子节点的路径，不经过重复的节点。这意味着红黑二叉树中的所有路径上的黑色节点数量必须相等。  

  II.红黑二叉树的性质和操作
  黑高：对于红黑树中的任意节点，其黑高指的是从该节点（不包含该节点）到其任意叶子节点的路径上的黑色节点数量。
  一个有 n 个节点的红黑二叉树的最大高度为 2log2(n+1)。

  旋转操作：左旋和右旋。左旋是将一个节点的右子节点提升为新的父节点，同时将原父节点作为左子节点。
  右旋则是左旋的镜像操作。通过旋转操作，可以调整节点的位置，使得树保持平衡。

  插入操作：在红黑树中插入一个新节点时，需要进行相应的调整以维持红黑性质和平衡性。插入操作的一般步骤如下：
  将新节点插入到红黑树中的合适位置，根据二叉搜索树的性质找到适当的位置进行插入。
  将插入的节点标记为红色。（不能是黑色）
  根据插入节点的父节点、叔节点（父节点的兄弟节点）和祖父节点的颜色，进行相应的调整，以满足红黑性质：
  如果插入节点的父节点是黑色，无需进行其他操作。
  如果插入节点的父节点是红色，可能需要进行旋转操作和颜色调整。

  删除操作：在红黑树中删除一个节点时，同样需要进行相应的调整。删除操作的一般步骤如下：
  找到要删除的节点，并确定要用于替换的节点（通常是前驱或后继节点）。
  删除节点并将替换节点放在其位置上。
  根据删除节点、替换节点、替换节点的子节点和兄弟节点的颜色，进行相应的调整，以满足红黑性质：
  如果删除节点是红色，无需进行其他操作。
  如果删除节点是黑色，可能需要进行旋转操作和颜色调整，以确保树的平衡和性质。

  观察红黑二叉树的基本操作，因为一棵红黑二叉树不可能存在两个红色节点相连并且为了满足黑高的定义，插入和删除的操作中，操作节点的旋转、调整故针对于此。

  #include <iostream>
  #include <map>//底层数据结构是红黑二叉树
  #include <set>//同上，有序集合
  #include <unordered_map>//底层数据结构结构是哈希表
  //C++中称之为映射，也分为有序映射（红黑二叉树）和无序映射，Python中称之为字典
  #include <unordered_set>//同上，C++中的无序集合


  //无序性： 集合中的元素是无序的，即集合不保持元素的插入顺序。

   唯一性： 集合中不包含重复的元素，每个元素在集合中只能出现一次。如果尝试向集合中添加已经存在的元素，集合将不会发生变化。

   可变性： 集合是可变类型，可以进行增加、删除等操作。

  集合的主要作用在于去除重复元素，并且在集合上进行集合运算，例如并集、交集、差集等。集合在处理需要去重的数据或进行一些集合操作时非常有用。
int main() {
    // 使用 std::map 存储键-值对，并按键的升序排列
    std::map<std::string, int> ages_map;
    ages_map["Alice"] = 30;
    ages_map["Bob"] = 25;
    ages_map["Charlie"] = 35;

    std::cout << "Using std::map:" << std::endl;
    for (const auto& pair : ages_map) {
        std::cout << pair.first << "'s age: " << pair.second << std::endl;
    }
    std::cout << std::endl;

    // 使用 std::unordered_map 存储键-值对，无序存储
    std::unordered_map<std::string, int> ages_unordered_map;
    ages_unordered_map["Alice"] = 30;
    ages_unordered_map["Bob"] = 25;
    ages_unordered_map["Charlie"] = 35;

    std::cout << "Using std::unordered_map:" << std::endl;
    for (const auto& pair : ages_unordered_map) {
        std::cout << pair.first << "'s age: " << pair.second << std::endl;
    }
    std::cout << std::endl;

    return 0;
}
控制台的打印结果：
Using std::map:
Alice's age: 30
Bob's age: 25
Charlie's age: 35

Using std::unordered_map:
Bob's age: 25
Charlie's age: 35
Alice's age: 30