位运算基础知识
正数和负数在二进制中的表达正数的二进制状态转负数的二进制： -1 依次取反 例：7的二进制为 0111 转为负数则为 0110 -> 1001 负数的二进制状态转正数的二进制，为逆过程： 依次取反 +1 例：-7的二进制为 1001 转为正数则为 0110 -> 0111 常见的位运算操作符 | 或 相同位次中只要出现1则返回1 如 0010 |...
排序算法总结
辅助函数12345678910111213// 交换函数void swap(vector<int>& nums, int x, int y) { int tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp;}// 测试函数void test(vector<int>...
平衡二叉树(AVL树)与二叉搜索树
二叉搜索树/二叉排序树定义满足以下特征的二叉树，即为二叉搜索树： 若左子树非空，则左子树上的所有节点要小于根节点 若右子树非空，则右子树上的所有节点要大于根节点 所有子结构满足上面两个条件 平衡二叉树的定义平衡二叉树，满足以下特征： 左右子树的高度差不超过1 所有子结构满足条件1 使用平衡二叉树优化二叉搜索树二叉搜索树在理想情况下查找效率是O(lo...
图的最短路径—Floyd算法和Bellman-Ford算法
Floyd算法借助邻接矩阵辅助，Floyd算法可以解决数据量不大，且权值中有负数的图，但不能是存在负环的图的最短路径问题。该算法步骤如下： 在n个节点中寻找”跳点”bridge 如果graph[from][bridge] != INT_MAX && graph[bridge][to] != INT_MAX && graph[f...
最小生成树—kruskal和prim算法
Kruskal算法模版 按各边权值进行从小到大排序 检测是否有环（使用并查集） 如果两节点属于同一个集合 则说明有环 如果两节点不属于同一个集合 不成环则进行合并 借助洛谷上的最小生成树 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。输入格式 第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。 接下来 M...