KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 239 Sliding Window Maximum



You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position                Max
—————               —–
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7


Example 2:

Input: nums = [1], k = 1
Output: [1]


Constraints:

1 <= nums.length <= 10<sup>5</sup> -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
* 1 <= k <= nums.length

算法思路：

LL(queue) + 递减栈
难点是什么时候输出结果，并不是出栈时候，而是每轮遍历时，就可以计算当轮的最大值，也就是当前的队首。此题也可以用heap，实现几乎一样，但时间复杂度是nlogn

注意事项：

  1. 每轮遍历时，计算当轮的最大值就是当前的队首
  2. 注意程序顺序，先递减栈模板，在计算结果，最后移出越界元素。如例子[876], i = 2, 窗口大小满足了，计算结果为8,8在下一轮会越界，所以移除。
  3. 结果数小于数组大小，注意line 8的条件

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	queue, res = collections.deque(), []
	for i in range(len(nums)):
		while queue and nums[i] > nums[queue[-1]]:
			queue.pop()
		queue.append(i)

		if i + 1 >= k:
			res.append(nums[queue[0]])
		if i - queue[0] + 1 >= k:
			queue.popleft()
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 = 2 + 3


Example 2:

Input: n = 9
Output: 3
Explanation: 9 = 4 + 5 = 2 + 3 + 4


Example 3:

Input: n = 15
Output: 4
Explanation: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5


Constraints:

* 1 <= n <= 10<sup>9</sup>

题目大意：

求连续整数的和等于N的个数

解题思路：

只有Fintech考，数学题。思路见注释

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
# x, x+1, ... , x+k-1
# (x + x+k-1) * k / 2 = 2x+k-1) = n, x = [n - k(k-1)/2]/k
def consecutiveNumbersSum(self, n: int) -> int:
	res = 1
	for i in range(2, int(math.sqrt(2 * n) + 1)):
		if (n - i * (i - 1) / 2) % i == 0:
			res += 1
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.


Example 2:

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


Constraints:

1 <= nums.length <= 10<sup>4</sup> 0 <= nums[i] <= 1000

题目大意：

N/A

解题思路：

BFS，但不需要用queue

解题步骤：

N/A

注意事项：

  1. end, next_end分别表示该层和下一层的边界，end从0开始，表示第0个数是第一层，遍历每个数，从0开始。
  2. 这个边界是inclusive的，所以当i==end时候，不应该res加1，是下一轮循环才是下一层的开始。有两种实现，我的实现是第一种，标准答案是遍历到最后一个数的前一个，因为最后一个数已经是目标，所以不需要计算next_end，更不需要层数+1。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def jump2(self, nums: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	update_end = False
	for i in range(len(nums)):
		if update_end:
			res += 1
			update_end = False
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
			update_end = True
	return res

Python代码：

1
2
3
4
5
6
7
8
9
def jump(self, nums: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	for i in range(len(nums) - 1):
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
			res += 1
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.


Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.


Constraints:

1 <= nums.length <= 10<sup>4</sup> 0 <= nums[i] <= 10<sup>5</sup>

题目大意：

N/A

解题思路：

BFS，但不需要用queue

解题步骤：

N/A

注意事项：

  1. 参考Jump game II，区别在于如果i <= end才更新，
  2. 返回next_end要大于等于(可以cover)最后一个元素下标

Python代码：

1
2
3
4
5
6
7
8
def canJump(self, nums: List[int]) -> bool:
	end, next_end = 0, 0
	for i in range(len(nums) - 1):
		if i <= end:
			next_end = max(next_end, i + nums[i]) # 4
		if i == end: #
			end = next_end # 8
	return next_end >= len(nums) - 1

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:



Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]


Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.


Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3


Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2


Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1


Constraints:

1 <= n <= 10<sup>4</sup> ranges.length == n + 1
* 0 <= ranges[i] <= 100

题目大意：

用多少个水龙头覆盖整个花园

解题思路：

两个难点，此题类似于jump game，这一层某个水龙头浇到最远点的水龙头也就是这一层的水龙头，这是难点一。
难点二是跟jump game不同，这题可以往前跳，也就是如例子中，点2表示从1跳到3，因为它的范围是1. 所以要重新计算每个水龙头的起点=它的左半范围起点

解题步骤：

N/A

注意事项：

  1. 第一步转化成jump game，jump game每个数值都是长度。若左半范围起点小于等于0，所有这些水龙头归结到起点0，长度为i + ranges[i], 其余情况是ranges[i] * 2
  2. 完全用jump game的程序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def minTaps(self, n: int, ranges: List[int]) -> int:
	end, next_end, res = 0, 0, 0
	nums = [0] * len(ranges)
	for i in range(len(ranges)):
		if i - ranges[i] <= 0:
			nums[0] = max(nums[0], ranges[i] + i)
		else:
			nums[i - ranges[i]] = max(nums[i - ranges[i]], ranges[i] * 2)

	for i in range(len(nums) - 1): # remember
		if i <= end:  # -3 <= 0
			next_end = max(next_end, i + nums[i])  # 3
		if i == end:
			end = next_end
			res += 1
	return res if next_end >= len(nums) - 1 else -1

算法分析：

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

Free mock interview