1. 堆的基本概念

堆是一种特殊的完全二叉树，分为大根堆（大顶堆）和小根堆（小顶堆）：

• 大根堆（大顶堆）：父节点的值总是大于或等于子节点的值
• 小根堆（小顶堆）：父节点的值总是小于或等于子节点的值

堆通常用数组实现，对于数组中的第i个节点：

• 其左子节点的位置：2i + 1
• 其右子节点的位置：2i + 2
• 其父节点的位置：(i - 1) / 2

2. 堆的基本实现

下面是一个小根堆的Java实现：

双指针是一种重要的算法技巧，使用两个指针对数组或链表进行操作。

一、对撞指针

对撞指针是指两个指针从数组的两端向中间移动。

1. 经典问题：两数之和

给定一个已按照升序排列的数组，找出两个数使得它们的和等于目标数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

基本规则

1. 每个结点或是红色，或是黑色的。
2. 根结点是黑色的。
3. 叶结点 (虚构的外部结点、NULL结点) 都是黑色的。
4. 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的)。
5. 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。

简记为：左根右（二叉排序树），根叶黑，不红红，黑路同（黑高相同）

插入规则

要求数组中严格递增的最长公共子序列，解题思路可以从简单到复杂逐步展开。以下是逐步深入的解题思路：

1. 暴力求解

• 思路: 最简单的方式就是直接穷举数组的所有子序列，并检查这些子序列是否是严格递增的。找到所有严格递增的子序列后，选择其中长度最长的一个。
• 步骤:
  1. 生成数组的所有可能的子序列。
  2. 对每个子序列进行判断，检查是否严格递增。
  3. 返回长度最长的严格递增子序列。

概述

B树（B-Tree）与二叉树（Binary Tree）不是一个概念，其中-是连接符，不是减号，有些人会读成B减树，这是错误的。它可以翻译成Balance Tree，或者是Bayer Tree。

B树是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。

B树与AVL树不同，可以拥有2个以上的子节点，并且每个节点可以有多个键值，这些属性减少了定位记录时所经历的中间过程，加快了存取速度。B树更适用于读写相对较大的数据块存储系统，如磁盘。这种数据结构常被应用在数据库和文件系统的实现上。

迪杰斯特拉算法介绍

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

基本思想

通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

问题分析

在一个有n个节点的无向连通图G = (V, E)中，V表示顶点集，E表示边集。只需n-1条边就可以使这个图连通，n-1条边要想保证图连通，就必须不含回路，所以我们只需要找出n-1条权值最小且无回路的边即可。

需要明确几个概念：

• 生成子图：选中一些边和所有顶点组成的图，称为原图的生成子图。

最小生成树

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。

背包问题是一种经典的优化问题。有的时候我们需要将有一堆不同重量或者体积的物品放入背包，但是背包容量有限，这时就要寻找一种最优的物品组合，也就是让背包中的物品价值最大化或者重量最小化。

背包问题分为0/1背包问题和分数背包问题。

• 0/1背包问题是指在背包容量一定的情况下，每个物品只能选择放入背包一次或不放入，要求放入背包中的物品的总价值最大化或者总重量最小化。
• 分数背包问题是指在背包容量一定的情况下，每个物品可以选择放入部分或全部，要求放入背包中的物品的总价值最大化或者总重量最小化。