KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

算法思路：

Leetcode 046的题目。这里作为知识点归纳。

  1. 类似于组合题，但用到了visited数组且递归中从i=0开始。

应用：

  1. 找所有可能性

注意事项：

  1. 每一种排列加入到结果集时要复制path。

Leetcode 046 Permutations 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def permute(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return [[]]
	path, result, visited = [], [], set()
	self.dfs(nums, path, result, visited)
	return result

def dfs(self, nums, path, result, visited):
	if len(path) == len(nums):
		result.append(list(path))
		return

	for i in range(len(nums)):
		if i in visited:
			continue
		path.append(nums[i])
		visited.add(i)
		self.dfs(nums, path, result, visited)
		visited.remove(i)
		path.pop()

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
public List<List<Integer>> permute(int[] nums) {
	List<Integer> path = new ArrayList<>();
	List<List<Integer>> res = new ArrayList<>();
	if(nums == null) {
		return res;
	}
	dfs(nums, new HashSet<>(), path, res);
	return res;
}

void dfs(int[] nums, Set<Integer> visited, List<Integer> path, List<List<Integer>> res) {
	if(path.size() == nums.length) {
		res.add(new ArrayList<>(path));
		return;
	}
	
	for(int i = 0; i < nums.length; i++) {
		if(visited.contains(i))
			continue;
		visited.add(i);
		path.add(nums[i]);
		dfs(nums, visited, path, res);
		visited.remove(i);
		path.remove(path.size() - 1);
	}
}

算法分析：

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

Posted on Edited on Disqus:

算法思路：

  1. 递归找pivot，然后按小于pivot和大于等于pivot分成两组。每轮递归，pivot肯定在正确（最终）位置上
  2. partition方法类似于Leetcode75的sort colors一样用两个指针i和noSmallerIdx。i是循环指针，而
    noSmallerIdx是第二组大于等于pivot的首元素，或者理解为比pivot小的元素（指针i指着）将要被交换
    的位置（比pivot大的元素）=比pivot小的元素的最后一个+1.
  3. 循环结束后，将pivot交换到正确的位置上。


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

应用：

  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]

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:

中序遍历算法思路：


如图所示，总体思路是左节点按层次遍历，而区别在于何时加入到结果集。

  1. 首先初始化将root的所有左儿子加入到stack。
  2. 开始循环，取出节点，判断其右儿子不为空，因为左儿子已经访问过。
  3. 若右子树不为空，跟初始化一样，将右子树的所有左儿子加入到栈中。
  4. 用到两个指针node和n，分别指向出栈节点和遍历所有左儿子节点。

若前序遍历，只要把打印语句从出栈时打印移到入栈时打印即可。见L144

应用：

  1. BST的关于Iterator的题目Leetcode 173
  2. 不需要遍历所有节点而需要遍历某些节点的题目如求某target最接近N个节点。Leetcode 272

中序遍历

Leetcode 094 Binary Tree Inorder Traversal

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def iterative_inorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append(it)
		it = it.left
	while stack:
		node = stack.pop()
		res.append(node.val)
		if node.right:
			n = node.right
			while n:
				stack.append(n)
				n = n.left
	return res

前序遍历

Leetcode 144 Binary Tree Preorder Traversal
只要将出栈节点加入结果换到入栈前加即可，也就是将Line 11换到取Line 7和Line 15

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def iterative_preorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append(it)
		res.append(it.val)
		it = it.left
	while stack:
		node = stack.pop()
		if node.right:
			n = node.right
			while n:
				stack.append(n)
				res.append(n.val)
				n = n.left
	return res

后序遍历

Leetcode 145 Binary Tree Postorder Traversal
跟中序比，需要用一个记数器来记录出现在栈顶的次数，若为2次就加入到结果集，并且不能继续迭代到右节点，因为第一次时候已做了。
由于tuple不可改，所以即使次数为1，也要出栈，更新次数后重新入栈。代码区别在Line 10 - 17.

注意事项：

  1. 记得要continue。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def iterative_postorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append((it, 0))  # count for it in the stack top
		it = it.left
	while stack:
		pair = stack.pop()
		node = pair[0]
		occurrence = pair[1] + 1
		if occurrence == 2:
			res.append(node.val)
			continue  # don't iterate on right node again
		else:
			stack.append((node, occurrence))
		if node.right:
			n = node.right
			while n:
				stack.append((n, 0))
				n = n.left
	return res

递归写法

DFS
BST的递归前序遍历Leetcode 0144
BST的递归中序遍历Leetcode 0094

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def recursive_inorder(self, root: TreeNode) -> List[int]:
	return self.dfs_inorder(root)

def dfs_inorder(self, root):
	if not root:
		return []
	return self.dfs_inorder(root.left) + [root.val] + self.dfs_inorder(root.right)

def recursive_preorder(self, root: TreeNode) -> List[int]:
	return self.recursive_preorder(root)

def recursive_preorder(self, root):
	if not root:
		return []
	return [root.val] + self.recursive_preorder(root.left) + self.recursive_preorder(root.right)

def recursive_postorder(self, root: TreeNode) -> List[int]:
	return self.recursive_postorder(root)

def recursive_postorder(self, root):
	if not root:
		return []
	return self.recursive_postorder(root.left) + self.recursive_postorder(root.right) + [root.val]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
