KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

算法思路：

  1. 递归找pivot，然后按小于pivot和大于等于pivot分成两组。每轮递归，pivot肯定在正确（最终）位置上
  2. partition方法类似于Leetcode75的sort colors一样用两个指针i和noSmallerIdx。i是循环指针，而
    noSmallerIdx是第二组大于等于pivot的首元素. 由于前面已经分为两部分了，所以nums[i]只有比pivot小才需要交换到前面，否则符合顺序，不用交换
  3. 循环结束后，将pivot交换到正确的位置上。


i指向4，因为4小于pivot，所以要换到前面去，跟6置换，noSmallerIdx向后移。

注意事项：

  1. range(start, end)不含end，因为end指向pivot

应用：

  1. 排序
  2. 快速选择quick select
  3. partition，如Leetcode 75

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def quick_sort(self, nums: List[int]):
	if not nums:
		return
	self.q_sort(nums, 0, len(nums) - 1)

def q_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	pivot = self.partition(nums, start, end)
	self.q_sort(nums, start, pivot - 1)
	self.q_sort(nums, pivot + 1, end)

def partition(self, nums: List[int], start: int, end: int):
	no_smaller_index, pivot = start, end
	for i in range(start, end):
		if nums[i] < nums[pivot]:
			nums[no_smaller_index], nums[i] = nums[i], nums[no_smaller_index]
			no_smaller_index += 1
	nums[no_smaller_index], nums[end] = nums[end], nums[no_smaller_index]
	return no_smaller_index

算法分析：

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

Quick Select

选择第k小的数(下标从0开始)

注意事项：

  1. left > right不再是等于，因为几个数相等的情况，排序的时候不用再移动，但第k小里面需要继续递归。
  2. binary select是单边递归，而不是双边。要判断pivot是否等于k。
  3. 递归调用仍用k，而不是跟pivot_pos相关，因为k是下标位置
  4. partition中range用[start, end)而不是len

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def quick_select(self, nums: List[int], k: int) -> int:
	if not nums:
		return -1
	return self.q_select(nums, 0, len(nums) - 1, k)

def q_select(self, nums: List[int], start: int, end: int, k: int):
	if start > end:
		return -1
	pivot = self.partition(nums, start, end)
	if k == pivot:
		return nums[pivot]
	if k < pivot:
		return self.q_select(nums, start, pivot - 1, k)
	else:
		return self.q_select(nums, pivot + 1, end, k)

算法分析：

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

Partition

用于原位排序，将相应的元素放入该放的位置直到不满足条件为止

注意事项：

  1. i不一定会移动，放在else里面 
1
2
3
4
5
6
7
8
9
10
def sort(self, nums: List[int]) -> int:
	i = 0
	while i < len(nums):
		if <condition>
			self.swap(nums, i, j)
		else:
			i += 1

def swap(self, nums, i, j):
	nums[i], nums[j] = nums[j], nums[i]

上述算法的问题不能有效处理两种情况：

  1. 有序数组[1, 2, 3, 4]
  2. 单一数组[2, 2, 2, 2]

第一种情况递归为
[123]
[12]
[1]
只会递归左半，不会递归右半

第二种情况
[2222]
[222]
[22]
[2]
只会递归右半，不会递归左半
这两种情况都是O(n^2)

解决第一个问题用randomize pivot的方法
解决第二个问题用three-way partition的方法，类似于75 Sort colors将区间从两个变成3个: 小于pivot, 等于pivot，大于pivot，这样对于单一值数组，左半和右半就不会递归了

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
def sortArray(self, nums: List[int]) -> List[int]:
	if not nums:
		return
	self.q_sort(nums, 0, len(nums) - 1)
	return nums


def q_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	pivot = random.randint(start, end)
	nums[pivot], nums[start] = nums[start], nums[pivot]
	lt, gt = self.partition(nums, start, end)
	self.q_sort(nums, start, lt - 1)
	self.q_sort(nums, gt, end)

def partition(self, x, start, end):
	i, lt, gt = start, start, end
	while i <= gt and i < len(x) and gt >= 0:
			if x[i] < x[lt]:
					x[i], x[lt] = x[lt], x[i]
					i += 1
					lt += 1
			elif x[i] > x[lt]:
					x[i], x[gt] = x[gt], x[i]
					gt -= 1
			else: # x[i] == x[lt]
					i += 1
	return lt, gt

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
public void sort(int[] arr) {
	if(arr == null || arr.length == 0)
		return;
	quickSort(arr, 0, arr.length - 1);
}

void quickSort(int[] arr, int left, int right) {
	if(left >= right)
		return;
	int pivotPos = partition(arr, left, right);
	quickSort(arr, left, pivotPos - 1);
	quickSort(arr, pivotPos + 1, right);
}

int partition(int[] arr, int left, int right) {
	int noSmallerIdx = left;
	int pivot = arr[right];
	for(int i = left; i < right; i++) {
		if(arr[i] < pivot) 
			swap(arr, noSmallerIdx++, i);
	}
	swap(arr, noSmallerIdx, right);
	return noSmallerIdx;
}

void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

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里做

实现思路：

  1. 数据结构为a->b的父子parent[a]=b关系defaultdict(str)
  2. find实现用来DFS写,先找到root，将所有节点连到root

Python代码：

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

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

    def find(self, s):
        if self.parents[s] == s:
            return s
        root = self.find(self.parents[s])
        return root

    def union(self, s1, s2):
        root1, root2 = self.find(s1), self.find(s2)
        self.parents[root2] = root1  # 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:

