KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

<pre>Input: nums = [1,2,0] Output: 3 </pre>

Example 2:

<pre>Input: nums = [3,4,-1,1] Output: 2 </pre>

Example 3:

<pre>Input: nums = [7,8,9,11,12] Output: 1 </pre>

Constraints:

  • 1 <= nums.length <= 5 * 10<sup>5</sup>
  • -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

</div>

题目大意：

找第一个缺失的正整数

解题思路：

类似于quick sort里面的partition，满足某些条件才移动指针

解题步骤：

N/A

注意事项：

  1. 第一个正确元素为1，所以预期数组为[1, 2, 3...]，从1开始并不是从0开始。
  2. 交换元素的条件：需要交换nums[i] != i + 1, 可以交换[1 <= nums[i] <= len(nums)], 不会死循环(nums[nums[i] - 1] != nums[i])
  3. 若满足条件，无限交换，直到不满足条件。不满足条件才移动遍历指针i
  4. 交换两元素涉及内嵌数组，所以不能用comment上的。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def firstMissingPositive(self, nums: List[int]) -> int:
	i = 0
	while i < len(nums):
		if nums[i] != i + 1 and 1 <= nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:
			# nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
			self.swap(nums, i, nums[i] - 1)
		else:
			i += 1
	j = 1
	while j <= len(nums):
		if j != nums[j - 1]:
			break
		j += 1
	return j

def swap(self, nums, i, j):
	nums[i], nums[j] = nums[j], nums[i]

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

  • "G": go straight 1 unit;
  • "L": turn 90 degrees to the left;
  • "R": turn 90 degrees to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

<pre>Input: instructions = "GGLLGG" Output: true Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0). When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.</pre>

Example 2:

<pre>Input: instructions = "GG" Output: false Explanation: The robot moves north indefinitely.</pre>

Example 3:

<pre>Input: instructions = "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...</pre>

Constraints:

  • 1 <= instructions.length <= 100
  • instructions[i] is 'G', 'L' or, 'R'.

</div>

题目大意：

循环按模式走是否回到原点

解题思路：

数学题，很难证明。定理是，只要按照给定模式走完，若回到原点或最后方向不是向北，都能回到原点

解题步骤：

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
def isRobotBounded(self, instructions: str) -> bool:
	DIRECTION_CONVERT_LEFT = {
		(0, 1): (-1, 0),
		(-1, 0): (0, -1),
		(0, -1): (1, 0),
		(1, 0): (0, 1),
	}
	DIRECTION_CONVERT_RIGHT = {
		(0, 1): (1, 0),
		(1, 0): (0, -1),
		(0, -1): (-1, 0),
		(-1, 0): (0, 1),
	}
	path, direction, position = instructions, (0, 1), (0, 0)
	for char in path:
		if char == 'L':
			direction = DIRECTION_CONVERT_LEFT[direction]
		elif char == 'R':
			direction = DIRECTION_CONVERT_RIGHT[direction]
		else:
			position = (position[0] + direction[0], position[1] + direction[1])
	return True if position == (0, 0) or direction != (0, 1) else False

算法分析：

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

Posted on Edited on Disqus:

LeetCode 239 Sliding Window Maximum

<div>

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:

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

Example 2:

<pre>Input: nums = [1], k = 1 Output: [1] </pre>

Constraints:

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

</div>

算法思路：

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

注意事项：

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

Python代码：

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

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

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

Example 1:

<pre>Input: n = 5 Output: 2 Explanation: 5 = 2 + 3 </pre>

Example 2:

<pre>Input: n = 9 Output: 3 Explanation: 9 = 4 + 5 = 2 + 3 + 4 </pre>

Example 3:

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

Constraints:

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

</div>

题目大意：

求连续整数的和等于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

<div>

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:

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

Example 2:

<pre>Input: nums = [2,3,0,1,4] Output: 2 </pre>

Constraints:

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

</div>

题目大意：

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)

Free mock interview