959. 由斜杠划分的区域

首先来看一下题干，NxN的网格是由多个1x1的正方形组成的，每个正方形里面都可能有斜杠，反斜杠或者空格，把网格分成相邻的区域，返回区域的数量。比如第一个例子，（……）
整体的思路就是，首先将每个1*1的小正方形分为四部分（打开画图），在题目给出的条件下，将能够合并的区域都合并，最终求得剩余区域的个数。（如图所示……四个部分），当这个正方体内的字符是斜杠，…..当这个正方体内的字符是反斜杠…..空格….
说到连通性就能够想到并查集。
这里再复习一下并查集的概念（打开visualgo）
把每一个集合想象成树状结构，初始状态下，每个节点都是一个树根，也就是说他们的父节点是自己，这里有10个节点，也就是十个集合。如果我们想将两个集合合并，比如1和3合并。只需要将1的父节点改为3就可以了，同理（再弄一个在根上）example 合并3集合和6集合，需要做的就是将parent[6]的值设置为3，新的集合就是这个样子。
其次我们怎么判断两个节点是否在同一个集合中呢？当两个节点的树根相同的时候，就认为在同一个集合（比如…）。先写一下查找树根的代码。
其实在这里还存在一个路径压缩的优化，（比如（find(0)））这样做的好处是，当前我们下一次想知道0属于哪个集合的时候，就能不再沿着树爬上来一次了。有了find以后只用判断两个节点的find结果是否相同，就可以知道他们是否属于同一个集合。
继续来写合并的代码union，合并的思路也很简单，就是分别找到待合并的两个节点的根，然后将这两个根连起来就好了。（写代码）在连的时候我们会发现（连38）总是需要把小的集合连在大的集合上。这样做的好处是，能尽量使树结构保持平衡，也就是尽量减少树的深度，从而加快查询效率。要实现的话，需要增加一个数组size，保存每个节点为父节点的子树的节点个数。（初始化，union里面都要加）

1128. 等价多米诺骨牌对的数量

这题如果用暴力解法的话时间复杂度O(N^2)，可以看到题目下方给出数据规模是4万，所以肯定会超时。
我看到一个比较取巧的解法，首先由于多米诺骨牌只有两个数字，那么他们的组合只有100种，可以将这两个数字转换成十进制数字的形式，比如3，1转化成三十一，这样用一个长度为100的数组就能让下标覆盖所有可能的排列情况。然后，下标对应的元素值就是下标数字出现的次数，也就是相同多米诺骨牌的数量。同时，为了解决题目所说的反转的问题，规定十位数必须大于等于个位数，或者反过来也同理，这样就把相等和反转相等统一成了相等。
注意，题目问的是组合数，如果由三个多米诺骨牌等价，那组合数就是C(2,3) = 3 = 1 + 2 C(2, n) = 1 + 2 + … + (n - 1)

博客 资源

1.31

https://www.paincker.com/leetcode-top-k
https://leetcode.com/problems/kth-largest-element-in-an-array/submissions/