KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2<sup>31</sup>, 2<sup>31</sup> - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “1+1”
Output: 2


Example 2:

Input: s = “6-4/2”
Output: 4


Example 3:

Input: s = “2(5+52)/3+(6/2+8)”
Output: 21


Constraints:

1 <= s <= 10<sup>4</sup> s consists of digits, '+', '-', '*', '/', '(', and ')'.
s is a *valid expression.

题目大意：

实现字符串加减乘除且有括号。

解题思路：

类似于Leetcode 227求加减乘除，这里多了括号，括号内含加减乘除，所以每对括号是一轮DFS。遇到左括号，就进入递归，遇到右括号就返回递归值

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

解题步骤：

N/A

注意事项：

  1. 不同于L227, 类似于填位法将i作为DFS参数传入，返回括号内的值以及i。i放入while循环， i += 1要加入到空格情况和循环最后
  2. 最后位加入加号要移除DFS中，放入主函数
  3. 注意处理括号情况的顺序，左括号在空格后，右括号在最后

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 calculate(self, s: str) -> int:
	s += '+'
	return self.dfs(s, 0)

def dfs(self, s, i):
	res, num, stack, op = 0, 0, [], '+'
	while i < len(s):
		char = s[i]
		if char == ' ':
			i += 1
			continue
		if char == '(':
			num, i = self.dfs(s, i + 1)
		elif char.isdigit():
			num = num * 10 + int(char)
		elif op == '-':
			stack.append(-num)
		elif op == '+':
			stack.append(num) # [4+2*1]
		elif op == '*':
			prev = stack.pop()
			stack.append(prev * num)
		elif op == '/':
			prev = stack.pop()
			stack.append(int(prev / num))  # remember
		if char in '+-*/':
			num = 0
			op = char

		if char == ')':
			return sum(stack), i
		i += 1
	return sum(stack)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:



Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]


Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]


Constraints:

m == mat.length n == mat[i].length
1 <= m, n <= 10<sup>4</sup> 1 <= m * n <= 10<sup>4</sup>
* -10<sup>5</sup> <= mat[i][j] <= 10<sup>5</sup>

题目大意：

按类对角线梅花间竹地遍历每个元素，输出最后结果

找规律解题思路：

边界条件很难找，而且每一层的结束点也和矩阵的长度或宽度有关。先找规律，可以看出

1
每层的所有元素下标和相等

正常从左到右从上到下遍历矩阵，用一个dict来每层的每一个数，可以看出这些数的顺序都是按题目要求的，只不过是正序或逆序，所以最后按照奇偶决定是否正序或逆序加入到结果

解题步骤：

  1. 从左到右从上到下遍历矩阵，dict[i + j]来加入每层的每一个数
  2. dict的key的范围容易得知，按照奇偶决定是否正序或逆序加入到结果

注意事项：

  1. dict[i + j]来加入每层的每一个数
  2. dict的key的最大值为len(mat) + len(mat[0]) - 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
	groups = collections.defaultdict(list)
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			groups[i + j].append(mat[i][j])
	res = []
	for i in range(len(mat) + len(mat[0]) - 1):
		if i % 2 == 1:
			res.extend(groups[i])
		else:
			res.extend(groups[i][::-1])
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)

按题意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
def print_diagnals(matrix):
    if not matrix or not matrix[0]:
        return []
    res = []
    is_reversed = True
    # all diagnal starting from top row
    for col in range(len(matrix[0])):
        diag_row, diag_col = 0, col
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    # diagnal start rightmost columns
    for row in range(1, len(matrix)):
        diag_row, diag_col = row, len(matrix[0]) - 1
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    return res

算法分析：

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

Posted on Edited on Disqus:

A list of user ids + IPs, a list of user ids who have made purchases, a list of advertisement
clicks with user IPs.
Each user id has at most 1 IP.

Output: for each ad, output the number of clicks and the number of purchases.

completed_purchase_user_ids = ["123"]

