KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5


Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4


Constraints:

n == arr.length 1 <= n <= 10<sup>5</sup>
* 1 <= arr[i] <= 10<sup>5</sup>

题目大意：

求相同元素的下标差的和

解题思路：

暴力法是TLE，由于存在重复计算。用prefix和suffix来优化。
prefix为从某个元素为起点到前继节点下标差之和
suffix为从某个元素为起点到后继节点下标差之和
结果 = prefix[i] + suffix[i]

解题步骤：

  1. 用Map来存储相同元素的下标
  2. 用prefix和suffix来计算每个元素的结果

注意事项：

  1. 一开始用presum表示从起点到其他下标的差之和。这不能用于某个元素的前继元素下标差之和。所以要改成从某个元素为起点到前继节点下标差之和

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getDistances(self, arr: List[int]) -> List[int]:
	val_to_index = collections.defaultdict(list)
	res = [0] * len(arr)
	for i in range(len(arr)):
		val_to_index[arr[i]].append(i)
	for val, indices in val_to_index.items():
		prefix, suffix = [0], [0]
		for i in range(1, len(indices)):
			prefix.append(prefix[-1] + i * abs(indices[i] - indices[i - 1]))
		for i in range(len(indices) - 2, -1, -1):
			suffix.append(suffix[-1] + (len(indices) - i - 1) * abs(indices[i] - indices[i + 1]))
		for i in range(len(indices)):
			res[indices[i]] = prefix[i] + suffix[len(indices) - i - 1]
	return res

算法分析：

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

Posted on Disqus:

LeetCode



Let’s play the minesweeper game (Wikipedia), online game)!

You are given an m x n char matrix board representing the game board where:

'M' represents an unrevealed mine, 'E' represents an unrevealed empty square,
'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals), digit ('1' to '8') represents how many mines are adjacent to this revealed square, and
'X' represents a revealed mine.

You are also given an integer array click where click = [click<sub>r</sub>, click<sub>c</sub>] represents the next click position among all the unrevealed squares ('M' or 'E').

Return the board after revealing this position according to the following rules:

1. If a mine 'M' is revealed, then the game is over. You should change it to 'X'.
2. If an empty square 'E' with no adjacent mines is revealed, then change it to a revealed blank 'B' and all of its adjacent unrevealed squares should be revealed recursively.
3. If an empty square 'E' with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
4. Return the board when no more squares will be revealed.

Example 1:



Input: board = [[“E”,”E”,”E”,”E”,”E”],[“E”,”E”,”M”,”E”,”E”],[“E”,”E”,”E”,”E”,”E”],[“E”,”E”,”E”,”E”,”E”]], click = [3,0]
Output: [[“B”,”1”,”E”,”1”,”B”],[“B”,”1”,”M”,”1”,”B”],[“B”,”1”,”1”,”1”,”B”],[“B”,”B”,”B”,”B”,”B”]]


Example 2:



Input: board = [[“B”,”1”,”E”,”1”,”B”],[“B”,”1”,”M”,”1”,”B”],[“B”,”1”,”1”,”1”,”B”],[“B”,”B”,”B”,”B”,”B”]], click = [1,2]
Output: [[“B”,”1”,”E”,”1”,”B”],[“B”,”1”,”X”,”1”,”B”],[“B”,”1”,”1”,”1”,”B”],[“B”,”B”,”B”,”B”,”B”]]


Constraints: m == board.length
n == board[i].length 1 <= m, n <= 50
board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'. click.length == 2
0 <= click<sub>r</sub> < m 0 <= click<sub>c</sub> < n
* board[click<sub>r</sub>][click<sub>c</sub>] is either 'M' or 'E'.

题目大意：

给定扫雷版上的某一个状态，计算扫雷版上的下一个状态

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 三种情况： 1. 踩雷，只需更改此格。 2. 踩到数字格也就是雷相邻的格，计算此格的临近雷数，更改此格。 3. 从此格开始BFS访问全版，节点出列后如果是数字格不加入到queue中，否则继续BFS访问，更改此格。
  2. x, y = node[0] + _dx, node[1] + _dy用node[0], node[1]不要用i, j

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
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

	if board[click[0]][click[1]] == 'M':
		board[click[0]][click[1]] = 'X'
		return board
	else:
		mine_num = self.get_neighboring_mine_num(board, click[0], click[1])
		if mine_num > 0:
			board[click[0]][click[1]] = str(mine_num)
			return board
		else:
			return self.bfs(board, click[0], click[1])

