KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

算法思路：

递归分前半和后半排序然后合并。

应用：

  1. 排序
  2. 求逆序数

注意事项：

  1. merge函数中更改输入nums。
  2. line 15的等号决定是否stable sort。

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 merge_sort(self, nums: List[int]):
	self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.m_sort(nums, start, mid)
	self.m_sort(nums, mid + 1, end)
	self.merge(nums, start, mid, end)

def merge(self, nums: List[int], start: int, mid: int, end: int):
	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:  # = decides if it is stable sort
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

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

Posted on Edited on Disqus:

括号题

算法思路：

  1. 优先考虑用Stack。Stack可以将字符压入比较或者字符的下标压入比较，后者信息量更大
    三种情况不合法： ‘[‘ (stack有余，for后发生), ‘]’ (要匹配的时候stack为空，for中发生), ‘{]’ (不匹配，for中发生)
  2. DP
  3. 1) 左括号的数量在每一位都大于等于右括号数量
    2) 右括号的总和要等于右括号总和
    以上两个条件都满足的话，左右括号匹配，但此法只能用于单种括号

应用：

  1. 括号题
  2. 字符串运算题如, 3+4, (3+4)*5

括号运算题

stack的作用是存储优先级较低的操作数(暂时不能计算)
定义公式

res是作为同一层的临时计算结果，若遇到左括号，res保留在stack中且reset，若遇到右括号，stack的结果还原到res
num也是临时变量负责储存整数

注意事项：

  1. char.isdigit()的计算
  2. 左括号：入栈和reset res和num。
  3. 右括号:出栈和还原res = tmp + f(res)。

括号运算题模板：

1
2
3
4
5
6
7
8
9
10
def parenthesis(self, s: str) -> int:
    (Optional) s边界处理如s += '+' 
	stack, num = [], 0 数据结构用stack以及stack的一个元素
	for char in s:
	    所有字符的可能情况
		比如
		if char.isdigit(): 
			num = num * 10 + int(char)
        如果某情况入栈就一定要重置参数num=0		
		如果某情况出栈，代入公式计算

算法分析：

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

LeetCode 394 Decode String

两个stack存储优先级较低的字符以及数字，类似于多重括号2*(3*(4))
公式：prev_res+prev_num*[res] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def decodeString(self, s: str) -> str:
	stack_num, stack_char, num, char_str = [], [], 0, ""
	# char_str + num[<>]
	for c in s:
		if c.isdigit():
			num = 10 * num + int(c)
		if c.isalpha():
			char_str += c
		if c == "[":
			stack_num.append(num)
			stack_char.append(char_str)
			num = 0
			char_str = ""
		if c == "]":
			prev_char = stack_char.pop()
			prev_num = stack_num.pop()
			char_str = prev_char + prev_num * char_str
	return char_str

LeetCode 227 Basic Calculator II

stack=只存加号操作符
核心思想是只有出现运算符，才能计算前一个数[op]num. 所以op和num是记录前一个符号和数字
字符三种类别:空格，数字和运算符
若遇到运算符，就处理四种的op，目标是都要把num压栈，但是op是乘除要计算积或商后才能压栈。压栈后num=0，
若5*6+, char=”+”的时候, prev = “5”, op = “*“, num=”6”.
公式： [prev][op][num][char] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def calculate(self, s: str) -> int:
	# prev[op]+num[char]
	# 2-3
	stack, num, op = [], 0, '+'
	s += "+"
	for c in s:
		if c == " ":
			continue
		if c.isdigit():
			num = 10 * num + int(c) #2
		if c in "+-*/":
			if op == "+":
				stack.append(num)
			if op == "-":
				stack.append(-num)
			if op == "*":
				prev = stack.pop()
				stack.append(prev * num)
			if op == "/":
				prev = stack.pop()
				stack.append(int(prev / num))
			op = c # *
			num = 0
	return sum(stack)

Posted on Edited on Disqus:

算法思路：

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

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

应用：

  1. 找所有可能性

注意事项：

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

学习要点：

详见DFS要点，大部分DFS题目涉及

  1. 用到全组合的API: dfs(nums, start, path, result), 4个参数
  2. 用到全组合的递归: dfs(nums, i + 1, path, result)
  3. 用到全排列的其他部分包括恢复状态和终止条件(加入res)

Leetcode 046 Permutations 

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

def dfs(self, nums, visited, path, res): # 
	if len(path) == len(nums):
		res.append(list(path))
		return
	for i in range(len(nums)): 
		if i in visited:
			continue
		visited.add(i) # [2, 1]
		path.append(nums[i])
		self.dfs(nums, visited, path, res) 
		path.pop()
		visited.remove(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
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*n!)，空间复杂度O(1)。解大小乘以path长度

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:

算法思路：

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

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

求较大值 -> 递减栈
求较小值 -> 递增栈

递减栈 vs heap
实现上几乎一样，详见算法知识点目录。区别在于元素间是否需要保持顺序或者是否是stream

应用：

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

注意事项：

  1. 跟最小堆一样，当元素大于栈顶元素的时候才倒逼栈内元素出栈。
  2. 记得是stack[-1]看栈顶元素不是stack[0]

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)

LeetCode 503 Next Greater Element II
核心思想: 原数组复制一遍，用新数组完全做一遍递减栈，最后才截取结果

例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
def nextGreaterElements(self, nums: List[int]) -> List[int]:
	num_list = nums * 2
	result, stack = [0] * len(num_list), []
	for i in range(len(num_list)):
		while stack and num_list[i] > num_list[stack[-1]]:
			index = stack.pop()
			result[index] = num_list[i]
		stack.append(i)

	while stack:
		index = stack.pop()
		result[index] = -1
	return result[:len(nums)]

算法分析：

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

Free mock interview