LeetCode



Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:



Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.


Example 2:



Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2


Constraints:

The number of nodes in the tree is in the range [2, 10<sup>5</sup>]. -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
All Node.val are unique. p != q
* p and q will exist in the BST.

题目大意：

BST中求给定的两节点的最低共同父亲节点

解题思路：

三种情况，也是用DFS

解题步骤：

N/A

注意事项：

  1. pq一定存在，所以有**三种情况： 1) p或q是root，另一是其子孙。 2) p，q分列root两边。 3) p，q在root的一边。跟LeetCode 236 Lowest Common Ancestor of a Binary Tree不同的是，
    第二种情况，不用递归即知道，因为这是BST。第一和第三种情况同
  2. 第二种情况由于要比较p, q, root顺序，所以要令p, q有序，Line 4-5

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
	if not root:
		return None
	if p.val > q.val: # remember
		return self.lowestCommonAncestor(root, q, p)
	if p.val <= root.val <= q.val or p == root or q == root: # remember root is p or q
		return root
	if p.val < root.val and q.val < root.val:
		return self.lowestCommonAncestor(root.left, p, q)
	else:
		return self.lowestCommonAncestor(root.right, p, q)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]


Example 2:

Input: nums = [0]
Output: [0]


Constraints:

1 <= nums.length <= 10<sup>4</sup> -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

Follow up: Could you minimize the total number of operations done?

题目大意：

将数组的0全部移到数组末

解题思路：

简单题。Quicksort的partition的应用

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def moveZeroes(self, nums: List[int]) -> None:
    	"""
    	Do not return anything, modify nums in-place instead.
    	"""
    	first_zero_idx = 0
    	for i in range(len(nums)):
    		if nums[i] != 0:
    			nums[i], nums[first_zero_idx] = nums[first_zero_idx], nums[i]
    			first_zero_idx += 1

算法分析：

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

Posted on Edited on Disqus:

LeetCode

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.



Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.



Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.



 


Example 1:



Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above


Example 2:



Input: n = 1
Output: [[“Q”]]


 


Constraints:




  • 1 <= n <= 9


题目大意：

八皇后问题，求所有解

Global dict算法思路(推荐)：

DFS填位法模板

注意事项：

  1. 用3个set，col_set, 对角线，反对角线set来提高效率。
  2. path用append的方法加入，这样终止条件用n来比较，不能用len(path)
  3. 打印函数中，one_result在每轮后reset；字符串不能改其中一个，只能用子串+Q+子串： (‘.’ path[i]) + ‘Q’ + (‘.’ (n - path[i] - 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
def solveNQueens(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs(n, 0, path, res, set(), set(), set())
	result = self.convert(res)
	return result

def dfs(self, n, start, path, res, col_set, diag_set, anti_diag_set):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		if not self.is_valid(start, i, col_set, diag_set, anti_diag_set):
			continue
		path.append(i)  # [0, 2]
		col_set.add(i)
		diag_set.add(start - i)
		anti_diag_set.add(start + i)
		self.dfs(n, start + 1, path, res, col_set, diag_set, anti_diag_set)
		anti_diag_set.remove(start + i)
		diag_set.remove(start - i)
		col_set.remove(i)
		path.pop()

def is_valid(self, i, val, col_set, diag_set, anti_diag_set):
	if val in col_set or i - val in diag_set or i + val in anti_diag_set:
		return False
	return True

算法分析：

时间复杂度为O(n x n!)，解大小乘以path长度,空间复杂度O(n^2)

常数空间算法II解题思路(推荐)：

较直观的方法，但复杂度稍差

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
def solveNQueens2(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs2(n, 0, path, res)
	result = self.convert(res)
	return result

def dfs2(self, n, start, path, res):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		path.append(i) # [0, 2]
		if self.is_valid2(path):
			self.dfs2(n, start + 1, path, res)
		path.pop()

def is_valid2(self, path):
	if len(path) != len(set(path)):
		return False
	for i in range(len(path)):
		for j in range(i + 1, len(path)):
			#if i == j:
			 #   continue
			if abs(i - j) == abs(path[i] - path[j]):
				return False
	return True

def convert(self, res):
	result, one_result = [], []
	for k in range(len(res)):
		one_result = [] # remember
		path = res[k]
		n = len(path)
		for i in range(n):
			s = ('.' * path[i]) + 'Q' + ('.' * (n - path[i] - 1))  # remember not s[path[i]] = 'Q'
			one_result.append(s)
		result.append(one_result)
	return result

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
public List<List<String>> solveNQueens2(int n) {
	List<List<String>> res = new ArrayList<>();
	int[] col = new int[n];
	solveR(n, col, 0, res);
	return res;
}

// 5/2/2020
void solveR(int n, int[] col, int st, List<List<String>> res) {
	if(st == n) {
		print(col, res);
		return;
	}
	
	for(int i = 0; i < n; i++) {
		col[st] = i;
		if(isValid(col, st))
			solveR(n, col, st + 1, res);
	}
}

boolean isValid(int[] col, int k) {
	for(int i = 0; i < k; i++) {
		if(col[i] == col[k])
			return false;
	}

	for(int i = 0; i < k; i++) {
		if(Math.abs(k - i) == Math.abs(col[k] - col[i])) //use abs
			return false;
	}
	return true;
}

算法分析：

时间复杂度为O(n x n!)，空间复杂度O(n^2)

Free mock interview