赞
踩
- 目 录
-
- 1 九阴真经第一式 :单调栈... 6
-
- 1.1 代表题目:最大矩形... 6
-
- 1.2 单调栈介绍(https://zhuanlan.zhihu.com/p/26465701)... 6
-
- 1.2.1 单调栈的性质:.... 11
-
- 1.3 触类旁通:... 12
-
- 1.3.1 每日温度(739) 12
-
- 1.3.2 下一个更大元素II(503)... 15
-
- 1.3.3 柱状图中最大矩形(84_困难)... 16
-
- 1.3.4 接雨水(42_困难_性能敏感)... 16
-
- 1.3.5 股票价格跨度(901)... 18
-
- 1.3.6 滑动窗口最大值(239_困难_O(n)时间复杂度解决)... 18
-
- 2 九阴真经第二式 :并查集... 19
-
- 2.1 代表题目:朋友圈... 19
-
- 2.2 并查集介绍... 19
-
- 2.3 触类旁通... 24
-
- 2.3.1 朋友圈的参考解法(547)... 24
-
- 2.3.2 冗余连接(684)... 27
-
- 2.3.3 岛屿数量(200_必做)... 27
-
- 2.3.4 句子相似性II (737_会员) 31
-
- 2.3.5 得分最高的路径(1102_会员)... 37
-
- 2.3.6 最低成本联通所有城市(1135_会员)... 44
-
- 2.3.7 以图辨树(261_会员)... 47
-
- 2.3.8 按字典序排列最小的等效字符串(1061_会员)... 50
-
- 2.3.9 无向图中连通分量的数目(323_会员)... 51
-
- 2.3.10 尽量减少恶意软件的传播(924_困难)... 51
-
- 3 九阴真经第三式 :滑动窗口... 54
-
- 3.1 代表题目:尽可能使字符串相等(1208)... 54
-
- 3.2 滑动窗口介绍... 55
-
- 3.2.1 Leetcode 209. 长度最小的子数组... 55
-
- 3.2.2 Leetcode 3. 无重复字符的最长子串... 57
-
- 3.2.1 Leetcode 1004. 最大连续1的个数 III 57
-
- 3.3 触类旁通... 58
-
- 3.3.1 尽可能使字符串相等(1208)的一种解法... 58
-
- 3.3.2 340. 至多包含 K 个不同字符的最长子串(会员_困难)... 59
-
- 3.3.3 1151. 最少交换次数来组合所有的 1(会员)... 63
-
- 3.3.4 159. 至多包含两个不同字符的最长子串(会员)... 63
-
- 3.3.5 1100. 长度为 K 的无重复字符子串(会员)... 64
-
- 4 九阴真经第四式 :前缀和 & HASH.. 65
-
- 4.1 代表题目:560. 和为K的子数组... 65
-
- 4.2 前缀和介绍... 66
-
- 4.3 触类旁通... 66
-
- 4.3.1 523. 连续的子数组和... 66
-
- 4.3.2 974. 和可被 K 整除的子数组.... 71
-
- 5 九阴真经第五式 :差分... 71
-
- 5.1.1 代表题目:1094. 拼车.... 71
-
- 5.2 差分介绍... 72
-
- 5.3 触类旁通... 72
-
- 5.3.1 1109. 航班预订统计... 72
-
- 5.3.2 121. 买卖股票的最佳时机(简单) 73
-
- 5.3.3 122. 买卖股票的最佳时机 II 74
-
- 5.3.4 253. 会议室 II (会员)... 76
-
- 6 九阴真经第六式 :拓扑排序(专业级)... 77
-
- 6.1 代表题目:210. 课程表 II 77
-
- 6.2 拓扑排序介绍... 78
-
- 6.3 触类旁通... 79
-
- 6.3.1 课程表II(210)的一种解法... 79
-
- 6.3.2 444. 序列重建 (会员)... 86
-
- 6.3.3 269. 火星词典.... 87
-
- 7 九阴真经第七式 :字符串... 89
-
- 7.1 代表题目:5. 最长回文子串... 89
-
- 7.2 字符串介绍... 89
-
- 7.3 触类旁通... 89
-
- 7.3.1 93. 复原IP地址(dfs)... 90
-
- 7.3.2 43. 字符串相乘.... 90
-
- 7.3.3 227. 基本计算器 II 90
-
- 8 九阴真经第八式 :BFS. 92
-
- 8.1 代表题目:127. 单词接龙... 92
-
- 8.2 Bfs介绍... 92
-
- 8.3 触类旁通... 93
-
- 8.3.1 139. 单词拆分.... 93
-
- 8.3.2 130. 被围绕的区域.... 94
-
- 8.3.3 317. 离建筑物最近的距离(困难)... 94
-
- 8.3.4 505. 迷宫 II (会员)... 95
-
- 8.3.5 529. 扫雷游戏.... 96
-
- 8.3.6 1263. 推箱子(困难)... 96
-
- 8.3.7 1197. 进击的骑士.... 97
-
- 8.3.8 815. 公交路线(困难_必做)... 97
-
- 8.3.9 934. 最短的桥.... 98
-
- 9 九阴真经第九式 :DFS. 98
-
- 9.1 代表题目:934. 最短的桥... 98
-
- 9.2 Dfs介绍... 99
-
- 9.3 触类旁通... 99
-
- 9.3.1 1102. 得分最高的路径.... 99
-
- 9.3.2 685. 冗余连接 II(困难)... 100
-
- 9.3.3 531. 孤独像素 I 100
-
- 9.3.4 533. 孤独像素 II 101
-
- 9.3.5 332. 重新安排行程.... 101
-
- 9.3.6 337. 打家劫舍 III 102
-
- 9.3.7 113. 路径总和 II 102
-
- 10 九阴真经第十式 :动态规划... 103
-
- 10.1 代表题目:213. 打家劫舍 II 103
-
- 10.2 动态规划介绍... 103
-
- 10.3 触类旁通... 103
-
- 10.3.1 1043. 分隔数组以得到最大和... 103
-
- 10.3.2 416. 分割等和子集.... 104
-
- 10.3.3 123. 买卖股票的最佳时机 III 104
-
- 10.3.4 62. 不同路径.... 108
-
- 10.3.5 63. 不同路径 II 108
-
- 10.3.6 651. 4键键盘(会员)... 108
-
- 10.3.7 361. 轰炸敌人.... 109
-
- 10.3.8 1066. 校园自行车分配 II(会员)... 109
-
- 10.3.9 750. 角矩形的数量(会员)... 110
-
- 10.3.10 1230. 抛掷硬币.... 110
-
- 10.3.11 1055. 形成字符串的最短路径(会员)... 110
-
- 11 九阴真经第十一式 :贪心算法... 111
-
- 11.1.1 代表题目:452. 用最少数量的箭引爆气球... 111
-
- 11.2 贪心算法介绍... 111
-
- 11.3 触类旁通... 111
-
- 11.3.1 1231. 分享巧克力(会员)... 111
-
- 11.3.2 1247. 交换字符使得字符串相同... 112
-
- 11.3.3 45. 跳跃游戏 II 112
-
- 11.3.4 621. 任务调度器.... 113
-
- 11.3.5 376. 摆动序列.... 113
-
- 12 九阴真经第十二式 :字典树... 114
-
- 12.1 代表题目:820. 单词的压缩编码... 114
-
- 12.2 字典树介绍... 115
-
- 12.3 触类旁通... 115
-
- 12.3.1 1231. 分享巧克力(会员)... 115
-
- 12.3.2 648. 单词替换.... 116
-
- 12.3.3 208. 实现 Trie (前缀树). 116
-
- 13 真题实战... 116
-
-
-
-
-
-
- 1 九阴真经第一式 :单调栈
- 1.1 代表题目:最大矩形
-
-
- 1.2 单调栈介绍(https://zhuanlan.zhihu.com/p/26465701)
- 单调栈是一种理解起来很容易,但是运用起来并不那么简单的数据结构。一句话解释单调栈,就是一个栈,里面的元素的大小按照他们所在栈内的位置,满足一定的单调性。那么到底什么时候用这个单调栈,怎么用单调栈呢。下面我们来看几个例子。
-
- 先来分享一道非常简单的,我本人在google interview中遇到的题目。(大雾,当时并没有做出来。)
-
- 题目是这样的,给一个数组,返回一个大小相同的数组。返回的数组的第i个位置的值应当是,对于原数组中的第i个元素,至少往右走多少步,才能遇到一个比自己大的元素(如果之后没有比自己大的元素,或者已经是最后一个元素,则在返回数组的对应位置放上-1)。
-
- 简单的例子:
-
- input: 5, 3, 1, 2, 4
-
- return: -1 3 1 1 -1
-
- explaination: 对于第0个数字5,之后没有比它更大的数字,因此是-1,对于第1个数字3,需要走3步才能达到4(第一个比3大的元素),对于第2和第3个数字,都只需要走1步,就可以遇到比自己大的元素。对于最后一个数字4,因为之后没有更多的元素,所以是-1。
-
- 暴力做的结果就是O(n^2)的时间复杂度,例如对于一个单调递减的数组,每次都要走到数组的末尾。那么用单调栈怎么做呢?先来看代码:
-
- vector<int> nextExceed(vector<int> &input) {
-
- vector<int> result (input.size(), -1);
-
- stack<int> monoStack;
-
- for(int i = 0; i < input.size(); ++i) {
-
- while(!monoStack.empty() && input[monoStack.top()] < input[i]) {
-
- result[monoStack.top()] = i - monoStack.top();
-
- monoStack.pop();
-
- }
-
- monoStack.push(i);
-
- }
-
- return result;
-
- }
-
- 我们维护这样一个单调递减的stack,stack内部存的是原数组的每个index。每当我们遇到一个比当前栈顶所对应的数(就是input[monoStack.top()])大的数的时候,我们就遇到了一个“大数“。这个”大数“比它之前多少个数大我们不知道,但是至少比当前栈顶所对应的数大。我们弹出栈内所有对应数比这个数小的栈内元素,并更新它们在返回数组中对应位置的值。因为这个栈本身的单调性,当我们栈顶元素所对应的数比这个元素大的时候,我们可以保证,栈内所有元素都比这个元素大。对于每一个元素,当它出栈的时候,说明它遇到了自己的next greater element,我们也就要更新return数组中的对应位置的值。如果一个元素一直不曾出栈,那么说明不存在next greater element,我们也就不用更新return数组了。
-
- 这里作者在数组末尾加入了一个height 0,来强迫程序在结束前,将所有元素按照顺序弹出栈。是一个很巧妙的想法。在这个例子中,对于每一个元素都只有一次入栈和出栈的操作,因此时间复杂度只有O(n)。
-
-
- 解决了这个开胃菜,我们来看一道稍微复杂一点的题目。Leetcode 84. Largest Rectangle in Histogram
-
- Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
-
- Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
-
- The largest rectangle is shown in the shaded area, which has area = 10 unit.
-
- For example,
- Given heights = [2,1,5,6,2,3],
- return 10.
-
- 来看看discuss中sipiprotoss5的解法。
-
- int largestRectangleArea(vector<int> &height) {
-
- int ret = 0;
-
- height.push_back(0);
-
- vector<int> index;
-
- for(int i = 0; i < height.size(); i++) {
-
- while(index.size() > 0 && height[index.back()] >= height[i]) {
-
- int h = height[index.back()];
-
- index.pop_back();
-
- int sidx = index.size() > 0 ? index.back() : -1;
-
- ret = max(ret, h * (i-sidx-1));
-
- }
-
- index.push_back(i);
-
- }
-
- return ret;
-
- }
-
- 看上去这个解法长得和刚才那道题的差不多。实际算法也很相近,作者维护了一个单调递增的栈,然后进行了一系列xjb操作。那么到底为什么可以这么做?我们需要分析一下,每一个元素都要入栈一次,出栈一次。入栈的时候是for loop的iteration走到它的时候,那出栈的时候意味着什么呢。想清楚了这一点,我们也就理解了上面的答案。在上一题,每个元素出栈,是说明它找到了它在原数组中的next greater element.那这道题呢?元素出栈,意味着,我们已经计算了以它的顶为上边框的最大矩形。首先我们可以通过反证法轻松证明,最后的结果中的最大矩形的上边框,一定和某一个bar的顶重合,否则我们一定可以通过提高上边框来增加这个矩形的面积。这一步之后,我们还需要理解,这时候我们计算的矩形的左右边框都已经到达了极限。结合栈内元素的单调性,我们知道左边的边框是栈顶的元素+1,栈顶元素所对应的bar一定比出栈元素对应的bar小,所以以出栈元素对应的bar为高的矩形无法往左边延展。结合代码,我们知道右边的边框是正在处理的i,因为我们已经判断过这个第i个元素所对应的bar也一定比出栈元素对应的bar小,所以矩形无法往右边延展。这个元素和左右边框之间如果还有空隙,那么这些空隙里所存在的bar,一定是因为维护栈的单调性而被弹出了。换言之,这些bar如果存在,那么一定比这个出栈元素所对应的bar高。既然这些bar的高度更高,那么就可以被纳入这个最大矩形的计算中(例如一个“凹”字)。因此我们证明了,当我们将第i个元素弹出栈的时候,我们计算了以hight[i]为高的最大矩形的面积。
-
- 下面我们来看另一个可以借助单调栈的题目,Leetcode 85. Maximal Rectangle.
-
-
-
-
- Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
-
- For example, given the following matrix:
-
- 1 0 1 0 0
-
- 1 0 1 1 1
-
- 1 1 1 1 1
-
- 1 0 0 1 0
-
- Return 6.
-
- 这道题可以轻松地转化成上一题。对于每一行,我们都可以构建一个histogram,然后计算。在构建新的histogram的时候,我们不需要全部遍历,只需要对已有的histogram进行略微的修改(运用DP的思想)。为了在视觉上更加清晰,我直接调用了上一题中的函数。思路还是异常简单的。
-
- int maximalRectangle(vector<vector<char>>& matrix) {
-
- if (matrix.empty()) return 0;
-
- vector<int> height(matrix[0].size(), 0);
-
- int maxRect= 0;
-
- for(int i = 0; i < matrix.size(); ++i) {
-
- for(int j = 0; j < height.size(); ++j) {
-
- if(matrix[i][j] == '0') height[j] = 0;
-
- else ++height[j];
-
- }
-
- maxRect = max(maxRect, largestRectangleArea(height));
-
- height.pop_back();
-
- }
-
- return maxRect;
-
- }
-
- int largestRectangleArea(vector<int> &height) {
-
- int ret = 0;
-
- height.push_back(0);
-
- vector<int> index;
-
- for(int i = 0; i < height.size(); i++) {
-
- while(index.size() > 0 && height[index.back()] >= height[i]) {
-
- int h = height[index.back()];
-
- index.pop_back();
-
- int sidx = index.size() > 0 ? index.back() : -1;
-
- ret = max(ret, h * (i-sidx-1));
-
- }
-
- index.push_back(i);
-
- }
-
- return ret;
-
- }
-
- 最后再总结一下单调栈。单调栈这种数据结构,通常应用在一维数组上。如果遇到的问题,和前后元素之间的大小关系有关系的话,(例如第一题中我们要找比某个元素大的元素,第二个题目中,前后的bar的高低影响了最终矩形的计算),我们可以试图用单调栈来解决。在思考如何使用单调栈的时候,可以回忆一下这两题的解题套路,然后想清楚,如果使用单调栈,每个元素出栈时候的意义。最后的时间复杂度,因为每个元素都出栈入栈各一次,所以是线性时间的复杂度。
-
-
-
- 1.2.1 单调栈的性质:
-
-
- 1.单调栈里的元素具有单调性;
-
- 2.元素加入栈前,会在栈顶端把破坏栈单调性的元素都删除;
-
- 3.使用单调栈可以找到元素向左遍历第一个比他小的元素,也可以找到元素向左遍历第一个比他大的元素。
-
-
-
- 对于第三条性质的解释(最常用的性质):
-
- 对于单调栈的第三条性质,你可能会产生疑问,为什么使用单调栈可以找到元素向左遍历第一个比他大的元素,
-
-
-
- 而不是最后一个比他大的元素呢?我们可以从单调栈中元素的单调性来解释这个问题,由于单调栈中的元素只能是单调递增或者是单调
-
-
-
- 递减的,所以我们可以分别讨论这两种情况(假设不存在两个相同的元素):
-
-
-
- 1.当单调栈中的元素是单调递增的时候,根据上面我们从数组的角度阐述单调栈的性质的叙述,可以得出:
-
-
-
- (1).当a > b 时,则将元素a插入栈顶,新的栈顶则为a
-
- (2).当a < b 时,则将从当前栈顶位置向前查找(边查找,栈顶元素边出栈),直到找到第一个比a小的数,停止查找,将元素a
-
- 插入栈顶(在当前找到的数之后,即此时元素a找到了自己的“位置”)
-
-
-
- 2.当单调栈中的元素是单调递减的时候,则有:
-
- (1).当a < b 时,则将元素a插入栈顶,新的栈顶则为a
-
- (2).当a > b 时,则将从当前栈顶位置向前查找(边查找,栈顶元素边出栈),直到找到第一个比a大的数,停止查找,将元素a
-
- 插入栈顶(在当前找到的数之后,即此时元素a找到了自己的“位置”)
-
- (原文链接:https://blog.csdn.net/liujian20150808/article/details/50752861)
-
-
-
- 1.3 触类旁通:
- 1.3.1 每日温度(739)
- 1.3.1.1 题目描述
-
-
- 1.3.1.2 参考代码:
- // 739. 每日温度
-
- #include <stdio.h>
-
- #include <stdlib.h>
-
- #include <string.h>
-
- #include <stdbool.h>
-
- #include <ctype.h>
-
- #include <math.h>
-
-
-
- #define MAX_DAILY_TEMPERATURES_NUM 30010
-
- int *g_destStack;
-
- int g_destLen;
-
- int g_tempStack[MAX_DAILY_TEMPERATURES_NUM];
-
- int g_tempLen;
-
-
-
- int GetMax(int a, int b)
-
- {
-
- if (a >= b) {
-
- return a;
-
- }
-
- return b;
-
- }
-
-
-
- bool MallocDailyTemperatures(int* t, int tSize)
-
- {
-
- int i;
-
- g_destLen = 0;
-
- if (tSize == 0) {
-
- return false;
-
- }
-
- g_destStack = (int *)malloc(tSize * sizeof(int));
-
- if (g_destStack == NULL) {
-
- return false;
-
- }
-
-
-
- for (i = 0; i < tSize; i++) {
-
- g_destStack[i] = 0;
-
- }
-
-
-
- return true;
-
- }
-
-
-
- /**
- * Note: The returned array must be malloced, assume caller calls free().
- */
-
- int *dailyTemperatures(int* t, int tSize, int* returnSize)
-
- {
-
- int i;
-
- int stackIndex;
-
- bool rslt;
-
- g_tempLen = 0;
-
-
-
- rslt = MallocDailyTemperatures(t, tSize);
-
- if (!rslt) {
-
- (*returnSize) = 0;
-
- return NULL;
-
- }
-
-
-
- g_tempStack[0] = 0;
-
- g_tempLen++;
-
-
-
-
-
-
-
-
-
- for (i = 1; i < tSize; i++) {
-
- while (g_tempLen > 0) {
-
- stackIndex = g_tempStack[g_tempLen - 1];
-
- // 不满足单调递减
-
- if (t[i] > t[stackIndex]) {
-
- g_destStack[stackIndex] = i - stackIndex;
-
- // 出栈
-
- g_tempLen--;
-
- continue;
-
- }
-
- break;
-
- }
-
- // 满足单调递减,入栈
-
- g_tempStack[g_tempLen++] = i;
-
- }
-
-
-
- (*returnSize) = tSize;
-
- return g_destStack;
-
- }
-
-
-
- 1.3.2 下一个更大元素II(503)
-
-
-
-
- 1.3.3 柱状图中最大矩形(84_困难)
-
-
-
-
-
-
- 1.3.4 接雨水(42_困难_性能敏感)
-
-
- 1.3.4.1 方法1,暴力解:
- 找出每根柱子左右的最高点,取两边最高柱子最小的高度,与中间柱子高度相减就是凹槽的高度。
-
- 复杂性分析
-
- 时间复杂度: O(n2)。数组中的每个元素都需要向左向右扫描。
- 空间复杂度 O(1)O(1) 的额外空间。
-
-
- 1.3.4.2 方法 2:栈的应用
- 我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到 ans 。算法使用栈来存储条形块的索引下标。
-
- 遍历数组:
-
- C++
-
- int trap(vector<int>& height)
-
- {
-
- int ans = 0, current = 0;
-
- stack<int> st;
-
- while (current < height.size()) {
-
- while (!st.empty() && height[current] > height[st.top()]) {
-
- int top = st.top();
-
- st.pop();
-
- if (st.empty())
-
- break;
-
- int distance = current - st.top() - 1;
-
- int bounded_height = min(height[current], height[st.top()]) - height[top];
-
- ans += distance * bounded_height;
-
- }
-
- st.push(current++);
-
- }
-
- return ans;
-
- }
-
- 1.3.5 股票价格跨度(901)
-
-
-
-
-
-
- 1.3.6 滑动窗口最大值(239_困难_O(n)时间复杂度解决)
-
-
-
-
-
-
- 2 九阴真经第二式 :并查集
- 2.1 代表题目:朋友圈
-
-
- 2.2 并查集介绍
- (https://blog.csdn.net/qq_41593380/article/details/81146850)江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的帮派,通过两两之间的朋友关系串联起来。而不在同一个帮派的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?
-
- 我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物。这样,每个圈子就可以这样命名“中国同胞队”美国同胞队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。
- 但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长 要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样,想打一架得先问个几十年,饿都饿死了,受不了。这样一来,队长面子上也挂不住了,不仅效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否是一个帮派的,至于他们是如何通过朋友关系相关联的,以及每个圈子内部的结构是怎样的,甚至队长是谁,都不重要了。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。
-
-
-
- 下面我们来看并查集的实现。 int pre[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。
-
- find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。
-
-
- int unionsearch(int root) //查找根结点
- {
- int son, tmp;
- son = root;
- while(root != pre[root]) //我的上级不是掌门
- root = pre[root];
- while(son != root) [W1] //我就找他的上级,直到掌门出现
- {
- tmp = pre[son];
- 10. pre[son] = root;
- 11. son = tmp;
- 12. }
- 13. return root; //掌门驾到~~
- 14.
- 再来看看join函数,就是在两个点之间连一条线,这样一来,原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办,画条线就行了。但我们现在是用并查集来描述武林中的状况的,一共只有一个pre[]数组,该如何实现呢? 还是举江湖的例子,假设现在武林中的形势如图所示。虚竹帅锅与周芷若MM是我非常喜欢的两个人物,他们的终极boss分别是玄慈方丈和灭绝师太,那明显就是两个阵营了。我不希望他们互相打架,就对他俩说:“你们两位拉拉勾,做好朋友吧。”他们看在我的面子上,同意了。这一同意可非同小可,整个少林和峨眉派的人就不能打架了。这么重大的变化,可如何实现呀,要改动多少地方?其实非常简单,我对玄慈方丈说:“大师,麻烦你把你的上级改为灭绝师太吧。这样一来,两派原先的所有人员的终极boss都是师太,那还打个球啊! 反正我们关心的只是连通性,门派内部的结构不要紧的。”玄慈一听肯定火大了:“我靠,凭什么是我变成她手下呀,怎么不反过来?我抗议!”于是,两人相约一战,杀的是天昏地暗,风云为之变色啊,但是啊,这场战争终究会有胜负,胜者为王。弱者就被吞并了。反正谁加入谁效果是一样的,门派就由两个变成一个了。这段函数的意思明白了吧?
-
- void join(int root1, int root2) //虚竹和周芷若做朋友
- {
- int x, y;
- x = unionsearch(root1);//我老大是玄慈
- y = unionsearch(root2);//我老大是灭绝
- if(x != y)
- pre[x] = y; //打一仗,谁赢就当对方老大
- }
- 再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么样,我也无法预知,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。
-
- 设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能干一场。 于是赶紧打电话问自己的上级:“你是不是掌门?” 上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。” 一路问下去,原来两人的最终boss都是东厂曹公公。 “哎呀呀,原来是自己人,有礼有礼,在下三营六组白面葫芦娃!” “幸会幸会,在下九营十八组仙子狗尾巴花!” 两人高高兴兴地手拉手喝酒去了。 “等等等等,两位大侠请留步,还有事情没完成呢!”我叫住他俩。 “哦,对了,还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其实偶们的掌门是曹公公。不如偶们一起结拜在曹公公手下吧,省得级别太低,以后查找掌门麻烦。” “唔,有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码,看得懂很好,看不懂可以自己模拟一下,很简单的一个递归而已。总之它所实现的功能就是这么个意思。
-
-
-
-
-
- 2.3 触类旁通
- 2.3.1 朋友圈的参考解法(547)
- /*
- * Copyright (c) Huawei Technologies Co., Ltd. 2019-2019. All rights reserved.
- * Description: 547. 朋友圈
- * Author: w00448446
- * Create: 2019-11-27
- */
-
- #include <stdio.h>
-
- #include <stdlib.h>
-
- #include <stdbool.h>
-
- #include <string.h>
-
- #include <ctype.h>
-
- #include <math.h>
-
-
-
- int *g_dest;
-
-
-
- bool Init(int mSize)
-
- {
-
- int i;
-
- if (mSize < 1) {
-
- return false;
-
- }
-
- g_dest = (int *)malloc(mSize * sizeof(int));
-
- if (g_dest == NULL) {
-
- return false;
-
- }
-
-
-
- for (i = 0; i < mSize; i++) {
-
- g_dest[i] = i;
-
- }
-
-
-
- return true;
-
- }
-
-
-
- int Find(int index)
-
- {
-
- if (g_dest[index] == index) {
-
- return index;
-
- }
-
- return g_dest[index] = Find(g_dest[index]);
-
- }
-
-
-
- int FindRoot(int i)
-
- {
-
- while (g_dest[i] != i) {
-
- i = g_dest[i];
-
- }
-
-
-
- return i;
-
- }
-
- void ProcCircle(int **m, int mSize)
-
- {
-
- int i, j;
-
- int rootI, rootJ;
-
- for (i = 0; i < mSize; i++) {
-
- for (j = (i + 1); j < mSize; j++) {
-
- if (m[i][j] != 1) {
-
- continue;
-
- }
-
- rootI = FindRoot(i);
-
- rootJ = FindRoot(j);
-
- if (rootI == rootJ) {
-
- continue;
-
- }
-
- g_dest[rootI] = rootJ;
-
- }
-
- }
-
-
-
- return;
-
- }
-
- int GetCircleNum(int mSize)
-
- {
-
- int i;
-
- int sum = 0;
-
- for (i = 0; i < mSize; i++) {
-
- if (g_dest[i] == i) {
-
- sum++;
-
- }
-
- }
-
- return sum;
-
- }
-
- void FreeCircle()
-
- {
-
- if (g_dest != NULL) {
-
- free(g_dest);
-
- g_dest = 0;
-
- }
-
- }
-
- int findCircleNum(int **m, int mSize, int* mColSize)
-
- {
-
- bool rslt;
-
- int sum;
-
-
-
- rslt = Init(mSize);
-
- if (!rslt) {
-
- return 0;
-
- }
-
-
-
- ProcCircle(m, mSize);
-
- sum = GetCircleNum(mSize);
-
-
-
- FreeCircle();
-
- return sum;
-
- }
-
-
-
- 2.3.2 冗余连接(684)
-
-
-
-
- 2.3.3 岛屿数量(200_必做)
-
-
- /*
- * Copyright (c) Huawei Technologies Co., Ltd. 2012-2019. All rights reserved.
- * Description: 200. 岛屿数量
- * Author: w00448446
- * Create: 2019-10-27
- */
-
- #include <stdio.h>
-
- #include <string.h>
-
- #include <stdlib.h>
-
- #include <stdbool.h>
-
- #include <ctype.h>
-
- #include "securec.h"
-
- #define POINT_MAX_VALUE 10000
-
- #define POINT_MIN_VALUE (-10000)
-
- #define POINT_MAX_NUM 2
-
- int g_direction[][POINT_MAX_NUM] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
-
- int g_len = (int)sizeof(g_direction) / sizeof(g_direction[0]);
-
- int GetMax(int a, int b)
-
- {
-
- if (a >= b) {
-
- return a;
-
- }
-
- return b;
-
- }
-
- void Dfs(char **grid, int gridSize, int *gridColSize, int x, int y)
-
- {
-
- int i;
-
- int nextX, nextY;
-
- grid[x][y] = '2';
-
-
-
- for (i = 0; i < g_len; i++) {
-
- nextX = (int) (x + g_direction[i][0]);
-
- nextY = (int) (y + g_direction[i][1]);
-
- if ((nextX >= 0) && (nextX < gridSize) && (nextY >= 0) && (nextY < gridColSize[0])) {
-
- if (grid[nextX][nextY] == '2') {
-
- continue;
-
- }
-
-
-
- if (grid[nextX][nextY] == '0') {
-
- continue;
-
- }
-
-
-
- Dfs(grid, gridSize, gridColSize, nextX, nextY);
-
- }
-
- }
-
- }
-
- int numIslands(char **grid, int gridSize, int *gridColSize)
-
- {
-
- int i, j;
-
- int sum = 0;
-
-
-
- for (i = 0; i < gridSize; i++) {
-
- for (j = 0; j < gridColSize[0]; j++) {
-
- if (grid[i][j] == '0') {
-
- continue;
-
- }
-
-
-
- if (grid[i][j] == '2') {
-
- continue;
-
- }
-
-
-
- if (grid[i][j] == '1') {
-
- sum++;
-
- Dfs(grid, gridSize, gridColSize, i, j);
-
- }
-
- }
-
- }
-
- return sum;
-
- }
-
-
-
- void TestCase1()
-
- {
-
- int rslt;
-
- char array1[] = "11110";
-
- char array2[] = "11010";
-
- char array3[] = "11000";
-
- char array4[] = "00000";
-
- char *grid[] = { array1, array2, array3, array4 };
-
- int gridSize = sizeof(grid) / sizeof(char *);
-
- int gridColSize[] = { 5, 5, 5, 5 };
-
- rslt = numIslands(grid, gridSize, gridColSize);
-
- if (rslt == 1) {
-
- printf("T1:succ");
-
- }
-
- }
-
-
-
- void TestCase2()
-
- {
-
- int rslt;
-
- char array1[] = "11000";
-
- char array2[] = "11000";
-
- char array3[] = "00100";
-
- char array4[] = "00011";
-
- char *grid[] = { array1, array2, array3, array4 };
-
- int gridSize = sizeof(grid) / sizeof(char *);
-
- int gridColSize[] = { 5, 5, 5, 5 };
-
- rslt = numIslands(grid, gridSize, gridColSize);
-
- if (rslt == 3) {
-
- printf("T2:succ");
-
- }
-
- }
-
-
-
- int main()
-
- {
-
- TestCase2();
-
- int i;
-
- if (scanf_s("%d", &i) != 0) {
-
- }
-
- return 0;
-
- }
-
-
-
-
-
- 2.3.4 句子相似性II (737_会员)
-
-
-
-
- /*
- * Copyright (c) Huawei Technologies Co., Ltd. 2012-2018. All rights reserved.
- * Description: 737. 句子相似性 II
- * Author: w00448446
- * Create: 2019-11-27
- */
-
- #include <stdio.h>
-
- #include <stdlib.h>
-
- #include <stdbool.h>
-
- #include <string.h>
-
- #include <ctype.h>
-
- #include <math.h>
-
-
-
- #define MAX_WORDS_NUM 4010
-
-
-
- typedef struct {
-
- int pre;
-
- char *words;
-
- } Word;
-
-
-
- Word g_pair[MAX_WORDS_NUM];
-
- int g_pairLen;
-
-
-
- int PairCmp[W2] (const void *w1, const void *w2)
-
- {
-
- return strcmp(((Word*)w1)->words, ((Word*)w2)->words);
-
- }
-
-
-
- int GetRoot[W3] (int i)
-
- {
-
- while (g_pair[i].pre != i) {
-
- i = g_pair[i].pre;
-
- }
-
- return i;
-
- }
-
- void Init(char ***pairs, int pairsSize)
-
- {
-
- int i, j;
-
- int pre1, pre2;
-
- Word pair1, pair2;
-
- Word *word1 = NULL;
-
- Word *word2 = NULL;
-
-
-
- g_pairLen = 0;
-
- if (pairsSize < 1) {
-
- return;
-
- }
-
-
-
- for (i = 0; i < pairsSize; i++) {
-
- g_pair[g_pairLen++].words = pairs[i][0];
-
- g_pair[g_pairLen++].words = pairs[i][1];
-
- }
-
-
-
- // 排序
-
- qsort(g_pair, g_pairLen, sizeof(Word), PairCmp);
-
-
-
- // 去除重复[W4]
-
- for (i = 1, j = 0; i < g_pairLen; i++) {
-
- if (strcmp(g_pair[i].words, g_pair[j].words) == 0) {
-
- continue;
-
- }
-
- j++;
-
- g_pair[j].words = g_pair[i].words;
-
- }
-
- g_pairLen = j + 1;
-
-
-
- // 初始化pre值
-
- for (i = 0; i < g_pairLen; i++) {
-
- g_pair[i].pre = i;
-
- }
-
-
-
- // 根据pair,生成映射
-
- for (i = 0; i < pairsSize; i++) {
-
- pair1.words = pairs[i][0];
-
- pair2.words = pairs[i][1];
-
- word1 = bsearch(&pair1, g_pair, g_pairLen, sizeof(Word), PairCmp);
-
- word2 = bsearch(&pair2, g_pair, g_pairLen, sizeof(Word), PairCmp);[W5]
-
- if ((word1 == NULL) || (word2 == NULL)) {
-
- printf("search fail, not expect!\n");
-
- continue;
-
- }
-
-
-
- pre1 = GetRoot(word1->pre);
-
- pre2 = GetRoot(word2->pre);
-
- if (pre1 == pre2) {
-
- continue;
-
- }
-
- g_pair[pre1].pre = pre2;[W6]
-
- }
-
- return ;
-
- }
-
-
-
- bool IsSimilar(char **words1, int words1Size, char **words2, int words2Size)
-
- {
-
- int i;
-
- int pre1, pre2;
-
- Word pair1, pair2;
-
- Word *word1 = NULL;
-
- Word *word2 = NULL;
-
- if (words1Size != words2Size) {
-
- return false;
-
- }
-
-
-
- for (i = 0; i < words1Size; i++) {
-
- // 查找
-
- pair1.words = words1[i];
-
- pair2.words = words2[i];
-
- word1 = bsearch(&pair1, g_pair, g_pairLen, sizeof(Word), PairCmp);
-
- word2 = bsearch(&pair2, g_pair, g_pairLen, sizeof(Word), PairCmp);
-
- if ((word1 == NULL) || (word2 == NULL)) {
-
- if (strcmp(words1[i], words2[i]) == 0) {
-
- continue;
-
- }
-
- return false;
-
- }
-
-
-
- pre1 = GetRoot(word1->pre);
-
- pre2 = GetRoot(word2->pre);
-
- if (pre1 == pre2) {
-
- continue;
-
- }
-
-
-
- return false;
-
- }
-
-
-
- return true;
-
- }
-
- bool areSentencesSimilarTwo(char **words1, int words1Size, char **words2, int words2Size,
-
- char ***pairs, int pairsSize, int *pairsColSize)
-
- {
-
- Init(pairs, pairsSize);
-
- bool rslt = IsSimilar(words1, words1Size, words2, words2Size);
-
- return rslt;
-
- }
-
-
-
- void Test1()
-
- {
-
- char *word1[] = { "great", "acting", "skills" };
-
- char *word2[] = { "fine", "drama", "talent" };
-
- char *pair1[] = { "great", "fine" };
-
- char *pair2[] = { "acting", "drama" };
-
- char *pair3[] = { "skills", "talent" };
-
- char **g[] = { pair1, pair2, pair3 };
-
-
-
- int word1Size = sizeof(word1) / sizeof(word1[0]);
-
- int word2Size = sizeof(word2) / sizeof(word2[0]);
-
- int pairsSize = sizeof(g) / sizeof(g[0]);
-
- int pairsColSize[] = { 2 };
-
- int rslt;
-
- rslt = areSentencesSimilarTwo(word1, word1Size, word2, word2Size, g, pairsSize, pairsColSize);
-
- if (rslt == 1) {
-
- printf("t1: succ\n");
-
- }
-
- }
-
- void main()
-
- {
-
- Test1();
-
- return;
-
- }
-
- 2.3.5 得分最高的路径(1102_会员)
-
-
- 使用并查集的一种解法:
-
-
-
- /*
- * Copyright (c) Huawei Technologies Co., Ltd. 2019-2019. All rights reserved.
- * Description: 1102. 得分最高的路径
- * Author: w00448446
- * Create: 2019-12-13
- */
-
- #include <stdio.h>
-
- #include <stdlib.h>
-
- #include <stdbool.h>
-
-
-
- #define MAX_NUM 10006
-
- #define DIRECTION_NODE_NUM 2
-
- #define DIRECTION_LEN 4
-
-
-
- typedef struct {
-
- int currIndex;
-
- int preIndex;
-
- int marked;
-
- int val;
-
- } Node;
-
-
-
- int g_direction[][DIRECTION_NODE_NUM] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
-
-
-
- int g_col;
-
- int g_row;
-
- Node g_node[MAX_NUM];
-
- Node g_sortNode[MAX_NUM];
-
- int g_num;
-
-
-
- int NodeCmp(const void *node1, const void *node2)
-
- {
-
- return (((Node *)node2)->val) - (((Node *)node1)->val);
-
- }
-
- void InitNode(const int **a, int aSize, const int *aColSize)
-
- {
-
- int i, j;
-
- g_col = aColSize[0];
-
- g_row = aSize;
-
- g_num = 0;
-
- for (i = 0; i < aSize; i++) {
-
- for (j = 0; j < g_col; j++) {
-
- g_node[g_num].val = a[i][j];
-
- g_node[g_num].currIndex = i * g_col + j;
-
- g_node[g_num].preIndex = g_node[g_num].currIndex;
-
- g_node[g_num].marked = 0;
-
- g_sortNode[g_num] = g_node[g_num];
-
- g_num++;
-
- }
-
- }
-
- // 从大到小排序
-
- qsort(g_sortNode, g_num, sizeof(Node), NodeCmp);
-
- }
-
-
-
- bool IsNodeValid(int i, int j)
-
- {
-
- if (i < 0) {
-
- return false;
-
- }
-
-
-
- if (i >= g_row) {
-
- return false;
-
- }
-
-
-
- if (j < 0) {
-
- return false;
-
- }
-
-
-
- if (j >= g_col) {
-
- return false;
-
- }
-
-
-
- return true;
-
- }
-
-
-
- int FindRoot(int index)
-
- {
-
- if (index == g_node[index].preIndex) {
-
- return index;
-
- }
-
- return g_node[index].preIndex = FindRoot(g_node[index].preIndex);
-
- }
-
-
-
- void UnionNode(int index)
-
- {
-
- int i;
-
- int currI, currJ, currRoot;
-
- int nextI, nextJ, nextMap, nextRoot;
-
-
-
- currI = g_node[index].currIndex / g_col;
-
- currJ = g_node[index].currIndex % g_col;
-
- for (i = 0; i < DIRECTION_LEN; i++) {
-
- nextI = currI + g_direction[i][0];
-
- nextJ = currJ + g_direction[i][1];
-
-
-
- if (!IsNodeValid(nextI, nextJ)) {
-
- continue;
-
- }
-
- // 如果有效点, 找到父亲节点进行并操作
-
- nextMap = nextI * g_col + nextJ;
-
- if (g_node[nextMap].marked == 0) {
-
- continue;
-
- }
-
-
-
- nextRoot = FindRoot(nextMap);
-
- currRoot = FindRoot(index);
-
- if (nextRoot == currRoot) {
-
- continue;
-
- }
-
-
-
- if (nextRoot <= currRoot) {
-
- g_node[currRoot].preIndex = nextRoot;
-
- continue;
-
- }
-
-
-
- // 进行并操作
-
- g_node[nextRoot].preIndex = currRoot;
-
- }
-
- }
-
-
-
- int Traverse()
-
- {
-
- int i, index;
-
- int startValid = 0;
-
- const int START_INDEX = 0;
-
- int startRoot;
-
- int endValid = 0;
-
- int endIndex = g_num - 1;
-
- int endRoot;
-
-
-
- for (i = 0; i < g_num; i++) {
-
- // 查找上下左右,进行归并
-
- index = g_sortNode[i].currIndex;
-
- g_node[index].marked = 1;
-
- UnionNode(index);
-
-
-
- if (index == START_INDEX) {
-
- startValid = 1;
-
- }
-
-
-
- if (index == endIndex) {
-
- endValid = 1;
-
- }
-
-
-
- if ((startValid == 0) || (endValid == 0)) {
-
- continue;
-
- }
-
-
-
- // 检测起始和结束点是否在一个圈子里面,若是则找到目标解
-
- startRoot = FindRoot(START_INDEX);
-
- endRoot = FindRoot(endIndex);
-
- if (endRoot == startRoot) {
-
- return g_sortNode[i].val;
-
- }
-
- }
-
- return g_sortNode[0].val;
-
- }
-
- int maximumMinimumPath(const int **a, int aSize, const int *aColSize)
-
- {
-
- InitNode(a, aSize, aColSize);
-
- int max = Traverse();
-
- return max;
-
- }
-
-
-
- void Test1()
-
- {
-
- int m1[] = { 5, 4, 5 };
-
- int m2[] = { 1, 2, 6 };
-
- int m3[] = { 7, 4, 6 };
-
- int *g[] = { m1, m2, m3 };
-
- int len = sizeof(g) / sizeof(g[0]);
-
- int col[] = { 3, 3, 3 };
-
- int rslt = maximumMinimumPath(g, len, col);
-
- if (rslt == 4) {
-
- printf("T1: pass\n");
-
- } else {
-
- printf("T1: fail\n");
-
- }
-
- }
-
-
-
- void Test2()
-
- {
-
- int m1[] = { 2, 2, 1, 2, 2, 2 };
-
- int m2[] = { 1, 2, 2, 2, 1, 2 };
-
- int *g[] = { m1, m2 };
-
- int len = sizeof(g) / sizeof(g[0]);
-
- int col[] = { 6, 6, 6 };
-
- int rslt = maximumMinimumPath(g, len, col);
-
- if (rslt == 2) {
-
- printf("T2: pass\n");
-
- } else {
-
- printf("T2: fail\n");
-
- }
-
- }
-
- void main(void)
-
- {
-
- Test2();
-
- Test1();
-
- return;
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。