KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Example 1:

Input: nums = [1,2,3]
Output: 6


Example 2:

Input: nums = [1,2,3,4]
Output: 24


Example 3:

Input: nums = [-1,-2,-3]
Output: -6


Constraints:

3 <= nums.length <= 10<sup>4</sup> -1000 <= nums[i] <= 1000

题目大意：

求数组任意三个数的最大乘积

排序法解题思路：

数学题，正负数分开，最大只可以是排序后最大的三个数(全正，全负)或最大整数乘以最小两个负数(正负均有)

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    def maximumProduct(self, nums: List[int]) -> int:
    	nums.sort()
    	return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])

算法分析：

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

Heap算法II解题思路：

由上述思路进一步优化，不需要全部排序，只需要知道最大的3个数和最小的两个数即可

Python代码：

1
2
3
4
def maximumProduct2(self, nums: List[int]) -> int:
	largest = heapq.nlargest(3, nums)
	smallest = heapq.nsmallest(2, nums)
	return max(largest[0] * largest[1] * largest[2], largest[0] * smallest[0] * smallest[1])

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.


Example 2:

Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.


Example 3:

Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints: 1 <= text1.length, text2.length <= 1000
* text1 and text2 consist of only lowercase English characters.

题目大意：

求两字符串的最大公共字符序列，不一定需要连续

解题思路：

两字符串最值问题用DP
dp[i][j]为最大公共字符序列，最后一位不需要相等。递归式为:

1
2
dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
         = max(dp[i - 1][j], dp[i][j - 1])

解题步骤：

DP五点注意事项

注意事项：

  1. 不相等时候不需要dp[i - 1][j - 1]，因为已经包含在dp[i - 1][j]或dp[i][j - 1]中, DP属于累计DP

Python代码：

1
2
3
4
5
6
7
8
9
10
11
# dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
#          = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # no dp[i - 1][j - 1] but no impact
	return dp[-1][-1]

打印路径

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
longest, res = dp[-1][-1], ''
while m >= 0 and n >= 0:
	if dp[m - 1][n] == longest:
		m -= 1
	elif dp[m][n - 1] == longest:
		n -= 1
	else:
		res += text1[m - 1]
		longest -= 1
		m -= 1
		n -= 1
return res[::-1]

算法分析：

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

Posted on Disqus:

LeetCode



You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A<sub>i</sub>, B<sub>i</sub>] and values[i] represent the equation A<sub>i</sub> / B<sub>i</sub> = values[i]. Each A<sub>i</sub> or B<sub>i</sub> is a string that represents a single variable.

You are also given some queries, where queries[j] = [C<sub>j</sub>, D<sub>j</sub>] represents the j<sup>th</sup> query where you must find the answer for C<sub>j</sub> / D<sub>j</sub> = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

Input: equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]


Example 2:

Input: equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
Output: [3.75000,0.40000,5.00000,0.20000]


Example 3:

Input: equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
Output: [0.50000,2.00000,-1.00000,-1.00000]


Constraints:

1 <= equations.length <= 20 equations[i].length == 2
1 <= A<sub>i</sub>.length, B<sub>i</sub>.length <= 5 values.length == equations.length
0.0 < values[i] <= 20.0 1 <= queries.length <= 20
queries[i].length == 2 1 <= C<sub>j</sub>.length, D<sub>j</sub>.length <= 5
* A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub> consist of lower case English letters and digits.

题目大意：

根据已知除法结果求其他除法表达式

解题思路：

这是G家的面试题。图问题，因为每个除法式相乘可以得到query所要的，所以属于图问题。可以用BFS来遍历图，如已知a/b = 2, b/c = 3, 需要知道a/c, 就是2 x 3，所以只要从a开始， c为BFS的target，迭代时不断相乘

解题步骤：

N/A

