KK's blog

每天积累多一些

0%

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.

<pre> 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"] </pre>

输出: black pen, 1 click, 1 purchase

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

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

<div>

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:

<pre>Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [    "This    is    an",    "example  of text",    "justification.  " ]</pre>

Example 2:

<pre>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.</pre>

Example 3:

<pre>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                  " ]</pre>

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

</div>

题目大意：

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

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

<div>

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:

<pre>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]. </pre>

Example 2:

<pre>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]. </pre>

Example 3:

<pre>Input: numCourses = 1, prerequisites = [] Output: [0] </pre>

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= a<sub>i</sub>, b<sub>i</sub> < numCourses
  • a<sub>i</sub> != b<sub>i</sub>
  • All the pairs [a<sub>i</sub>, b<sub>i</sub>] are distinct.

</div>

题目大意：

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

算法思路：

拓扑排序的经典题

注意事项：

  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)

Posted on Edited on Disqus:

LeetCode

<div>

Implement a SnapshotArray that supports the following interface:

  • SnapshotArray(int length) initializes an array-like data structure with the given length.  Initially, each element equals 0.
  • void set(index, val) sets the element at the given index to be equal to val.
  • int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
  • int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

<pre>Input: ["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]] Output: [null,null,0,null,5] Explanation: SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3 snapshotArr.set(0,5); // Set array[0] = 5 snapshotArr.snap(); // Take a snapshot, return snap_id = 0 snapshotArr.set(0,6); snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5</pre>

Constraints:

  • 1 <= length <= 50000
  • At most 50000 calls will be made to set, snap, and get.
  • 0 <= index < length
  • 0 <= snap_id <(the total number of times we call snap())
  • 0 <= val <= 10^9

</div>

题目大意：

设计一个数据结构支持数组的快照

Binary Search解题思路(推荐)：

暴力法是每次快照时候，将当时的数组的所有值存入dict中，key为(snap_id, index), value为数组值，得到MLE 后来考虑用二分法优化snap，将数值跟前值不同才存入历史记录，但得到TLE，应该是因为snap时间太长，因为要遍历整个数组
所以应该将存入历史这一步放在set中，每次值改变才存入历史记录，虽然一个snap_id可能会存入多值，大部分是不需要，因为同一个snap_id应该取最新值，但这样设计费了空间，省了时间。

解题步骤：

N/A

注意事项：

  1. 历史记录为3d数组，第一维为数组index, 第二维为所有历史记录，第三维为每一个记录为[snap_id, value]。由于数组初始值为0，所以初始历史记录为[-1, 0]
  2. snap_id和题目要求的id差1，比如第一次call snap为0，但是之前的snap应该为-1
  3. 最容易错的在于二分法，要先将snap_id + 1，比如[-1, 0], [0, 5], [0, 6], [0, 2], [1, 1], [1, 4]...找snap_id = 0的值也就是要找最后的，所以先加1，找到[1, 1]再下标减1

Python代码：

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

    def __init__(self, length: int):
        self.snap_id = 0
        self.history = [[[-1, 0]] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.history[index].append([self.snap_id, val])

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        last_snap_id = bisect.bisect(self.history[index], [snap_id + 1]) - 1 # remember snap + 1
        return self.history[index][last_snap_id][1]

算法分析：

get时间复杂度为O(logn)，空间复杂度O(n), 数组某值n更改次数

暴力法算法II解题思路(不推荐)：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def __init__(self, length: int):
	self.ary = [0] * length
	self.snap_id = -1
	self.idx_snap_to_val = {}

def set(self, index: int, val: int) -> None:
	self.ary[index] = val

def snap(self) -> int:
	self.snap_id += 1
	for i, n in enumerate(self.ary):
		self.idx_snap_to_val[(i, self.snap_id)] = self.ary[i]
	return self.snap_id

def get(self, index: int, snap_id: int) -> int:
	return self.idx_snap_to_val[(index, snap_id)]

Posted on Edited on Disqus:

LeetCode

<div>

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

<pre>Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1 Output: 6 Explanation: The shortest path without eliminating any obstacle is 10. The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2). </pre>

Example 2:

<pre>Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output: -1 Explanation: We need to eliminate at least two obstacles to find such a walk. </pre>

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 40
  • 1 <= k <= m * n
  • grid[i][j] is either 0 or 1.
  • grid[0][0] == grid[m - 1][n - 1] == 0

</div>

题目大意：

矩阵从左上走到右下，但含障碍，现在可以移除k个，使得路径最短，求最短路径

解题思路：

求最短路径用BFS，但此题难点在于distance跟路径有关，比如某一格可能属于不同的路径，此时它的distance会不同，所以distance不能global，必须作为state传到下一个迭代 同样的情况也在visited中存在，visited跟路径相关，而这一格跟k相关，这一格可以被属于不同的k的路径访问，所以visited应该加入k

解题步骤：

N/A

注意事项：

  1. visited是(x, y, k), queue是(x, y, k, dis)
  2. (x, y, k - 1)跟visited比较，而不是(x, y, k)。下一个节点的条件为eleminatios >= 0
  3. 若k过多会LTE, 因为广度会过大。这是用曼哈顿距离来剪枝。左上到右下距离为m - n + 2这肯定是最短距离，若k大于等于这个数，也就是可以移除曼哈顿路径上的所有障碍。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shortestPath(self, grid: List[List[int]], k: int) -> int:
	m, n = len(grid), len(grid[0])
	if k >= m + n - 2: # TLE
		return m + n - 2

	queue = collections.deque([(0, 0, k, 0)]) # x, y, k, distance
	visited = set([(0, 0, k)]) # include k
	while queue:
		_x, _y, _k, _dis = queue.popleft()
		if _x == m - 1 and _y == n - 1:
			return _dis
		for _dx, _dy in OFFSET:
			x, y = _x + _dx, _y + _dy
			if x < 0 or x >= m or y < 0 or y >= n:
				continue
			eliminations = _k - 1 if grid[x][y] == 1 else _k
			if (x, y, eliminations) not in visited and eliminations >= 0:
				queue.append((x, y, eliminations, _dis + 1))
				visited.add((x, y, eliminations))
	return -1

算法分析：

时间复杂度为O(nmk)，空间复杂度O(mnk), 某个cell都可能被访问k次，因为最多有k条路径

Free mock interview