并查集中的元素个数
……怎么样去求一个并查集中某一个集合的元素个数呢?究竟在找的时候递归得到答案,并完之后遍历,还是一个一个在合并的时候去查找呢?
基本思想
初始化时将与father数组对应的num数组中的元素全部变为1每一次合并时将被合并集合元素数加到合并到的集合的父节点的num中
=> father[x] = y; //x的爸爸是y=> num[y] += num[x]; //爸爸的元素数再加上孩 ...
二维并查集
一道题目引发的扩展……
岛屿的数量题目
LeetCode给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例1
输入:11110110101100000000
输出: 1
2
输入:11000110000010000011
输出: 3
思路与实现过程这道题 ...
并查集
定义
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。
模版12345678910111213141516171819202122232425262728293031class Unionfind{ private: vector<int&g ...
动态规划
定义及分类
多阶段决策过程的最优化问题。动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。
Code实例01Bag题目
01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为$W_1$,$W_2$至$W_n$,与之相对应的价值为$P_1$,$P_2$至$P_n$。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中 ...
广度优先搜索
BFS主要思想将全部邻接点入队列,以FIFO原则,依次访问所有未访问节点
模版题及其实现最小花费
在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。
输入格式
第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。以下m行每行输入三个正整数x,y,z ...
二叉树的遍历
二叉树
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。
二叉树的定义和结构1234567struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(N ...
线段树
线段树的作用
线段树是一种二叉搜索树,它能以较低时间复杂度O(logN)得解决大规模求和、gcd等空间复杂度为2N,但实际应用时还需4N的空间
查询和单点更改的代码实现123456789101112131415class NumArray{ public: int *tree; int size; NumArray(vector<int> nums) ...
First-blog
First Blog
FormatsTestingTestingtesting
Hyperlink行内形式: Github自动链接: Github http://github.com/GZTimeHacker
List
first item
second item
third item
Table
表头1
表头2
表头3
表头4
默认左对齐
左对齐
居中对其
右对齐
默认左对齐 ...
问
5e15dcdb3bbbdb8d74e8dcafcadae52530b6b8f271318fd724817cb4e9b31b054a68d85ee4907e7862cc9ca265535a088c9aa01e3ad2fdaf2f437b9c4470806fb04a6ff796ca222cfea0846dad925f8049e2ed2875f50b0d0ff09d57a13aec6059838 ...