ad_clicks = [
    #"IP_Address,Time,Ad_Text",
    "127.0.0.1,2011-01-03 09:21:22,black pen"]

all_user_ips = [
    #"User_ID,IP_Address",
        "123,127.0.0.1"]

输出:
black pen, 1 click, 1 purchase

题目大意：

给定购买记录，click记录，ip地址。求每个产品点击数和购买次数

解题思路：

此题比较直观，点击数直接可以从click记录中获得，购买次数就是将三个表格join一起获得

解题步骤：

N/A

注意事项：

  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
    def get_ad_clicks_purchases(self, completed_purchase_user_ids, ad_clicks, all_user_ips):
    	# get clicks
    	product_to_clicks = collections.defaultdict(int)
    	for ad_click in ad_clicks:
    		parts = ad_click.split(',')
    		product_to_clicks[parts[2]] += 1

    	# get purchases
    	userid_to_ip = collections.defaultdict(str)
    	for all_user_ip in all_user_ips:
    		parts = all_user_ip.split(',')
    		userid_to_ip[parts[0]] = parts[1]

    	ip_to_product = collections.defaultdict(str)
    	for ad_click in ad_clicks:
    		parts = ad_click.split(',')
    		ip_to_product[parts[0]] = parts[2]

    	product_to_purchase = collections.defaultdict(int)
    	for user_id in completed_purchase_user_ids:
    		ip = userid_to_ip[user_id]
    		product = ip_to_product[ip]
    		product_to_purchase[product] += 1

    	res = []
    	for product, click in product_to_clicks.items():
    		res.append((product, click, product_to_purchase[product]))
    	return res

算法分析：

时间复杂度为O(n + m + p)，空间复杂度O(n + m + p), n, m, p分别每个表的大小

Posted on Edited on Disqus:

LeetCode



Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified and no extra space is inserted between words.

Note:

A word is defined as a character sequence consisting of non-space characters only. Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

Example 1:

Input: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
Output:
[
   “This    is    an”,
   “example  of text”,
   “justification.  “
]


Example 2:

Input: words = [“What”,”must”,”be”,”acknowledgment”,”shall”,”be”], maxWidth = 16
Output:
[
  “What   must   be”,
  “acknowledgment  “,
  “shall be        “
]
Explanation: Note that the last line is “shall be    “ instead of “shall     be”, because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.


Example 3:

Input: words = [“Science”,”is”,”what”,”we”,”understand”,”well”,”enough”,”to”,”explain”,”to”,”a”,”computer.”,”Art”,”is”,”everything”,”else”,”we”,”do”], maxWidth = 20
Output:
[
  “Science  is  what we”,
  “understand      well”,
  “enough to explain to”,
  “a  computer.  Art is”,
  “everything  else  we”,
  “do                  “
]


Constraints: 1 <= words.length <= 300
1 <= words[i].length <= 20 words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100 words[i].length <= maxWidth

题目大意：

加入尽量均等的空格使得单词组成的每行左右对齐

Round Robin加入space解题思路(推荐)：

法二是先将一个space加入到预结果，再计算extra spaces，计算比较复杂。此法与maxWidth比较时，用1个space，而最后不区分正常space和extra space，将space按round robin方法加入，不用考虑法二复杂的计算公式。

注意事项：

  1. 关键变量两个word_list, cur_len. 用目前结果cur_len + 空格个数 + 准加入单词长度与maxWidth比较。1个单词和2个单词以上的空格情况都照顾到了。
  2. i % (len(word_list) - 1)若长度为1时候，不能对0取余，所以此情况要变成1， 加入or 1。word_list中的单词加入空格
  3. 最后一行用ljust向左对齐，右边补齐空格

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
	res = []
	word_list, cur_len = [], 0
	for word in words:
		if cur_len + len(word_list) + len(word) > maxWidth:
			for i in range(maxWidth - cur_len):
				word_list[i % (len(word_list) - 1 or 1)] += ' '
			res.append(''.join(word_list))
			word_list, cur_len = [], 0
		word_list.append(word)
		cur_len += len(word)
	return res + [' '.join(word_list).ljust(maxWidth)]