protected void iterativeInorder(BinaryNode p) {  
	Stack<BinaryNode> stack = new Stack<BinaryNode>();  
	BinaryNode head = p;
	while(head != null) {
		stack.push(head);
		head = head.left;
	}
	
	BinaryNode node = null;
	while (stack.size() > 0) {  
		node = stack.pop();
		System.out.print(node.data);
		if(node.right != null) {
			BinaryNode n = node.right; 
			while(n != null) {
				stack.push(n);
				n = n.left;
			}
		}
	}  
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(logn)，最差为O(n)。

Posted on Edited on Disqus:

LeetCode 272 Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and _k_ = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

题目大意：

找BST中给定目标的最接近的k个值。

解题思路：

首先观察得到最接近的节点一定在二叉树的搜索路径上的节点的其中一个。这样可以分成两组
前驱节点和后驱节点（比target大），加入到两个stack中，由BST的iterator可以知道这两个
stack的越靠近栈首就越接近target，所以出栈的一定是最接近target的。只要比较两栈首元素
即可。如果某个节点出栈要找其儿子节点填充。找前驱节点和后驱节点的方法是相反的。这里可
参照KB的BST非递归中序遍历。

注意事项：

  1. 找最接近target的节点，不用判断左右儿子是否为空，因为若为空，表示root更接近。大于target的放入successors，否则是predecessors
  2. 然后判断两栈首谁大，谁大的就获得相应的比它远离target的节点入栈。如predecessors是左节点的所有右儿子。

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
def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
	predecessors, successors = [], []
	it = root
	while it:
		if target < it.val:
			successors.append(it)
			it = it.left
		else:
			predecessors.append(it)
			it = it.right
	res = []
	while k > 0:
		if predecessors and (not successors or target - predecessors[-1].val < successors[-1].val - target):
			node = predecessors.pop()
			if node.left:
				n = node.left
				while n:
					predecessors.append(n)
					n = n.right
			res.append(node.val)
		else:
			node = successors.pop()
			if node.right:
				n = node.right
				while n:
					successors.append(n)
					n = n.left
			res.append(node.val)
		k -= 1
	return res

注意事项：

  1. target - preOrder.peek().val < postOrder.peek().val - target的条件前
    记得加上!preOrder.isEmpty()

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
public List<Integer> closestKValues(TreeNode root, double target, int k) {
	List<Integer> res = new ArrayList<>();
	if(root == null)
		return res;
	Stack<TreeNode> preOrder = new Stack<>();
	Stack<TreeNode> postOrder = new Stack<>();
	findTargetAndPopulateStacks(preOrder, postOrder, root, target);
	
	while(k-- > 0) {
		if(postOrder.isEmpty() || (!preOrder.isEmpty() && 
				target - preOrder.peek().val < postOrder.peek().val - target))
			getPredecessor(preOrder, res);
		else 
			getSuccessor(postOrder, res);
	}
	return res;
}

void findTargetAndPopulateStacks(Stack<TreeNode> preOrder, Stack<TreeNode> postOrder, 
		TreeNode root, double target) {
	TreeNode node = root;
	while(node != null) {
		if(node.val < target) { 
			preOrder.push(node);
			node = node.right;
		}
		else {
			postOrder.push(node);
			node = node.left;
		}
	}
}

void getSuccessor(Stack<TreeNode> postOrder, List<Integer> res) {
	TreeNode node = postOrder.pop();
	res.add(node.val);
	if(node.right != null) {
		TreeNode n = node.right;
		while(n != null) {
			postOrder.push(n);
			n = n.left;
		}
	}
}

void getPredecessor(Stack<TreeNode> preOrder, List<Integer> res) {
	TreeNode node = preOrder.pop();
	res.add(node.val);
	if(node.left != null) {
		TreeNode n = node.left;
		while(n != null) {
			preOrder.push(n);
			n = n.right;
		}
	}
}

算法分析：

时间复杂度为O(k + logn)，空间复杂度O(logn)。

Posted on Edited on Disqus:

LeetCode 173 Binary Search Tree Iterator



Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:



BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false


Note:

next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree. You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

题目大意：

实现BST的Iterator

算法思路：

参照KB中BST的非递归中序遍历。将其分拆为初始化以及去掉stack不为空的循环分别为所求。

注意事项：

  1. 初始化，将root所有左节点加入到stack。先写next，出栈栈顶节点，将它的右儿子的所有左节点入栈。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class BSTIterator(TestCases):

    def __init__(self, root: TreeNode):
        self.stack = []
        it = root
        while it:
            self.stack.append(it)
            it = it.left

    def next(self) -> int:
        node = self.stack.pop()
        if node.right:
            n = node.right
            while n:
                self.stack.append(n)
                n = n.left
        return node.val

    def hasNext(self) -> bool:
        return True if self.stack else False

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
Stack<TreeNode> s = new Stack<>();
public L173BinarySearchTreeIterator(TreeNode root) {
	TreeNode head = root;
	while(head != null) {
		s.push(head);
		head = head.left;
	}
}

// Recommended
public int next2() {
	TreeNode node = s.pop(); 
	if(node.right != null) {// left node has been visited
		TreeNode n = node.right; 
		while(n != null) {
			s.push(n);
			n = n.left;
		}
	}
	return node.val;

}

/** @return whether we have a next smallest number */
public boolean hasNext() {
	return !s.isEmpty();
}

算法分析：

next的平均时间复杂度(amortized complexity)为O(1)，n为字符串长度，空间复杂度O(logn)。

Free mock interview