KK's blog

LeetCode 493 Reverse Pairs

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Example 1:

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

Example 2:

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

Constraints:

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

题目大意：

求数组的逆序数

解题思路：

1. Merge sort模板
2. merge分两部分写，一个部分比较求个数，另一部分排序

注意事项：

1. merge分两部分写，一个部分比较，另一部分排序
2. 计算个数由两部分组成，两指针部分和剩余元素部分。若以后半数组为主，就是前半数组指针i的后面个数(程序用此)
   若以前半数组为主(加入到res时候)，就是后半数组指针j的前面个数
3. nums[start:end+1] = res，前面是nums不是res

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
41
42
43
44
45
46
47
48

def reversePairs(self, nums: List[int]):
	if not nums:
		return 0
	return self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums, start, end):
	if start >= end:
		return 0
	mid = start + (end - start) // 2
	count = 0
	count += self.m_sort(nums, start, mid)
	count += self.m_sort(nums, mid + 1, end)
	count += self.merge(nums, start, mid, end)
	return count

def merge(self, nums, start, mid, end):
	i, j, res, count = start, mid + 1, [], 0
	while i <= mid and j <= end:
		if nums[i] <= 2 * nums[j]:
			i += 1
		else:
			count += mid - i + 1
			j += 1

	while i <= mid:
		i += 1
	while j <= end:
		count += mid - i + 1
		j += 1

	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1

	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1

	nums[start:end + 1] = res
	return count

算法分析：

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

LeetCode 503 Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:

<pre><b>Input:</b> [1,2,1] <b>Output:</b> [2,-1,2] <b>Explanation:</b> The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2. </pre>

Note: The length of given array won't exceed 10000.

题目大意：

给定一个循环数组（末尾元素的下一个元素为起始元素），输出每一个元素的下一个更大的数字（Next Greater Number）。Next Greater Number是指位于某元素右侧，大于该元素，且距离最近的元素。如果不存在这样的元素，则输出-1。

注意：给定数组长度不超过10000。

解题思路：

最直接的思路是遍历每个元素，对每个元素，遍历它的后面所有元素。最差情况是递减数列，时间复杂度为<code>O(n²)</code>。
这题关于局部递增数组，所以考虑用递减栈。首先不考虑循环数组的情况，例如8,5,4,6,栈存入8,5,4，当6准备进栈时，5,4比6小，它们都出栈且它们的结果集为6。 循环数组其实只要将原数组复制一倍，按原算法处理，结果集取前n个元素即可。

1. 栈不为空，准入栈元素逼出比其小的元素且赋予其结果。
2. 该元素入栈。、
3. 栈剩下元素的结果集赋值为-1

注意事项：

1. 栈存储元素下标，结果集存储元素值。
2. 栈剩下元素的结果集赋值为-1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

def nextGreaterElements(self, nums: List[int]) -> List[int]:
	num_list = nums * 2
	result, stack = [0] * len(num_list), []
	for i in range(len(num_list)):
		while stack and num_list[i] > num_list[stack[-1]]:
			index = stack.pop()
			result[index] = num_list[i]
		stack.append(i)

	while stack:
		index = stack.pop()
		result[index] = -1
	return result[:len(nums)]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int[] nextGreaterElements(int[] nums) {
	Stack s = new Stack();
	int[] nums2 = new int[nums.length*2];
	int[] re2 = new int[nums2.length];
	for(int i=0;i<nums2.length;i++){
		nums2[i] = nums[i%nums.length];
	}
	for(int i=0;i<nums2.length;i++){
		while(!s.isEmpty() && nums2[i]>nums2[(int)s.peek()]){
			int topIdx = (int)s.pop();
			re2[topIdx] = nums2[i];
		}
		s.add(i);
	}
	while(!s.isEmpty()){
		int topIdx = (int)s.pop();
		re2[topIdx] = -1;
	}
	int[] re = new int[nums.length];
	for(int i=0;i<nums.length;i++)
		re[i] = re2[i];
	return re;
}

算法分析：

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

有人考虑用TreeMap， 2 1 3 但TreeMap不能保留顺序，如这个TreeMap可以对应两种数组,[2,1,3], [2,3,1]并非一一对应。

Follow-up:

1. Given an integer array, print the Next Greater Number for every element.先从不循环数组考起。 3,8,5,4,6,7 => 8,-1,6,6,7,-1
2. 先让其写出暴力法brute force
3. 再优化，第0个提示是考虑用一些数据结构，第一个提示为Stack。第二个提示，给定两个stack，怎么排序一个数组。如1,4,3,2. 一个stack用于维护当前递增栈，另一个用于缓冲。过程：栈1从底到顶14，3准入，因为比4小，不能维持递增顺序，4入栈2，然后3入栈1，再把栈2所有元素入栈1。同理4,3入栈2,2入栈1。
4. 最后如果是循环数组circular array，如果解决。 3,8,5,4,6,7 => 8,-1,6,6,7,8
5. 第一个层次暴力法，第二层次思路从第二个提示到联系到此题解法，Meets bar。最后能实现且解决follow-up，raise bar。

LeetCode 104 Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

<pre>Input: root = [3,9,20,null,null,15,7] Output: 3 </pre>

Example 2:

<pre>Input: root = [1,null,2] Output: 2 </pre>

Example 3:

<pre>Input: root = [] Output: 0 </pre>

Example 4:

<pre>Input: root = [0] Output: 1 </pre>

Constraints:

• The number of nodes in the tree is in the range [0, 10<sup>4</sup>].
• -100 <= Node.val <= 100

题目大意：

求二叉树高度。

解题思路：

公式dfs(root)=1+max(dfs(root.left),dfs(root.right))

Python代码：

1
2
3
4

def maxDepth(self, root: TreeNode) -> int:
	if not root:
		return 0
	return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

算法分析：

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

LeetCode 2073 Time Needed to Buy Tickets

<div>

There are n people in a line queuing to buy tickets, where the 0<sup>th</sup> person is at the front of the line and the (n - 1)<sup>th</sup> person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the i<sup>th</sup> person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k**(0-indexed) **to finish buying tickets.

Example 1:

<pre>Input: tickets = [2,3,2], k = 2 Output: 6 Explanation:

• In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
• In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0]. The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds. </pre>

Example 2:

<pre>Input: tickets = [5,1,1,1], k = 0 Output: 8 Explanation:

• In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
• In the next 4 passes, only the person in position 0 is buying tickets. The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds. </pre>

Constraints:

• n == tickets.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

</div>

题目大意：

排队买票，每个人都有不同的票数需求。每人每次只能买一张，买完后重新排队。买一张票需要1秒，求第k个人买票的总时间。

解题思路：

一开始按照题目要求老老实实每个元素减一，按照流程计算，但效率较低。考虑若所有人票数大于0，每轮计算结果是一样的：
当前排队人数乘以排队的人中的最小票数。当最小票数人离队后，公式会改变。如此循环直到第k个人票数也变成0为止。

解题步骤：

1. 求最小值
2. 计算票数
3. 更新人数，继续循环
4. 结果减去排在第k个人后的人数

注意事项：

1. 结果要减去排在第k个人后的还在排队的人数（tickets数不为负数，可以等于0，因为是同时在同一轮买到足够票）。

Python代码：

1
2
3
4
5
6
7
8
9
10

def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
	sum, ppl, min_tickets = 0, len(tickets), 0
	while tickets[k] > 0:
		min_tickets = min(t for t in tickets if t > 0)
		sum += min_tickets * ppl
		tickets = [t - min_tickets for t in tickets]
		ppl -= tickets.count(0)

	after_k = [i for i in range(k + 1, len(tickets)) if tickets[i] >= 0]
	return sum - len(after_k)

算法分析：

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

LeetCode 275 H-Index II

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i<sup>th</sup> paper and citations is sorted in an ascending order, return compute the researcher's h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index.

You must write an algorithm that runs in logarithmic time.

Example 1:

<pre>Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3. </pre>

Example 2:

<pre>Input: citations = [1,2,100] Output: 2 </pre>

Constraints:

• n == citations.length
• 1 <= n <= 10<sup>5</sup>
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

题目大意：

一个人的学术文章有n篇分别被引用了n次及以上，那么H指数就是n

解题思路：

数组有序，论文数从小到大有序(符合引用次数的论文数从右向左递减)，引用次数由小到大排序，所以只要从右向左遍历数组，数值和索引相交的值就是所求。

解题步骤：

二分法可提高效率，用的是

注意事项：

1. 此题是寻找单一目标，所以等号可以并入任一个if statement，但循环出来后，start必须先比较，因为贪婪法，下标越向左，越容易获得更大的结果。从这一意义上看，此题接近于first_position

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def hIndex(self, citations: List[int]) -> int:
	if citations is None or len(citations) == 0:
		return 0
	start, end = 0, len(citations) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if citations[mid] >= len(citations) - mid:
			end = mid
		else:
			start = mid
	if citations[start] >= len(citations) - start:
		return len(citations) - start
	if citations[end] >= len(citations) - end:
		return len(citations) - end
	return 0

算法分析：

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