KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

算法思路：

DFS用于需要知道具体路径的问题，而并查集方法用于不需知道具体路径只关心连通性的问题。
此算法把同一个连通集归结为同一个根节点，作为判断是否一个连通集的标识。它用深度为2的扁平树组织起来。这是查找操作。
另一个关键操作是联合两个不同连通集，就是直接把根节点直接作为另一课树的子节点。在这个过程中，新的树深度可能会大于2，但当要union路径大于2的节点是，会对其进行路径压缩。
最巧妙的操作当属find操作，将路径进行压缩，变成长度为1的路径，见步骤4。
可能有人会考虑用HashMap而不是树，HashMap查找也是很高效，但联合操作比较费时，因为要更新另一个树的所有节点的根节点。

算法步骤：

  1. 初始化UnionFind类，包括3个属性：count（独立连通数）, parent（某节点的父节点）, rank（连通集排名，只有每个连通集根节点的rank不为0，其他点均为0。这是一个描述连通集规模的变量，如果规模越大，
    rank值可能越大。合并时候，rank较小的话，规模也较小，这样用rank小的合并到rank大的，需要压缩路径的节点较少，复杂度更低）。合格的节点的parent初始化为自己的id，rank为0，count为所有合格节点数量。
  2. 遍历所有节点，union此节点及其相邻的节点（如上下左右）
  3. union时候，先find两节点的根节点，若相同忽略。若不同，合并此两连通集：rank大的连通集，作为rank小的连通集的父节点。若rank相等，选任一作为另一个的父节点且把它的rank加1。count减1。
    如下图，union 5和1的，find(6)会进行压缩路径，把6接到5下。
  4. find寻找根节点的同时，压缩成与根节点路径为1的连通。

例子矩阵：
{‘0’,’1’,’1’,’0’,’0’}
{‘1’,’1’,’1’,’0’,’0’}

应用条件：

动态计算连通数如305. Number of Islands II

注意事项：

  1. find中是if语句不是while语句，因为递归已经达到
  2. union中，是祖先节点相连，不是输入相连
  3. union的调用在类外面调用，不是在init里做

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class UnionFind:

    def __init__(self, li):
        self.parent = collections.defaultdict(str)
        for s in li:
			self.parent[s] = s

    def find(self, s):
        if self.parent[s] != s:  # if statement
            self.parent[s] = self.find(self.parent[s])
        return self.parent[s]

    def union(self, s1, s2):
        root, root2 = self.find(s1), self.find(s2)
        if root != root2:
            self.parent[root] = root2 # remember not self.parent[s] = s2

注意事项：

find要注意压缩路径parent[i] = find(parent[i])

初始化：

1
2
3
4
5
6
7
8
9
10
class UnionFind {
	int[] parent;
	
	public Initialization(int n) {
        // initialize your data structure here.
        parent = new int[n + 1];
        for (int i = 1; i <= n; ++i)
            father[i] = i;
    }
}

查找：

1
2
3
4
5
6
public int find(int i) {
	if (parent[i] != i) {
		parent[i] = find(parent[i]); // path compression
	}
	return parent[i];
}

合并：

1
2
3
4
5
6
public void union(int a, int b) {
	int root_a = find(a);
	int root_b = find(b);
	if (root_a != root_b)
		parent[root_a] = root_b;
}

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class UnionFind {
	int count; // # of connected components
	int[] parent;
	int[] rank;

	public UnionFind(char[][] grid) { // for problem 200
		count = 0;
		int m = grid.length;
		int n = grid[0].length;
		parent = new int[m * n];
		rank = new int[m * n];
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (grid[i][j] == '1') {
					parent[i * n + j] = i * n + j;
					++count;
				}
				rank[i * n + j] = 0;
			}
		}
	}

	public int find(int i) {
		if (parent[i] != i) {
			parent[i] = find(parent[i]); // path compression
		}
		return parent[i];
	}

	// union point x and y with rank
	public void union(int x, int y) {
		int rootx = find(x);
		int rooty = find(y);
		if (rootx != rooty) {
			if (rank[rootx] > rank[rooty]) {
				parent[rooty] = rootx;
			} else if (rank[rootx] < rank[rooty]) {
				parent[rootx] = rooty;
			} else {
				parent[rooty] = rootx;
				rank[rootx] += 1;
			}
			--count;
		}
	}

	public int getCount() {
		return count;
	}
}