def bfs(self, board, i, j):
	queue = collections.deque([(i, j)])
	visited = set([(i, j)])
	while queue:
		node = queue.popleft()
		mine_num = self.get_neighboring_mine_num(board, node[0], node[1])
		if mine_num > 0:
			board[node[0]][node[1]] = str(mine_num)
			continue
		else:
			board[node[0]][node[1]] = 'B'
		for _dx, _dy in OFFSETS:
			x, y = node[0] + _dx, node[1] + _dy # remember not to use i, j
			if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or (x, y) in visited:
				continue
			queue.append((x, y))
			visited.add((x, y))
	return board

def get_neighboring_mine_num(self, board, i, j):
	num = 0
	for _dx, _dy in OFFSETS:
		x, y = i + _dx, j + _dy
		if 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] == 'M':
			num += 1
	return num

算法分析：

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

Posted on Disqus:

LeetCode



Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure. void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Example 1:

Input
[“TimeMap”, “set”, “get”, “get”, “set”, “get”, “get”]
[[], [“foo”, “bar”, 1], [“foo”, 1], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 4], [“foo”, 5]]
Output
[null, null, “bar”, “bar”, null, “bar2”, “bar2”]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set(“foo”, “bar”, 1);  // store the key “foo” and value “bar” along with timestamp = 1.
timeMap.get(“foo”, 1);         // return “bar”
timeMap.get(“foo”, 3);         // return “bar”, since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is “bar”.
timeMap.set(“foo”, “bar2”, 4); // store the key “foo” and value “bar2” along with timestamp = 4.
timeMap.get(“foo”, 4);         // return “bar2”
timeMap.get(“foo”, 5);         // return “bar2”


Constraints: 1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits. 1 <= timestamp <= 10<sup>7</sup>
All the timestamps timestamp of set are strictly increasing. At most 2 * 10<sup>5</sup> calls will be made to set and get.

题目大意：

实现带历史记录的HashMap。也就是同一个key记录所有赋过值的value

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. Map to list的思路，list含两个，包括value和timestamp，用binary search搜索timestamp的下标，然后返回对应的value

Python代码：

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

    def __init__(self):
        self.key_to_val = collections.defaultdict(list)
        self.key_to_timestamp = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.key_to_val[key].append(value)
        self.key_to_timestamp[key].append(timestamp)

    def get(self, key: str, timestamp: int) -> str:
        index = bisect.bisect(self.key_to_timestamp[key], timestamp) - 1
        if index == -1:
            return ''
        else:
            return self.key_to_val[key][index]

算法分析：

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

Posted on Disqus:

LeetCode



You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

Letter-logs: All words (except the identifier) consist of lowercase English letters. Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The digit-logs maintain their relative ordering.

Return the final order of the logs.

Example 1:

Input: logs = [“dig1 8 1 5 1”,”let1 art can”,”dig2 3 6”,”let2 own kit dig”,”let3 art zero”]
Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]
Explanation:
The letter-log contents are all different, so their ordering is “art can”, “art zero”, “own kit dig”.
The digit-logs have a relative order of “dig1 8 1 5 1”, “dig2 3 6”.


Example 2:

Input: logs = [“a1 9 2 3 1”,”g1 act car”,”zo4 4 7”,”ab1 off key dog”,”a8 act zoo”]
Output: [“g1 act car”,”a8 act zoo”,”ab1 off key dog”,”a1 9 2 3 1”,”zo4 4 7”]


Constraints:

1 <= logs.length <= 100 3 <= logs[i].length <= 100
All the tokens of logs[i] are separated by a single space. logs[i] is guaranteed to have an identifier and at least one word after the identifier.

题目大意：

排序log file，以下顺序：字母log (内容，id), 数字log

