KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


Example 2:

Input: nums = [0,0,0], target = 1
Output: 0


Constraints:

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

题目大意：

三数和最接近target

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 此题不需去重，若等于target可直接返回

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def threeSumClosest(self, nums: List[int], target: int) -> int:
	nums.sort()
	res = float('inf')
	for i in range(len(nums)):
		left, right = i + 1, len(nums) - 1
		while left < right:
			temp = nums[i] + nums[left] + nums[right]
			if abs(temp - target) < abs(res - target):
				res = temp
			if temp < target:
				left += 1
			elif temp > target:
				right -= 1
			else:
				return target
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.


Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].


Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.


Constraints:

nums1.length == m + n nums2.length == n
0 <= m, n <= 200 1 <= m + n <= 200
-10<sup>9</sup> <= nums1[i], nums2[j] <= 10<sup>9</sup>

*Follow up: Can you come up with an algorithm that runs in O(m + n) time?

题目大意：

合并两有序数组，最后结果储存在第一个数组

解题思路：

从后往前合并

解题步骤：

N/A

注意事项：

  1. i从m - 1而不是len(nums1) - 1开始，m和n是数组实际长度。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
	i, j, k = m - 1, n - 1, len(nums1) - 1
	while i >= 0 and j >= 0:
		if nums1[i] > nums2[j]:
			nums1[k] = nums1[i]
			k -= 1
			i -= 1
		else:
			nums1[k] = nums2[j]
			k -= 1
			j -= 1
	while i >= 0:
		nums1[k] = nums1[i]
		k -= 1
		i -= 1
	while j >= 0:
		nums1[k] = nums2[j]
		k -= 1
		j -= 1

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]


Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]


Example 3:

Input: nums = [], target = 0
Output: [-1,-1]


Constraints:

0 <= nums.length <= 10<sup>5</sup> -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
nums is a non-decreasing array. -10<sup>9</sup> <= target <= 10<sup>9</sup>

题目大意：

求有序数列中元素等于target的第一个和最后一个下标

解题思路：

用模板

解题步骤：

N/A

注意事项：

  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
30
31
32
33
34
35
36
37
38
39
40
def searchRange(self, nums: List[int], target: int) -> List[int]:
	first = self.first_position(nums, target)
	last = self.last_position(nums, target)
	return [first, last]

def last_position(self, nums, target):
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			start = mid
	if nums[end] == target:
		return end
	if nums[start] == target:
		return start
	return -1

def first_position(self, nums, target):
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start+ (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			end = mid
	if nums[start] == target:
		return start
	if nums[end] == target:
		return end
	return -1

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>] indicates that there is a flight from city from<sub>i</sub> to city to<sub>i</sub> with cost price<sub>i</sub>.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return-1.

Example 1:



Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.


Example 2:



Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.


Constraints:

1 <= n <= 100 0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3 0 <= from<sub>i</sub>, to<sub>i</sub> < n
from<sub>i</sub> != to<sub>i</sub> 1 <= price<sub>i</sub> <= 10<sup>4</sup>
There will not be any multiple flights between two cities. 0 <= src, dst, k < n
* src != dst

题目大意：

求只允许停k个站情况下，最便宜机票价格

解题思路：

BFS + Heap
这是单源最短路径的典型应用。可以用Dijkstra，机票价格相当于单源最短路径问题中的路径大小。一开始我用BFS，但得到TLE，因为存在循环，导致节点被重复访问(同一路径)。但一个节点的确可以被用不同路径访问。所以引入visited[node] = dis

解题步骤：

N/A

注意事项：

  1. node需要被多次访问，所以跟模板不同，visited的检测要放在neighbor循环之外且用node且初始化为空。visited不再是set，它需要记录node离src的距离。一方面用于循环检测，因为如果存在循环，会出现dist >= visited[node]。若该节点的当前距离小于之前的最小距离，此时也要加入到heap，因为贪婪法，虽然此路径费用较高，但它距离更近，当k限制比较小时，此路径可能满足要求。这就是为什么一个节点会被多次访问的原因。
  2. 若路径不存在返回-1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
	graph = collections.defaultdict(list)
	for pair in flights:
		graph[pair[0]].append((pair[1], pair[2]))
    heap = ([(0, src, 0)]) # price, node_id, distance
	visited = {}
	while heap:
		p, node, dist = heapq.heappop(heap)
		if node == dst and dist <= k + 1:
			return p
		if node in visited and dist >= visited[node]:
			continue
		visited[node] = dist
		for neighbor, _price in graph[node]:
			heapq.heappush(heap, (p + _price, neighbor, dist + 1))
	return -1

算法分析：

时间复杂度为O(VlogV)，空间复杂度O(V)

Posted on Edited on Disqus:

LeetCode



Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10<sup>4</sup> for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”


Example 2:

Input: numerator = 2, denominator = 1
Output: “2”


Example 3:

Input: numerator = 4, denominator = 333
Output: “0.(012)”


Constraints:

-2<sup>31</sup> <= numerator, denominator <= 2<sup>31</sup> - 1 denominator != 0

题目大意：

N/A

解题思路：

小学定理为若余数重复则前重复对应的结果到目前位置的前一位为循环体

解题步骤：

N/A

注意事项：

  1. 小学定理为若余数重复则前重复对应的结果到目前位置的前一位为循环体，并不是digit一样，而是余数。类似于L003 Longest Substring Without Repeating Characters，记录余数到商下标。循环中顺序很重要，与长除法一致(上图)。分子为remainder，查看remainder是否重复，若否，加入到map，乘以10，求商和新余数，进入下一轮迭代。
  2. 输入均为负数或其一为负数的情况，计算结果符号，分子分母分别转成正数
  3. 分子大于分母或分子小于分母的情况都归结为用分子除以分母，加入到结果，若有余数，再加小数点

Line 26 - 27与Line 16 - 17一致

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 fractionToDecimal(self, numerator: int, denominator: int) -> str:
	res, remainder_to_pos = '', collections.defaultdict(int)
	is_negative, remainder = 1, 0
	if numerator / denominator < 0:
		is_negative = -1
	numerator = abs(numerator)
	denominator = abs(denominator)
	'''
	if numerator < denominator:
		res = '0.'
		remainder = numerator
	else:
		res = str(numerator // denominator)
		remainder = numerator % denominator
	'''
	res = str(numerator // denominator)
	remainder = numerator % denominator
	if remainder > 0:
		res += '.'
	while remainder > 0:
		if remainder in remainder_to_pos:
			res = res[:remainder_to_pos[remainder]] + '(' + res[remainder_to_pos[remainder]:] + ')'
			break
		remainder_to_pos[remainder] = len(res)  # remember
		remainder *= 10 # remember not numerator * 10 // denominator
		res += str(remainder // denominator)
		remainder %= denominator
	return res if is_negative == 1 else '-' + res

算法分析：

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

Free mock interview