长春网站优化页面,设计素材网站图片,aspcms中引文 网站修改配置,天津seo排名公司20. 二叉树的定义与操作
二叉树#xff08;binary tree#xff09;是一种非线性数据结构#xff0c;代表着祖先与后代之间的派生关系#xff0c;体现着“一分为二”的分治逻辑 与链表类似#xff0c;二叉树的基本单元是节点#xff0c;每个节点包含#xff1a;值、左子…20. 二叉树的定义与操作
二叉树binary tree是一种非线性数据结构代表着祖先与后代之间的派生关系体现着“一分为二”的分治逻辑 与链表类似二叉树的基本单元是节点每个节点包含值、左子节点引用、右子节点引用 /* 二叉树节点结构体 */
struct TreeNode {int val; // 节点值TreeNode *left; // 左子节点指针TreeNode *right; // 右子节点指针TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};在二叉树中除叶节点外其他所有节点都包含子节点和非空子树 如果将 “节点 2” 视为父节点则其左子节点和右子节点分别是 “节点 4” 和 “节点 5”左子树是 “节点 4 及其以下节点形成的树”右子树是 “节点 5 及其以下节点形成的树” 二叉树常见术语 根节点 root node 位于二叉树顶层的节点没有父节点 叶节点 leaf node 没有子节点的节点其两个指针均指向 None 边 edge 连接两个节点的线段即节点指针 节点所在的层 level 从顶至底递增根节点所在层为 1 节点的度 degree 节点的子节点的数量。在二叉树中度的取值范围是 0、1、2 二叉树的高度 height 从根节点到最远叶节点所经过的边的数量 节点的深度 depth 从根节点到该节点所经过的边的数量 节点的高度 height 从最远叶节点到该节点所经过的边的数量 二叉树常见操作/* 1、初始化二叉树 */
// 与链表类似首先初始化节点然后构建指针
// 初始化节点
TreeNode* n1 new TreeNode(1);
TreeNode* n2 new TreeNode(2);
TreeNode* n3 new TreeNode(3);
TreeNode* n4 new TreeNode(4);
TreeNode* n5 new TreeNode(5);
// 构建指针指向
n1-left n2;
n1-right n3;
n2-left n4;
n2-right n5;/* 2、插入与删除节点 */
// 与链表类似在二叉树中插入与删除节点可以通过修改指针来实现
TreeNode* P new TreeNode(0);
// 在 n1 - n2 中间插入节点 P
n1-left P;
P-left n2;
// 删除节点 P
n1-left n2;21. 常见二叉树类型
完美二叉树满二叉树 完美二叉树perfect binary tree所有层的节点都被完全填满。在完美二叉树中叶节点的度为 0其余所有节点的度都为 2若树高度为 h则节点总数为 2 h 1 − 1 2^{h1}-1 2h1−1呈现标准的指数级关系反映了自然界中常见的细胞分裂现象 完全二叉树 完全二叉树complete binary tree只有最底层的节点未被填满且最底层节点尽量靠左填充 完满二叉树 完满二叉树full binary tree除了叶节点之外其余所有节点都有两个子节点 平衡二叉树 平衡二叉树balanced binary tree中任意节点的左子树和右子树的高度之差的绝对值不超过 1 22. 二叉树的退化
当二叉树的每层节点都被填满时达到 “完美二叉树”而当所有节点都偏向一侧时二叉树退化为 “链表” 完美二叉树是理想情况可以充分发挥二叉树 “分治” 的优势链表则是另一个极端各项操作都变为线性操作时间复杂度退化至 O(n)
23. 二叉树遍历 从物理结构的角度来看树是一种基于链表的数据结构因此其遍历方式是通过指针逐个访问节点。然而树是一种非线性数据结构这使得遍历树比遍历链表更加复杂需要借助搜索算法来实现 二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等
23.1 层序遍历
层序遍历level-order traversal从顶部到底部逐层遍历二叉树并在每一层按照从左到右的顺序访问节点 层序遍历本质上属于广度优先遍历breadth-first traversal它体现了 “一圈一圈向外扩展” 的逐层遍历思想 广度优先遍历通常借助 “队列” 来实现。队列遵循 “先进先出” 的规则而广度优先遍历则遵循 “逐层推进” 的规则两者背后的思想是一致的/* 层序遍历 */
// 时间复杂度所有节点被访问一次使用 O(n) 时间其中 n 为节点数量
// 空间复杂度在最差情况下即满二叉树时遍历到最底层之前队列中最多同时存在 (n1)/2 个节点占用 O(n) 空间
vectorint levelOrder(TreeNode *root) {// 初始化队列加入根节点queueTreeNode * queue;queue.push(root);// 初始化一个列表用于保存遍历序列vectorint vec;while (!queue.empty()) {TreeNode *node queue.front();queue.pop(); // 队列出队vec.push_back(node-val); // 保存节点值if (node-left ! nullptr)queue.push(node-left); // 左子节点入队if (node-right ! nullptr)queue.push(node-right); // 右子节点入队}return vec;
}23.2 前序、中序、后序遍历
前序、中序和后序遍历都属于深度优先遍历depth-first traversal体现 “先走到尽头再回溯继续” 的思想下图展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整个二叉树的外围 “走” 一圈在每个节点都会遇到三个位置分别对应前序遍历、中序遍历和后序遍历 深度优先搜索通常基于递归实现// 时间复杂度所有节点被访问一次使用 O(n) 时间
// 空间复杂度在最差情况下即树退化为链表时递归深度达到 n系统占用 O(n) 栈帧空间
/* 前序遍历 */
void preOrder(TreeNode *root) {if (root nullptr)return;// 访问优先级根节点 - 左子树 - 右子树vec.push_back(root-val);preOrder(root-left);preOrder(root-right);
}/* 中序遍历 */
void inOrder(TreeNode *root) {if (root nullptr)return;// 访问优先级左子树 - 根节点 - 右子树inOrder(root-left);vec.push_back(root-val);inOrder(root-right);
}/* 后序遍历 */
void postOrder(TreeNode *root) {if (root nullptr)return;// 访问优先级左子树 - 右子树 - 根节点postOrder(root-left);postOrder(root-right);vec.push_back(root-val);
}前序遍历二叉树的递归过程可分为 “递” 和 “归” 两个逆向的部分 “递” 表示开启新方法程序在此过程中访问下一个节点“归” 表示函数返回代表当前节点已经访问完毕 24. 二叉搜索树
如下图所示二叉搜索树binary search tree满足以下条件 对于根节点左子树中所有节点的值 根节点的值 右子树中所有节点的值任意节点的左、右子树也是二叉搜索树即同样满足上述条件 24.1 二叉搜索树的操作 1、查找节点 给定目标节点值 num可以根据二叉搜索树的性质来查找。声明一个节点 cur从二叉树的根节点 root 出发循环比较节点值 cur.val 和 num 之间的大小关系 若 cur.val num 说明目标节点在 cur 的右子树中因此执行 cur cur.right若 cur.val num 说明目标节点在 cur 的左子树中因此执行 cur cur.left若 cur.val num 说明找到目标节点跳出循环并返回该节点 二叉搜索树的查找操作与二分查找算法的工作原理一致都是每轮排除一半情况。循环次数最多为二叉树的高度当二叉树平衡时使用 O(log n) 时间 /* 查找节点 */
TreeNode *search(int num) {TreeNode *cur root;// 循环查找越过叶节点后跳出while (cur ! nullptr) {// 目标节点在 cur 的右子树中if (cur-val num)cur cur-right;// 目标节点在 cur 的左子树中else if (cur-val num)cur cur-left;// 找到目标节点跳出循环elsebreak;}// 返回目标节点return cur;
}2、插入节点 给定一个待插入元素 num为保持二叉搜索树 “左子树 根节点 右子树” 性质插入操作流程如下图所示 查找节点插入位置与查找操作相似从根节点出发根据当前节点值和 num 的大小关系循环向下搜索直到越过叶节点遍历至 None时跳出循环在该位置插入节点初始化节点 num将该节点置于 None 的位置 在代码实现中需要注意以下两点 二叉搜索树不允许存在重复节点否则将违反其定义。因此若待插入节点在树中已存在则不执行插入直接返回为实现插入节点需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时可以获取到其父节点从而完成节点插入操作 // 时间复杂度O(log n)
void insert(int num) {// 若树为空则初始化根节点if (root nullptr) {root new TreeNode(num);return;}TreeNode *cur root, *pre nullptr;// 循环查找越过叶节点后跳出while (cur ! nullptr) {// 找到重复节点直接返回if (cur-val num)return;pre cur;// 插入位置在 cur 的右子树中if (cur-val num)cur cur-right;// 插入位置在 cur 的左子树中elsecur cur-left;}// 插入节点TreeNode *node new TreeNode(num);if (pre-val num)pre-right node;elsepre-left node;
}3、删除节点 先在二叉树中查找到目标节点再将其从二叉树中删除。与插入节点类似需要保证在删除操作完成后二叉搜索树的 “左子树 根节点 右子树” 的性质仍然满足。需要根据目标节点的子节点数量共分为 0、1 和 2 这三种情况执行对应的删除节点操作 3.1 当待删除节点的度为 0 时表示该节点是叶节点可以直接删除 3.2 当待删除节点的度为 1 时将待删除节点替换为其子节点即可 3.3 当待删除节点的度为 2 时无法直接删除它而需要使用一个节点替换该节点 由于要保持二叉搜索树 “左 根 右” 的性质因此这个节点可以是右子树的最小节点或左子树的最大节点假设选择右子树的最小节点即中序遍历的下一个节点则删除操作流程如下 查找 cur 在中序遍历的后继节点 nex在二叉树中递归删除节点 nex将节点 nex 值赋给节点 cur // 时间复杂度O(log n)
// 其中查找待删除节点需要 O(log n) 时间获取中序遍历后继节点需要 O(log n) 时间
void remove(int num) {// 若树为空直接提前返回if (root nullptr)return;TreeNode *cur root, *pre nullptr;// 循环查找越过叶节点后跳出while (cur ! nullptr) {// 找到待删除节点跳出循环if (cur-val num)break;pre cur;// 待删除节点在 cur 的右子树中if (cur-val num)cur cur-right;// 待删除节点在 cur 的左子树中elsecur cur-left;}// 若无待删除节点则直接返回if (cur nullptr)return;// 1、子节点数量 0 or 1if (cur-left nullptr || cur-right nullptr) {// 当子节点数量 0 / 1 时 child nullptr / 该子节点TreeNode *child cur-left ! nullptr ? cur-left : cur-right;// 删除节点 curif (cur ! root) {if (pre-left cur)pre-left child;elsepre-right child;} else {// 若删除节点为根节点则重新指定根节点root child;}// 释放内存delete cur;}// 2、子节点数量 2else {// 获取中序遍历中 cur 的下一个节点TreeNode *tmp cur-right;while (tmp-left ! nullptr) {tmp tmp-left;}int tmpVal tmp-val;// 递归删除节点 tmpremove(tmp-val);// 用 tmp 覆盖 curcur-val tmpVal;}
}4、中序遍历有序 二叉树的中序遍历遵循 “左 根 右” 的遍历顺序而二叉搜索树满足 “左子节点 根节点 右子节点” 的大小关系。这意味着在二叉搜索树中进行中序遍历时总是会优先遍历下一个最小节点从而得出一个重要性质二叉搜索树的中序遍历序列是升序的利用中序遍历升序的性质在二叉搜索树中获取有序数据仅需 O(n) 时间无须进行额外的排序操作非常高效 24.2 二叉搜索树的效率
二叉搜索树的各项操作的时间复杂度都是对数阶具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下数组比二叉搜索树的效率更高 在理想情况下二叉搜索树是 “平衡” 的这样就可以在 l o g n log n logn 轮循环内查找任意节点。然而如果在二叉搜索树中不断地插入和删除节点可能导致二叉树退化为下图所示的链表这时各种操作的时间复杂度也会退化为 O(n) 在完美二叉树中插入两个节点后树将严重向左倾斜查找操作的时间复杂度也随之恶化 25. AVL 树
AVL 树既是二叉搜索树也是平衡二叉树同时满足这两类二叉树的所有性质因此也被称为平衡二叉搜索树balanced binary search tree/* AVL 树节点类 */
struct TreeNode {int val{}; // 节点值int height 0; // 节点高度TreeNode *left{}; // 左子节点TreeNode *right{}; // 右子节点TreeNode() default;explicit TreeNode(int x) : val(x){}
};节点高度由于 AVL 树的相关操作需要获取节点高度因此需要为节点类添加 height 变量 节点高度是指从该节点到最远叶节点的距离即所经过的边的数量需要特别注意的是叶节点的高度为 0而空节点的高度为 -1 /* 获取节点高度 */
int height(TreeNode *node) {// 空节点高度为 -1 叶节点高度为 0return node nullptr ? -1 : node-height;
}/* 更新节点高度 */
void updateHeight(TreeNode *node) {// 节点高度等于最高子树高度 1node-height max(height(node-left), height(node-right)) 1;
}节点平衡因子节点左子树的高度减去右子树的高度同时规定空节点的平衡因子为 0 设平衡因子为 f则一棵 AVL 树的任意节点的平衡因子皆满足 -1 f 1 /* 获取平衡因子 */
int balanceFactor(TreeNode *node) {// 空节点平衡因子为 0if (node nullptr)return 0;// 节点平衡因子 左子树高度 - 右子树高度return height(node-left) - height(node-right);
}26. AVL 树旋转
AVL 树的特点在于 “旋转” 操作它能够在不影响二叉树的中序遍历序列的前提下使失衡节点重新恢复平衡 换句话说旋转操作既能保持 “二叉搜索树” 的性质也能使树重新变为 “平衡二叉树” 将平衡因子绝对值 1 的节点称为 “失衡节点” 根据节点失衡情况的不同旋转操作分为四种右旋、左旋、先右旋后左旋、先左旋后右旋
26.1 右旋
如下图所示节点下方为平衡因子 从底至顶看二叉树中首个失衡节点是 “节点 3”关注以该失衡节点为根节点的子树将该节点记为 node其左子节点记为 child执行 “右旋” 操作以 child 为原点将 node 向右旋转右旋完成后用 child 替代以前 node 的位置子树已恢复平衡并仍保持二叉搜索树的特性 如下图所示当节点 child 有右子节点记为 grandChild时需要在右旋中添加一步将 grandChild 作为 node 的左子节点 /* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {TreeNode *child node-left;TreeNode *grandChild child-right;// 以 child 为原点将 node 向右旋转child-right node;node-left grandChild;// 更新节点高度updateHeight(node);updateHeight(child);// 返回旋转后子树的根节点return child;
}26.2 左旋 /* 左旋操作 */
TreeNode *leftRotate(TreeNode *node) {TreeNode *child node-right;TreeNode *grandChild child-left;// 以 child 为原点将 node 向左旋转child-left node;node-right grandChild;// 更新节点高度updateHeight(node);updateHeight(child);// 返回旋转后子树的根节点return child;
}26.3 先左旋后右旋
对于下图中的失衡节点 3仅使用左旋或右旋都无法使子树恢复平衡 此时需要先对 child 执行 “左旋”再对 node 执行 “右旋” 26.4 先右旋后左旋 26.5 旋转的选择 如下表通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号来确定失衡节点属于上图哪种情况 为便于使用将旋转操作封装成一个函数。通过这个函数就能对各种失衡情况进行旋转使失衡节点重新恢复平衡/* 执行旋转操作使该子树重新恢复平衡 */
TreeNode *rotate(TreeNode *node) {// 获取节点 node 的平衡因子int _balanceFactor balanceFactor(node);// 左偏树if (_balanceFactor 1) {if (balanceFactor(node-left) 0) {// 右旋return rightRotate(node);} else {// 先左旋后右旋node-left leftRotate(node-left);return rightRotate(node);}}// 右偏树if (_balanceFactor -1) {if (balanceFactor(node-right) 0) {// 左旋return leftRotate(node);} else {// 先右旋后左旋node-right rightRotate(node-right);return leftRotate(node);}}// 平衡树无须旋转直接返回return node;
}27. 堆
堆heap是一种满足特定条件的完全二叉树主要可分为下图所示的两种类型 小顶堆 min heap任意节点的值 ≤ 其子节点的值大顶堆 max heap任意节点的值 ≥ 其子节点的值 堆作为完全二叉树的一个特例具有以下特性 最底层节点靠左填充其他层的节点都被填满将二叉树的根节点称为 “堆顶”将底层最靠右的节点称为 “堆底”对于大顶堆小顶堆堆顶元素即根节点的值分别是最大最小的 堆常用操作/* 初始化堆 */
priority_queueint, vectorint, greaterint minHeap; // 初始化小顶堆
priority_queueint, vectorint, lessint maxHeap; // 初始化大顶堆/* 元素入堆 */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);/* 获取堆顶元素 */
int peek maxHeap.top(); // 5/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1/* 获取堆大小 */
int size maxHeap.size();/* 判断堆是否为空 */
bool isEmpty maxHeap.empty();/* 输入列表并建堆 */
vectorint input{1, 3, 2, 5, 4};
priority_queueint, vectorint, greaterint minHeap(input.begin(), input.end());堆常见应用 优先队列 堆通常作为实现优先队列的首选数据结构其入队和出队操作的时间复杂度均为 O(log n) 堆排序 给定一组数据可以用它们建立一个堆然后不断地执行元素出堆操作从而得到有序数据 获取最大的 k 个元素Top-K 问题 例如选择热度前 10 的新闻作为微博热搜选取销量前 10 的商品等
28. 建堆操作 使用一个列表的所有元素来构建一个堆的过程被称为 “建堆操作” 28.1 借助入堆操作实现
首先创建一个空堆然后遍历列表依次对每个元素执行 “入堆操作”即先将元素添加至堆的尾部再对该元素执行 “从底至顶” 堆化 每当一个元素入堆堆的长度就加一。由于节点是从顶到底依次被添加进二叉树的因此堆是 “自上而下” 构建的设元素数量为 n每个元素的入堆操作使用 O(log n) 时间因此该建堆方法的时间复杂度为 O(nlog n)
28.2 通过遍历堆化实现 实际可以实现一种更为高效的建堆方法共分为两步 将列表所有元素原封不动添加到堆中此时堆的性质尚未得到满足倒序遍历堆即层序遍历的倒序依次对每个非叶节点执行 “从顶至底堆化” 每当堆化一个节点后以该节点为根节点的子树就形成一个合法的子堆。而由于是倒序遍历因此堆是 “自下而上” 被构建的 之所以选择倒序遍历是因为能保证当前节点之下的子树已经是合法的子堆这样堆化当前节点才是有效的 叶节点没有子节点天然就是合法的子堆因此无需堆化 如以下代码所示最后一个非叶节点是最后一个节点的父节点从它开始倒序遍历并执行堆化 /* 构造方法根据输入列表建堆 */
MaxHeap(vectorint nums) {// 将列表元素原封不动添加进堆maxHeap nums;// 堆化除叶节点以外的其他所有节点for (int i parent(size() - 1); i 0; i--) {siftDown(i);}
}29. Top-K 问题 给定一个长度为 n 的无序数组 nums请返回数组中前 k 大的元素 基于堆更加高效地解决 Top-K 问题步骤如下 初始化一个小顶堆其堆顶元素最小先将数组的前 k 个元素依次入堆从第 k1 个元素开始若当前元素大于堆顶元素则将堆顶元素出堆并将当前元素入堆遍历完成后堆中保存的就是最大的 k 个元素 总共执行了 n 轮入堆和出堆堆的最大长度为 k因此时间复杂度为 O(nlog k)。该方法的效率很高当 k 较小时时间复杂度趋向 O(n)当 k 较大时时间复杂度不会超过 O(nlog n) 该方法适用于动态数据流使用场景。在不断加入数据时可以持续维护堆内的元素从而实现最大个元素的动态更新 /* 基于堆查找数组中最大的 k 个元素 */
priority_queueint, vectorint, greaterint topKHeap(vectorint nums, int k) {priority_queueint, vectorint, greaterint heap;// 将数组的前 k 个元素入堆for (int i 0; i k; i) {heap.push(nums[i]);}// 从第 k1 个元素开始保持堆的长度为 kfor (int i k; i nums.size(); i) {// 若当前元素大于堆顶元素则将堆顶元素出堆、当前元素入堆if (nums[i] heap.top()) {heap.pop();heap.push(nums[i]);}}return heap;
}30. 图
图graph是一种非线性数据结构由顶点vertex和边edge组成。可以将图 G 抽象地表示为一组顶点 V 和一组边 E 的集合。以下示例展示了一个包含 5 个顶点和 7 条边的图 如果将顶点看作节点将边看作连接各个节点的指针就可将图看作是一种从链表拓展而来的数据结构。如下图相较于线性关系链表和分治关系树网络关系图的自由度更高从而更为复杂 30.1 图常见类型
根据边是否具有方向可分为下图所示的无向图和有向图 在无向图中边表示两顶点之间的 “双向” 连接关系 例如微信或 QQ 中的 “好友关系” 在有向图中边具有方向性即 A → B 和 B → A 两个方向的边是相互独立的 例如微博或抖音上的 “关注” 与 “被关注” 关系 根据所有顶点是否连通可分为下图所示的连通图和非连通图 对于连通图从某个顶点出发可以到达其余任意顶点对于非连通图从某个顶点出发至少有一个顶点无法到达 可以为边添加 “权重” 变量从而得到下图所示的有权图 例如在王者荣耀等手游中系统会根据共同游戏时间来计算玩家之间的 “亲密度”这种亲密度网络就可以用有权图来表示 30.2 图常见术语
邻接 adjacency 当两顶点之间存在边相连时称这两顶点 “邻接” 路径 path 从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的 “路径” 度 degree 一个顶点拥有的边数对于有向图入度表示有多少条边指向该顶点出度表示有多少条边从该顶点指出
30.3 图的表示
30.3.1 邻接矩阵 设图的顶点数量为 n邻接矩阵使用一个 n×n 大小的矩阵来表示图每一行列代表一个顶点矩阵元素代表边用 1 或 0 表示两个顶点之间是否存在边 如下图所示设邻接矩阵为 M、顶点列表为 V那么矩阵元素 M[i, j] 1 表示顶点 V[i] 到顶点 V[j] 之间存在边反之M[i, j] 0 表示两顶点之间无边 邻接矩阵具有以下特性 顶点不能与自身相连因此邻接矩阵主对角线元素没有意义对于无向图两个方向的边等价此时邻接矩阵关于主对角线对称将邻接矩阵的元素从 1 和 0 替换为权重则可表示有权图 使用邻接矩阵表示图时可以直接访问矩阵元素以获取边因此增删查操作的效率很高时间复杂度均为 O(1)。然而矩阵的空间复杂度为 O(n^2)内存占用较多
30.3.2 邻接表
邻接表使用 n 个链表来表示图链表节点表示顶点。第 i 条链表对应顶点 i其中存储了该顶点的所有邻接顶点即与该顶点相连的顶点。下图展示了一个使用邻接表存储的图的示例 邻接表仅存储实际存在的边而边的总数通常远小于 n^2因此它更加节省空间。然而在邻接表中需要通过遍历链表来查找边因此其时间效率不如邻接矩阵
31. 分治
分治divide and conquer通常基于递归实现包括 “分” 和 “治” 两个步骤 分划分阶段递归地将原问题分解为两个或多个子问题直至到达最小子问题时终止治合并阶段从已知解的最小子问题开始从底至顶地将子问题的解进行合并从而构建出原问题的解 “归并排序” 是分治策略的典型应用之一 分递归地将原数组原问题划分为两个子数组子问题直到子数组只剩一个元素最小子问题治从底至顶地将有序的子数组子问题的解进行合并从而得到有序的原数组原问题的解 如何判断分治问题 问题可以被分解原问题可以被分解成规模更小、类似的子问题以及能够以相同方式递归地进行划分子问题是独立的子问题之间是没有重叠的互相没有依赖可以被独立解决子问题的解可以被合并原问题的解通过合并子问题的解得来 通过分治提升效率 分治不仅可以有效地解决算法问题往往还可以带来算法效率的提升。在排序算法中快速排序、归并排序、堆排序相较于选择、冒泡、插入排序更快就是因为它们应用了分治策略 分治常见应用 1、寻找最近点对 该算法首先将点集分成两部分然后分别找出两部分中的最近点对最后再找出跨越两部分的最近点对 2、大整数乘法 例如 Karatsuba 算法它是将大整数乘法分解为几个较小的整数的乘法和加法 3、矩阵乘法 例如 Strassen 算法它是将大矩阵乘法分解为多个小矩阵的乘法和加法 4、汉诺塔问题 汉诺塔问题可以视为典型的分治策略通过递归解决 5、求解逆序对 在一个序列中如果前面的数字大于后面的数字那么这两个数字构成一个逆序对。求解逆序对问题可以通过分治的思想借助归并排序进行求解
32. 回溯
回溯算法是一种通过穷举来解决问题的方法它的核心思想是从一个初始状态出发暴力搜索所有可能的解决方案当遇到正确的解则将其记录直到找到解或者尝试了所有可能的选择都无法找到解为止 回溯算法通常采用 “深度优先搜索” 来遍历解空间前序、中序和后序遍历都属于深度优先搜索 回溯算法本质上是一种深度优先搜索算法它尝试所有可能的解决方案直到找到满足条件的解 这种方法的优势在于它能够找到所有可能的解决方案而且在合理的剪枝操作下具有很高的效率在处理大规模或者复杂问题时回溯算法的运行效率可能难以接受 时间回溯算法通常需要遍历状态空间的所有可能时间复杂度可以达到指数阶或阶乘阶空间在递归调用中需要保存当前的状态例如路径、用于剪枝的辅助变量等当深度很大时空间需求可能会变得很大 常见的效率优化方法 剪枝避免搜索那些肯定不会产生解的路径从而节省时间和空间启发式搜索在搜索过程中引入一些策略或者估计值从而优先搜索最有可能产生有效解的路径
33. 动态规划 动态规划将一个问题分解为一系列更小的子问题并通过存储子问题的解来避免重复计算从而大幅提升时间效率 问题给定一个共有 n 阶的楼梯你每步可以上 1 阶或者 2 阶请问有多少种方案可以爬到楼顶下图所示对于一个 3 阶楼梯共有 3 种方案可以爬到楼顶 本题的目标是求解方案数量可以考虑通过回溯来穷举所有可能性。具体来说将爬楼梯想象为一个多轮选择的过程从地面出发每轮选择上 1 阶或 2 阶每当到达楼梯顶部时就将方案数量加 1当越过楼梯顶部时就将其剪枝 动态规划是一种 “从底至顶” 的方法从最小子问题的解开始迭代地构建更大子问题的解直至得到原问题的解 由于动态规划不包含回溯过程因此只需使用循环迭代实现无须使用递归。在以下代码中初始化一个数组 dp 来存储子问题的解 /* 爬楼梯动态规划 */
int climbingStairsDP(int n) {if (n 1 || n 2)return n;// 初始化 dp 表用于存储子问题的解vectorint dp(n 1);// 初始状态预设最小子问题的解dp[1] 1;dp[2] 2;// 状态转移从较小子问题逐步求解较大子问题for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];
}根据以上内容总结出动态规划的常用术语 将数组 d p dp dp 称为 d p dp dp 表 d p [ i ] dp[i] dp[i] 表示状态 i i i 对应子问题的解将最小子问题对应的状态即第 1 和 2 阶楼梯称为初始状态将递推公式 d p [ i ] d p [ i − 1 ] d p [ i − 2 ] dp[i]dp[i-1]dp[i-2] dp[i]dp[i−1]dp[i−2] 称为状态转移方程 34. 贪心算法 贪心算法是一种常见的解决优化问题的算法其基本思想是在问题的每个决策阶段都选择当前看起来最优的选择即贪心地做出局部最优的决策以期望获得全局最优解 贪心算法和动态规划都常用于解决优化问题它们之间的区别如下 动态规划会根据之前阶段的所有决策来考虑当前决策并使用过去子问题的解来构建当前子问题的解贪心算法不会重新考虑过去的决策而是一路向前地进行贪心选择不断缩小问题范围直至问题被解决 问题给定 n 种硬币第 i 种硬币的面值为 coins[i-1]目标金额为 amt每种硬币可以重复选取问能够凑出目标金额的最少硬币个数如果无法凑出目标金额则返回 -1 /* 零钱兑换贪心 */
int coinChangeGreedy(vectorint coins, int amt) {// 假设 coins 列表有序int i coins.size() - 1;int count 0;// 循环进行贪心选择直到无剩余金额while (amt 0) {// 找到小于且最接近剩余金额的硬币while (i 0 coins[i] amt) {i--;}// 选择 coins[i]amt - coins[i];count;}// 若未找到可行方案则返回 -1return amt 0 ? count : -1;
}34.1 贪心算法优缺点
贪心算法不仅操作直接、实现简单而且通常效率也很高。在以上代码中记硬币最小面值为 m i n ( c o i n s ) min(coins) min(coins)则贪心选择最多循环 a m t / m i n ( c o i n s ) amt/min(coins) amt/min(coins) 次时间复杂度为 O ( a m t / m i n ( c o i n s ) ) O(amt/min(coins)) O(amt/min(coins))。这比动态规划解法的时间复杂度 O ( n ∗ a m t ) O(n*amt) O(n∗amt) 提升了一个数量级然而对于某些硬币面值组合贪心算法并不能找到最优解 正例 c o i n s [ 1 , 5 , 10 , 20 , 50 , 100 ] coins [1, 5, 10, 20, 50, 100] coins[1,5,10,20,50,100]在该硬币组合下给定任意 a m t amt amt贪心算法都可以找出最优解反例 1 c o i n s [ 1 , 20 , 50 ] coins [1, 20, 50] coins[1,20,50]假设 a m t 60 amt 60 amt60贪心算法只能找到 50 1 × 10 50 1×10 501×10 的兑换组合共计 11 枚硬币但动态规划可以找到最优解 20 20 20 20 20 20 202020仅需 3 枚硬币反例 2 c o i n s [ 1 , 49 , 50 ] coins [1, 49, 50] coins[1,49,50]假设 a m t 98 amt 98 amt98贪心算法只能找到 50 1 × 48 50 1×48 501×48 的兑换组合共计 49 枚硬币但动态规划可以找到最优解 49 49 49 49 4949仅需 2 枚硬币 一般情况下贪心算法适用于以下两类问题 可以保证找到最优解贪心算法在这种情况下往往是最优选择因为它往往比回溯、动态规划更高效可以找到近似最优解对于很多复杂问题来说寻找全局最优解是非常困难的能以较高效率找到次优解也是非常不错的
34.2 贪心典型例题
硬币找零问题 在某些硬币组合下贪心算法总是可以得到最优解 区间调度问题 假设你有一些任务每个任务在一段时间内进行你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务那么贪心算法就可以得到最优解 分数背包问题 给定一组物品和一个载重量你的目标是选择一组物品使得总重量不超过载重量且总价值最大。如果每次都选择性价比最高价值 / 重量的物品那么贪心算法在一些情况下可以得到最优解 股票买卖问题 给定一组股票的历史价格你可以进行多次买卖但如果你已经持有股票那么在卖出之前不能再买目标是获取最大利润 霍夫曼编码 霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树每次选择出现频率最小的两个节点合并最后得到的霍夫曼树的带权路径长度即编码长度最小 Dijkstra 算法 它是一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法