解题思路(推荐)：

N/A

解题步骤：

N/A

注意事项：

  1. 排序的multi key实现(0, content_str, li[0]) if is_alpha else (1, ). (1, )表示按数组顺序

Python代码：

1
2
3
4
5
6
7
8
9
def reorderLogFiles(self, logs: List[str]) -> List[str]:

	def get_key(x):
		li = x.split(' ')
		content_str = ' '.join(li[1:])
		is_alpha = 1 if content_str[0].isalpha() else 0
		return (0, content_str, li[0]) if is_alpha else (1, )

	return sorted(logs, key=get_key)

算法分析：

时间复杂度为O(nmlogn)，空间复杂度O(mn), n为log数量，m为每个log的最长长度。如mergesort中merge复杂度为nm, 每个key比较是O(m)复杂度

算法II解题思路：

我的解法。本质上和上法一致，较繁琐

注意事项：

  1. 字母log排序不能按content_str + ‘ ‘ + li[0], 而是(content_str, li[0])作多key排序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def reorderLogFiles2(self, logs: List[str]) -> List[str]:
	letter_logs, digit_logs = [], []
	for i in range(len(logs)):
		if logs[i][-1].isdigit():
			digit_logs.append(logs[i])
		else:
			li = logs[i].split(' ')
			content_str = ' '.join(li[1:])
			letter_logs.append((content_str, li[0], i))
	letter_logs.sort()
	res = [logs[pair[2]] for pair in letter_logs]
	res += digit_logs
	return res

Posted on Edited on Disqus:

LeetCode



You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse”
Output: [
[“mobile”,”moneypot”,”monitor”],
[“mobile”,”moneypot”,”monitor”],
[“mouse”,”mousepad”],
[“mouse”,”mousepad”],
[“mouse”,”mousepad”]
]
Explanation: products sorted lexicographically = [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”]
After typing m and mo all products match and we show user [“mobile”,”moneypot”,”monitor”]
After typing mou, mous and mouse the system suggests [“mouse”,”mousepad”]


Example 2:

Input: products = [“havana”], searchWord = “havana”
Output: [[“havana”],[“havana”],[“havana”],[“havana”],[“havana”],[“havana”]]


Example 3:

Input: products = [“bags”,”baggage”,”banner”,”box”,”cloths”], searchWord = “bags”
Output: [[“baggage”,”bags”,”banner”],[“baggage”,”bags”,”banner”],[“baggage”,”bags”],[“bags”]]


Constraints:

1 <= products.length <= 1000 1 <= products[i].length <= 3000
`1 <= sum(products[i].length) <= 2 104* All the strings ofproductsare **unique**. *products[i]consists of lowercase English letters. *1 <= searchWord.length <= 1000*searchWord` consists of lowercase English letters.

题目大意：

实现搜索结果为3个autocomplete的功能

Prefix解题思路(推荐)：

Prefix

解题步骤：

N/A

注意事项：

  1. 用Trie，另一种思路是用prefix，此法采用prefix法，将所有单词按前缀加入到字典中

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
	products.sort()
	prefix_dict = collections.defaultdict(list)
	for word in products:
		for i in range(len(word)):
			prefix = word[:i + 1]
			if len(prefix_dict[prefix]) < 3:
				prefix_dict[prefix].append(word)
	res = []
	for i in range(len(searchWord)):
		prefix = searchWord[:i + 1]
		res.append(prefix_dict[prefix])
	return res

算法分析：

时间复杂度为O(nL1 + L2)，空间复杂度O(nL1), L1为单词列表中最长的长度，L2为搜索单词长度，n为单词个数

Trie + DFS算法II解题思路：

建Trie，然后根据搜索的前缀定位到Trie节点，然后对此节点做DFS找到3个单词，因为DFS和字母顺序是一致的，所以DFS可行
具体参考Leetcode solution

Two pointers算法III解题思路：

先排序，用双指针相向搜索，根据搜索单词的每一个字母，不断收缩搜索范围，左指针和右指针之间即为满足条件的结果。每轮将左指针往后三个结果加到结果集
具体参考Leetcode discussion

Free mock interview