public int numIslands3(char[][] grid) {
	if (grid == null || grid.length == 0) {
		return 0;
	}

	int nr = grid.length;
	int nc = grid[0].length;
	int num_islands = 0;
	UnionFind uf = new UnionFind(grid);
	for (int r = 0; r < nr; ++r) {
		for (int c = 0; c < nc; ++c) {
			if (grid[r][c] == '1') {
				grid[r][c] = '0';
				if (r - 1 >= 0 && grid[r - 1][c] == '1') {
					uf.union(r * nc + c, (r - 1) * nc + c);
				}
				if (r + 1 < nr && grid[r + 1][c] == '1') {
					uf.union(r * nc + c, (r + 1) * nc + c);
				}
				if (c - 1 >= 0 && grid[r][c - 1] == '1') {
					uf.union(r * nc + c, r * nc + c - 1);
				}
				if (c + 1 < nc && grid[r][c + 1] == '1') {
					uf.union(r * nc + c, r * nc + c + 1);
				}
			}
		}
	}

	return uf.getCount();
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。遍历每个节点，而每个节点只会遍历4个相邻节点。

Ref：

并查集(Union-Find)算法介绍

Posted on Edited on Disqus:

算法思路：

left is left pointer, i is right pointer

求最短串

Python代码：

1
2
3
4
5
6
7
8
def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <meets condition>:
			res = min(res, i - left + 1)
			<anti-calculate condition such as char_to_count>
			left += 1
	return <result>

求最长串

Python代码：

1
2
3
4
5
6
7
8
def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <does not meet condition>:
			<anti-calculate condition such as char_to_count>
			left += 1
		res = max(res, i - left + 1)
	return <result>

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

Posted on Edited on Disqus:

算法思路：

Leetcode 208 Implement Trie (Prefix Tree), 也可以用HashMap将所有前缀加入到Map来实现，效率稍低。

注意事项：

  1. TrieNode用{}和is_end，insert, search, startswith用it和i迭代比较
  2. startswith含整个单词，如单词apple，startswith(‘apple’) -> True
  3. Line 11记得加，也就是dict在取value是一定要先检验key是否存在。可以不加，解决方案是用defaultdict（后版本）。

新版本比旧版本更简洁，体现在is_end的处理放在了for循环外。
存储结构举例： a

1
2
3
4
5
6
TrieNode(
  children = { 
              'a':  TrieNode(is_End = True)
		     }
  is_end = False
)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    def __init__(self):
        self.head = TrieNode()

    def insert(self, word: str) -> None:
        it = self.head
        for i in range(len(word)):
            # if word[i] not in it.children:
                #it.children[word[i]] = TrieNode()
            it = it.children[word[i]]
        it.is_end = True

    def search(self, word: str) -> bool:
        it = self.head
        for i in range(len(word)):
            if word[i] not in it.children:
                return False
            it = it.children[word[i]]
        return it.is_end

    def startsWith(self, prefix: str) -> bool:
        it = self.head
        for i in range(len(prefix)):
            if prefix[i] not in it.children:
                return False
            it = it.children[prefix[i]]
        return True

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.is_end = False

旧版本： 冗余了一个if语句if i == len(word) - 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Trie(TestCases):

        def __init__(self):
        self.head = TrieNode()

    def insert(self, word: str) -> None:
        if not word:
            return
        it = self.head
        for i in range(len(word)):
            # if word[i] not in it.children:
                # it.children[word[i]] = TrieNode()
            it = it.children[word[i]]
            if i == len(word) - 1:
                it.is_end = True

    def search(self, word: str) -> bool:
        if not word:
            return False
        it = self.head
        for i in range(len(word)):
            if word[i] not in it.children:
                return False
            it = it.children[word[i]]
            if i == len(word) - 1 and it.is_end:
                return True
        return False

    def startsWith(self, prefix: str) -> bool:
        if not prefix:
            return False
        it = self.head
        for i in range(len(prefix)):
            if prefix[i] not in it.children:
                return False
            it = it.children[prefix[i]]
            if i == len(prefix) - 1:
                return True
        return False

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.is_end = False

算法分析：

每个操作时间复杂度为O(n)，空间复杂度O(n)，n为单词长度。

Posted on Edited on Disqus:

算法思路：

对于拓扑排序来说， 我们的中心思想是要我们可以找到一个顺序，每一次我们可以进行的工序是现在没有先序依赖的工序，
按照这个顺序可以流畅的完成我们的任务。
思路基于BFS的队列实现。区别在于统计每个节点的入度数。此法也可用于无向图。

  1. 根据边统计每个节点的入度数记入in[i]，其他节点（含无边节点）入度数为0
  2. 找出度数为0的节点加入到Queue
  3. 取出队首节点，把此节点邻接的节点度数减1，如果度数为0，加入到队列，循环直到队列为空
  4. 如果队列为空但仍有节点度数不为0，存在循环，否则不存在

应用：

  1. 求最长或最短路径(Leetcode 310)
  2. 判断拓扑顺序(Leetcode外星人字典)
  3. 判断循环(Python代码返回None)

注意事项：

  1. graph要含所有节点，包括没有边的节点。否则结果会有遗漏
  2. in_degree初始化要对所有节点赋0
  3. 第四步判断是否含循环必不可少，要根据题目要求来处理。除非L310 min height明确一定有解，而L269外星人字典就明确可能无解

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def topological_sort(self, graph: List[List[int]], n: int) -> List[int]:
	in_degree = [0] * n
	for i in range(len(graph)):
		for j in range(len(graph[i])):
			in_degree[graph[i][j]] += 1

	start_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0]
	queue, res = deque(start_nodes), []

	while queue:
		root = queue.popleft()
		res.append(root)
		for i in graph[root]:
			in_degree[i] -= 1
			if in_degree[i] == 0:
				queue.append(i)
	return res if len(res) == n else None

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
 * graph: 邻接表
 * num: 节点个数 
 */