注意事项：

  1. 核心思想： BFS来遍历图，迭代时不断相乘。无向图，因为a/c也可以c/a.
  2. BFS的注意事项后两个：BFS无解时候不存在的时候返回-1
  3. 两种edge cases： 若query中任意元素不在图中，返回-1(题目要求), 若元素相等，返回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
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
	graph = collections.defaultdict(list)
	for i, li in enumerate(equations):
		graph[li[0]].append((li[1], values[i]))
		graph[li[1]].append((li[0], 1 / values[i])) # remember it is an undirected graph
	res = []
	for query in queries:
		if query[0] not in graph or query[1] not in graph:
			res.append(-1.0)
		elif query[0] in graph and query[0] == query[1]:
			res.append(1.0)
		else:
			val = self.bfs(graph, query)
			res.append(val)
	return res

def bfs(self, graph, query):
	queue = collections.deque([(query[0], 1)])
	visited = set([queue[0]])
	while queue:
		node, parent_val = queue.popleft()
		if node == query[1]:
			return parent_val
		for neighbor, val in graph[node]:
			if neighbor in visited:
				continue
			queue.append((neighbor, parent_val * val))
			visited.add(neighbor)
	return -1 # remember

算法分析：

时间复杂度为O(（V + E) * m)，空间复杂度O(E), m为query数

Posted on Disqus:

LeetCode



Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums. int[] reset() Resets the array to its original configuration and returns it.
int[] shuffle() Returns a random shuffling of the array.

Example 1:

Input
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]



Constraints: 1 <= nums.length <= 200
-10<sup>6</sup> <= nums[i] <= 10<sup>6</sup> All the elements of nums are unique.
At most `5 104calls **in total** will be made toresetandshuffle`.

题目大意：

随机重排数组

解题思路：

水塘抽样法

先看算法，再理解，第i个元素会被交换的概率：
某一个元素保留概率为(n - i) / (n - i + 1)
某一个元素交换概率为1 / (n - i)
所以从左到右遍历到第i个元素时，它被交换到后面的概率为 所有前面都保留 乘以 第i轮循环时被交换：

1
(n - 1) / n * (n - 2) / (n - 1) ... (n - i) / (n - i + 1) * 1 / (n - i)

前面都约了，最后等于1 / n

解题步骤：

N/A

注意事项：

  1. 死记算法，跟后面的元素互换
  2. 复制原数组以防被改

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def __init__(self, nums: List[int]):
	self.original = list(nums)
	self.nums = nums

def reset(self) -> List[int]:
	return list(self.original)

def shuffle(self) -> List[int]:
	for i in range(len(self.nums)):
		swap_idx = random.randrange(i, len(self.nums))
		self.nums[i], self.nums[swap_idx] = self.nums[swap_idx], self.nums[i]
	return self.nums

算法分析：

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

Posted on Disqus:

LeetCode



You are given an integer length and an array updates where updates[i] = [startIdx<sub>i</sub>, endIdx<sub>i</sub>, inc<sub>i</sub>].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the i<sup>th</sup> operation, you should increment all the elements arr[startIdx<sub>i</sub>], arr[startIdx<sub>i</sub> + 1], ..., arr[endIdx<sub>i</sub>] by inc<sub>i</sub>.

Return arr after applying all the updates.

Example 1:



Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]


Example 2:

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4]


Constraints:

1 <= length <= 10<sup>5</sup> 0 <= updates.length <= 10<sup>4</sup>
0 <= startIdx<sub>i</sub> <= endIdx<sub>i</sub> < length -1000 <= inc<sub>i</sub> <= 1000

题目大意：

统一加一个数到子数组中，如此有好几个操作，求最后数组结果

解题思路：

差分数组，数加到首节点，数减在末节点 + 1，最后累加

解题步骤：

N/A

注意事项：

  1. 数加到首节点，数减在末节点 + 1，最后累加
  2. 端点需要累加res[li[0]] += li[2], 而不是res[li[0]] = li[2]
  3. len(res)而不是len(li)

Python代码：

1
2
3
4
5
6
7
8
9
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
	res = [0] * length
	for li in updates:
		res[li[0]] += li[2] # remember += not =
		if li[1] + 1 < len(res): # remember not len(li)
			res[li[1] + 1] += -li[2] # remember += not =
	for i in range(1, len(res)):
		res[i] += res[i - 1]
	return res

算法分析：

时间复杂度为O(n + m)，空间复杂度O(1), n, m分别为数组长度和update个数

Free mock interview