KK's blog

每天积累多一些

0%

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:

算法思路：

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

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

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

递减栈 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而不是0，这样不用处理stack剩下的元素

例子：

1
2
3
4
5
6
7
8
9
10
# [1, 2], [2, 1]
def nextGreaterElements(self, nums: List[int]) -> List[int]:
	nums_copy = nums * 2
	stack, res = [], [-1] * len(nums_copy)
	for i in range(len(nums_copy)):
		while stack and nums_copy[i] > nums_copy[stack[-1]]:
			index = stack.pop()
			res[index] = nums_copy[i]
		stack.append(i)
	return res[:len(nums)]

算法分析：

时间复杂度为O(n)，空间复杂度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”, prev_op = “*“, num=”6”.
公式： [prev][prev_op][num][c=op]
实现时候先写只有加减的，再处理乘除，思维从简单开始。注意减法容易遗漏 

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

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. graph的值是node的下标, 注意in_degree的赋值.
  3. 第四步判断是否含循环必不可少，要根据题目要求来处理。除非L310 min height明确一定有解，而L269外星人字典就明确可能无解

Python代码：

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

	start_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0]
	queue, res = deque(start_nodes), []
	while queue:
		node = queue.popleft()
		res.append(node)
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	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:

算法思路：

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

适用条件：

prefix搜索和文件系统
变体：Trie+DFS, search中迭代变递归，详见算法知识目录

注意事项：

  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
)

实现思路：

  1. 数据结构为多叉树defaultdict(TrieNode)
  2. 实现用链表来迭代写，self.head是fake node
  3. search和startsWith的遍历指针从head开始，比较指针的子节点(下一位)和s[i]. 不能比较指针是否为空, 因为it=it.children[s[i]]后，it就肯定不会空，由于defaultdict

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为单词长度。

Free mock interview