public void topologicalSort(ArrayList<ArrayList<Integer>> graph, int num) {
	int[] inDegree = new int[num];
	//populate inDegree
	for(ArrayList<Integer> adjacencyList : graph){
		for(Integer node : adjacencyList){
			inDegree[node]++;
		}       	
	}
	Queue<Integer> q = new LinkedList<Integer>();
	for(int i=0;i<inDegree.length;i++){
		if(inDegree[i]==0)
			q.offer(i);
	}
	int count = 0;
	while(!q.isEmpty()){
		Integer v = q.poll();
		count++;
		System.out.print(v + "->");
		for(int neighbor : graph.get(v)){
			if(--inDegree[neighbor]==0)
				q.offer(neighbor);
		}
	}
	/* check isCyclic  or not
	return count == num;;
	*/
}

算法分析：

时间复杂度为O(n)，w为树的所有层里面的最大长度，空间复杂度O(w)。

Posted on Edited on Disqus:

算法思路：

定义： 栈里元素维持由栈底到栈顶从大到小的顺序叫递减栈。跟最小堆一样，递减栈的栈首元素最小。

反之是递增栈，不过此法因为用递减栈比较多，所以统称递减栈。通常是将下标而不是值放入到栈中，这样还可以知道元素间的距离。

应用：

  1. 数组不能打乱顺序且求极值

注意事项：

  1. 跟最小堆一样，当元素大于栈顶元素的时候才倒逼栈内元素出栈。

Python代码：

1
2
3
4
5
6
stack = []
for i in range(len(li)):
	while stack and li[i] > li[stack[-1]]:
		index = stack.pop()

	stack.append(i)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

Free mock interview