KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

<pre>Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units. </pre>

Example 2:

<pre>Input: heights = [2,4] Output: 4 </pre>

Constraints:

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

</div>

题目大意：

求直方图中最大的矩形面积

解题思路：

类似于L042 Trapping Rain Water的stack法，但此题水量是反的。所以仍然用Stack，但用递增栈

解题步骤：

N/A

注意事项：

  1. 比L042稍简单，不用处理最后一个bar高度和宽度计算，但是用递增栈且公式中宽度计算仍然采用i - stack[-1] - 1，因为bar并不一定连续，如212, 最后一个2入栈，栈中剩下[_, 1]第一个2已经出栈了，但是可以有水量的。
  2. 原数组头尾加入0，头0是因为公式有stack[-1]避免越界， 尾0是因为让所有留在栈中的bar出栈且计算。

大厦题，首尾加入节点：
LeetCode 084 Largest Rectangle in Histogram LeetCode 218 The Skyline Problem

Python代码：

1
2
3
4
5
6
7
8
9
10
def largestRectangleArea(self, heights: List[int]) -> int:
	stack, res = [], 0
	heights.insert(0, 0) # remember
	heights.append(0)
	for i in range(len(heights)):
		while stack and heights[i] < heights[stack[-1]]:
			index = stack.pop()
			res = max(res, (i - stack[-1] - 1) * heights[index]) # remember i - stack[-1] - 1 not i - index
		stack.append(i)
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

</div>

题目大意：

求所有子集

解题思路：

组合知识点

解题步骤：

N/A

注意事项：

  1. 题目要求结果含空集

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def subsets(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return []
	res = [[]]
	self.dfs(nums, 0, [], res)
	return res

def dfs(self, nums, st, path, res):
	if st == len(nums):
		return
	for i in range(st, len(nums)):
		path.append(nums[i])
		res.append(list(path))
		self.dfs(nums, i + 1, path, res)
		path.pop()

算法分析：

时间复杂度为<code>O(nx2<sup>n</sup>)</code>，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode

<div>

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

<pre>Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5] </pre>

Example 2:

<pre>Input: head = [5], left = 1, right = 1 Output: [5] </pre>

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Follow up: Could you do it in one pass?</div>

题目大意：

反转链表中的子链表[left, right]，start和end是1-index位置, inclusive

解题思路：

锁定start和end节点，将end的后续节点一个个加到start直接后续

LeetCode 206 Reverse Linked List 反转整个LL LeetCode 092 Reverse Linked List II 反转部分LL，此题更加一般化

模板： 不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> ... -> end(group n+1) -> NodeA （前状态） -> ...

  1. 找出start和end，start为反转部分的前一个，end为反转部分的首个节点
  2. 循环删除end直接后，再加入到start直接后

Python代码：

1
2
3
4
5
6
start, end = fake_head, head
while <反转链表长度>:
	# delete the node
	moved_node, end.next = end.next, end.next.next
	# insert the moved_node
	start.next, moved_node.next = moved_node, start.next

解题步骤：

N/A

注意事项：

  1. 经典题，见LeetCode 2074 Reverse Nodes in Even Length Groups。 思路是锁定start和end节点，将end的后续节点一个个加到start直接后续
  2. 第二个循环中，right要记得减一，否则死循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
	left, right = left - 1, right - 1
	fake_head = ListNode(0)
	fake_head.next = head
	it = fake_head
	while left > 0:
		it = it.next
		left -= 1
		right -= 1
	start, end = it, it.next
	while right > 0:
		moved_node, end.next = end.next, end.next.next # delete a node
		start.next, moved_node.next = moved_node, start.next # insert a node
		right -= 1 # remember
	return fake_head.next

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>Input: numerator = 1, denominator = 2 Output: "0.5" </pre>

Example 2:

<pre>Input: numerator = 2, denominator = 1 Output: "2" </pre>

Example 3:

<pre>Input: numerator = 4, denominator = 333 Output: "0.(012)" </pre>

Constraints:

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

</div>

题目大意：

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)

Posted on Edited on Disqus:

LeetCode 2074 Reverse Nodes in Even Length Groups

<div>

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

  • The 1<sup>st</sup> node is assigned to the first group.
  • The 2<sup>nd</sup> and the 3<sup>rd</sup> nodes are assigned to the second group.
  • The 4<sup>th</sup>, 5<sup>th</sup>, and 6<sup>th</sup> nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Example 1:

<pre>Input: head = [5,2,6,3,9,1,7,3,8,4] Output: [5,6,2,3,9,1,4,8,3,7] Explanation:

  • The length of the first group is 1, which is odd, hence no reversal occurrs.
  • The length of the second group is 2, which is even, hence the nodes are reversed.
  • The length of the third group is 3, which is odd, hence no reversal occurrs.
  • The length of the last group is 4, which is even, hence the nodes are reversed. </pre>

Example 2:

<pre>Input: head = [1,1,0,6] Output: [1,0,1,6] Explanation:

  • The length of the first group is 1. No reversal occurrs.
  • The length of the second group is 2. The nodes are reversed.
  • The length of the last group is 1. No reversal occurrs. </pre>

Example 3:

<pre>Input: head = [2,1] Output: [2,1] Explanation:

  • The length of the first group is 1. No reversal occurrs.
  • The length of the last group is 1. No reversal occurrs. </pre>

Example 4:

<pre>Input: head = [8] Output: [8] Explanation: There is only one group whose length is 1. No reversal occurrs. </pre>

Constraints:

  • The number of nodes in the list is in the range [1, 10<sup>5</sup>].
  • 0 <= Node.val <= 10<sup>5</sup>

</div>

题目大意：

把链表分成1,2,3..n大小的组。若该组大小为偶数，反转链表。

解题思路：

一开始考虑分奇偶组来处理，但忽略了最后一组也可能为偶数。用stack来，先做统计，若为偶数，就出栈且反转。
后来为了程序更加简洁，就独立一个函数出来按组处理。而每组用迭代将后续节点一个个加到上一组末节点和首节点之间。

解题步骤：

  1. 按组处理
  2. 每组先统计个数，如果为偶数，反转链表

start(group n) -> end(group n+1, head of group n+1 will become new tail after reversed) -> ...
不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> ... -> end(group n+1) -> NodeA （前状态） -> ...

注意事项：

  1. 若最后一组不满为偶数，也要逆转。
  2. 反转链表时，个数为这组大小减一，因为该组的首节点不用反转。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
	group, cur = 2, head
	while cur.next:
		cur = self.process_one_group(cur, group)
		group += 1
	return head

def process_one_group(self, tail_of_last: ListNode, n: int) -> ListNode:
	cur, count = tail_of_last, 0
	while cur.next and count < n:
		cur = cur.next
		count += 1
	if count % 2 == 0:
		start, end = tail_of_last, tail_of_last.next
		for i in range(count - 1):
			# delete the node
			moved_node, end.next = end.next, end.next.next
			# insert the moved_node
			start.next, moved_node.next = moved_node, start.next
	cur = tail_of_last
	for i in range(count):
		cur = cur.next
	return cur

算法分析：

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

Free mock interview