算法分析：

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

计算extra space算法II解题思路：

用公式计算空格数和位置：

1
extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1)

解题步骤：

N/A

注意事项：

0.1 题目要求： 若空格有多余，尽量分到前面；若某一行只有一个单词，左对齐右补空格；最后一行无论多少个单词都是左对齐右补空格
0.2 用buffer记录这一行的单词，count记录单词和空格的长度，若count + 当前单词长度大于maxWidth就处理

  1. 公式：extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1)
    有多余空格就分配到单词间隔个数中len(buffer) - 1，而不是单词个数. 商为多余的空格个数，余数为从第几位开始，减一个空格。如x x x x，idx = 1，表示平分后仍多出一个空格，所以分配到第0个到第1个单词之间，也就是[:idx + 1]中，而剩余的buffer[idx + 1:]比上述少一个空格。它们之间的连接用较少空格数
  2. 公式中若余数为0， 表示全部平均分配，这时要取extra_space_num + 1，所以令idx = len(buffer) - 1。 extra_space_num + 1里面的1是原本就应该有一个空格，所以此情况并没有额外多空格。
  3. 公式中len(buffer) - 1可能为0，所以要特别处理，对应到题目要求的第二点
  4. 最后一行是buffer的内容，出来for循环后，向右加空格，对应到题目要求的第三点，代码与第二点要求类似

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 fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
	# words.append(' ' * maxWidth)
	buffer, count, res = [], 0, []
	for word in words:
		new_length = len(word) if len(buffer) == 0 else 1 + len(word)
		if count + new_length <= maxWidth:
			buffer.append(word)
			count += new_length
		else:
			num_space_left = maxWidth - count # 3
			if len(buffer) > 1:
				extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1) # 3, 0
				if idx == 0:
					idx = len(buffer) - 1
				tmp = (' ' * (extra_space_num + 1)).join(buffer[:idx + 1]) + (' ' * extra_space_num) #
				tmp += (' ' * extra_space_num).join(buffer[idx + 1:])
				res.append(tmp.strip())
			else:
				tmp = buffer[0] + (' ' * (maxWidth - len(buffer[0])))
				res.append(tmp)
			buffer = [word]
			count = len(word)

	if buffer:
		res.append(' '.join(buffer))
		res[-1] += (' ' * (maxWidth - len(res[-1])))
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that you must take course b<sub>i</sub> first if you want to take course a<sub>i</sub>.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].


Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].


Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]


Constraints: 1 <= numCourses <= 2000
`0 <= prerequisites.length <= numCourses (numCourses - 1)*prerequisites[i].length == 2*0 <= ai, bi < numCourses*ai != bi* All the pairs[ai, bi]` are distinct.

题目大意：

课程有先修课要求，求修课的顺序

算法思路：

拓扑排序的经典题

注意事项：

  1. 注意题目要求课程可能存在循环，记得第四部侦测循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
	in_degree = [0] * numCourses
	graph = [[] for _ in range(numCourses)]
	for li in prerequisites:
		in_degree[li[0]] += 1
		graph[li[1]].append(li[0])
	queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 0])
	res = []
	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 numCourses == len(res) else []

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
public int[] findOrder(int numCourses, int[][] prerequisites) {
	ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> res = new ArrayList<>();
	for(int i=0;i<numCourses;i++)
		graph.add(new ArrayList<Integer>());
	int[] inDegree = new int[numCourses];
	//populate inDegree & convert to graph
	for(int i=0;i<prerequisites.length;i++){
		//[0,1] means 1->0
		inDegree[prerequisites[i][0]]++;
		graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
	}
	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();
		res.add(v);
		count++;
		for(int neighbor : graph.get(v)){
			if(--inDegree[neighbor]==0)
				q.add(neighbor);
		}
	}
	if(count != numCourses)
		res.clear();

	return res.stream().mapToInt(i->i).toArray();
}

算法分析：

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

Free mock interview