KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.


Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].


Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].


Constraints:

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

题目大意：

给定一个数组，找一个3个数的序列，满足后两个数交换后是有序的。

解题思路：

此题较难理解，首先要拆分为三个条件：中间的数大于两边的，左边的数小于右边的
num[i] < num[j]
num[k] < num[j]
num[i] < num[k]
这3个条件要贯彻在代码中

第一方法：暴力法是三重循环遍历i, j, k满足上述三个条件，复杂度为O(n^3)
第二方法：贪婪法。这题是寻找有或者无，所以不需要直到具体答案而且i对应的数值越小越好容易找到答案，因为这样nums[i], nums[j]之间的区间越大，越容易找到k。我们把nums[i]变成min_i, 这样遍历j的时候，顺便可以求min_i同时保证j和k的值都大于min_i，减少了一轮循环复杂度为O(n^2)
第三方法：递减栈。由第二方法，我们可以把min_i值都存起来，这是一个mins[i]为以i为结尾的子数组的最小值，很容易满足num[i] < num[k]和num[i] < num[j]。难点在要找一个比nums[j]小的数就满足num[k] < num[j]，容易想到LeetCode 503 Next Greater Element II里面的递减栈，不过那题是求下一个比自己大的数，所以要反着做，从数组从后向前遍历。

解题步骤：

  1. Populate mins数组
  2. 递减栈的实现分别要满足上述三个条件。mins[j], num[j], stack[-1]分别代表i，j和k

注意事项：

  1. 输入只有一个数的时候

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def find132pattern(self, nums: List[int]) -> bool:
	mins = [nums[0]]
	for i in range(1, len(nums)):
		mins.append(min(nums[i], mins[i-1]))
	stack = []
	for j in range(len(nums) - 1, -1, -1):
		if nums[j] <= mins[j]: # num[i] < num[j]
			continue
		while stack and stack[-1] <= mins[j]: # num[i] < num[k] 
			stack.pop()
		if stack and stack[-1] < nums[j]: # num[k] < num[j] 
			return True
		stack.append(nums[j])
	return False

算法分析：

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

Posted on Disqus:

LeetCode



You are given n​​​​​​ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime<sub>i</sub>, processingTime<sub>i</sub>] means that the i<sup>​​​​​​th</sup>​​​​ task will be available to process at enqueueTime<sub>i</sub> and will take processingTime<sub>i</sub>to finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle. If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping. The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows:
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.


Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation**: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.
Constraints:*​​​​​​​ 1 <= tasks.length <= 10<sup>5</sup>
tasks[i] = [enqueueTime<sub>i</sub>, processingTime<sub>i</sub>] 1 <= enqueueTime<sub>i</sub>, processingTime<sub>i</sub> <= 10<sup>9</sup>

题目大意：

一个CPU按一定顺序单线程处理多个当前准备好的任务。准备好的任务排序是按处理时间为先，然后是下标。

解题思路：

这题跟L253 Meeting Rooms II类似也是关于重合区间的问题

  1. 先对开始时间进行排序
  2. 对endtime进行heap排序，用start跟堆顶比较
    但区别是endtime不是预先知道的，是根据前面任务完成时间而动态计算。所以heap应该严格根据题目要求，存储处理时间和任务下标。
    入堆条件为新任务开始时间 <= 当前任务的结束时间
    这里注意有两种情况需要考虑：
  3. 区间重合
  4. 区间不重合 （容易忽略）
    Current_time的引入=连续区间的开始时间(不重合的区间)或结束时间(存在重合的区间不会记录开始时间到这个变量)。

解题步骤：

  1. 任务按开始时间排序
  2. 建堆，堆元素是(processing time, task index)
  3. 入堆条件是遍历后序任务，若新任务开始时间 <= 当前任务的结束时间，才入堆
  4. 出堆得到任务下标，加入到结果序列

注意事项：

  1. 任务排序时候，记得加入index以及之后都要用此变量，不能用原输入变量
  2. 严格按照条件：堆元素为存储处理时间和任务下标，不能用Endtime
  3. 两个不同情况：区间重合或不重合，写程序要重点考虑。
  4. 程序可以优化：heappush的3个逻辑是重复的，合并为一个，current_time可以为开始时间，这样就可以把多个同一个开始时间的tasks一起加入到堆
  5. if not heap, 计算current_time也是两情况，若两区间重合情况，current_time是第一个出堆时区间结束时间，它大于第二区间的开始时间，时间不能回拨，所以取max。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def getOrder(self, tasks: List[List[int]]) -> List[int]:
	sorted_tasks = [(tasks[i][0], tasks[i][1], i) for i in range(len(tasks))]
	sorted_tasks.sort()
	heap, res = [], []
	current_time = sorted_tasks[0][0]
	i = 0
	while heap or i < len(sorted_tasks):
		if not heap:
			current_time = max(current_time, sorted_tasks[i][0])
		while i < len(sorted_tasks) and sorted_tasks[i][0] <= current_time: # start time <= current task's finished time, task[0]-> current_time 
			heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2])) 
			i += 1

		task = heapq.heappop(heap)
		current_time += task[0]
		res.append(task[1]) # finished processing

算法分析：

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

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
def getOrder(self, tasks: List[List[int]]) -> List[int]:
	sorted_tasks = [(tasks[i][0], tasks[i][1], i) for i in range(len(tasks))]
	sorted_tasks.sort()
	heap, res = [], []
	current_time = sorted_tasks[0][0]
	i = 0
	while i < len(sorted_tasks):
		if i > 0 and sorted_tasks[i-1][0] != sorted_tasks[i][0]:
			break
		heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2])) # finished time=>processing t, task index #3
		i += 1
	while heap or i < len(sorted_tasks):
		if not heap:
			current_time = sorted_tasks[i][0]
			heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2]))
			i += 1

		task = heapq.heappop(heap)
		current_time += task[0]
		res.append(task[1]) # finished processing
		while i < len(sorted_tasks) and sorted_tasks[i][0] <= current_time: # start time <= current task's finished time, task[0]-> current_time 
			heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2])) 
			i += 1
	return res

Posted on Disqus:

常用知识点

数据类型

boolean, number, string, bigint, symbol, any, null, undefined, array, tuple, object

注意事项：

  1. 用===
  2. 单语句也用大括号
  3. map.forEach((v, k)
  4. const arr
  5. val2Index.get(target-nums[i])! 
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
let age: number = 25;  
const age = 25;
let scores: number[] = [12, 13];
let entry: [string, number] = ["1", 2];

// return type can be void
function sum(a:number=5, b?: number): number {
	console.log(`ID: ${a}`);
	return a + b;
}

interface User {
	id: string;
	age?: number;
	readonly name: string;
}

type ID = string | number;
let userId: ID = "ab";
type Status = "pending" | "active";
enum Color {
    Red = "Red",
	Green = "Green"
}
// 类型推断: 函数变量需要写类型，函数内大部分不需要写

const map = new Map<string, number>([
        ["key1", "value1"], // like tuple
        ["key2", "value2"]
]);
map.set("a", 9);
map.forEach((v, k) => {console.log(`${k}:${v}`)}); // recommend
for(const [k, v] of map){
	if(typeof v == 'string')
		console.log(`${k}:${v}`);
}

// class: readonly, private, protected, public, constructor
// class Dob extends Animal

for (let i=0; i < 5; i++) {
	let b = i + 1;
}
const nums = [1, 2, 3];
nums.forEach((num) => {let t = num + 1;}); // recommend

// 剩余函数
function sum2(...nums: number[]){
	let s = 0;
	nums.forEach(num => {s += num;});
	for (const num of nums) {
		s += num;
	}
	return s;
}
let bb = sum2(2, 3, 4);

// 匿名函数
const add = (a: number, b:number) => {
	return a + b;
}

let cc = nums.join("");

类型 函数名 作用 输入参数 返回值 例子
for range 和len结合使用相当于取某范围List下标,第三个参数为步长 N/A N/A for i in range(len(nums))前闭后开,用逗号
array length nums.length
array sort nums.sort((a, b) => a - b);)
map get
map set
map has
map size
map delete
map clear
map keys
map values
map entries
string join 跟python相反 nums.join(“”);

Leetcode 001

TypeScript基础

Posted on Edited on Disqus:

LeetCode



Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.


Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]


Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]


Constraints: 2 <= arr.length <= 10<sup>5</sup>
* -10<sup>6</sup> <= arr[i] <= 10<sup>6</sup>

题目大意：

数组中求最小差值的所有数值pair，pair中按数值排序

解题思路：

其中一个例子是有序的，就联想到排序，然后遍历求最小插值并记录对应的结果

解题步骤：

N/A

注意事项：

N/A

Python代码：

1
2
3
4
5
6
7
8
9
10
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
	arr.sort()
	min_diff, res = float('inf'), []
	for i in range(1, len(arr)):
		if arr[i] - arr[i-1] <= min_diff:
			if arr[i] - arr[i-1] < min_diff:
				res = []
				min_diff = arr[i] - arr[i-1]
			res.append([arr[i-1], arr[i]])
	return res

算法分析：

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

Posted on Disqus:

LeetCode



Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implement the MyCircularQueue class:

MyCircularQueue(k) Initializes the object with the size of the queue to be k. int Front() Gets the front item from the queue. If the queue is empty, return -1.
int Rear() Gets the last item from the queue. If the queue is empty, return -1. boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful. boolean isEmpty() Checks whether the circular queue is empty or not.
boolean isFull() Checks whether the circular queue is full or not.

You must solve the problem without using the built-in queue data structure in your programming language.

Example 1:

Input
[“MyCircularQueue”, “enQueue”, “enQueue”, “enQueue”, “enQueue”, “Rear”, “isFull”, “deQueue”, “enQueue”, “Rear”]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4


Constraints: 1 <= k <= 1000
0 <= value <= 1000 At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

题目大意：

实现循环队列

解题思路Array(推荐)：

用两个指针为维持数据的开始和结束+1，由于循环队列，所以用mod来找到数组下标，也就是start和end一样时候，既可能是empty也可能是full，所以加一个变量记录

解题步骤：

用count就可以省去end和is_full两个变量
如果要实现同步队列，就引入self.queueLock = Lock(), with self.queueLock: 就进行enQueue操作

注意事项：

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MyCircularQueue:

    def __init__(self, k: int):
        self.data = [0] * k
        self.start = 0 # starting point of data
        self.end = 0 # ending point + 1 of data
        self.size = k
        self.is_full = False

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.end] = value
        self.end = (self.end + 1) % self.size
        if self.start == self.end:
            self.is_full = True
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.start = (self.start + 1) % self.size
        self.is_full = False
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[self.start]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.end - 1) % self.size]

    def isEmpty(self) -> bool:
        return not self.is_full and self.start == self.end

    def isFull(self) -> bool:
        return self.is_full

算法分析：

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

算法II解题思路Linked List：

比较简单，省略

算法分析：

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

Free mock interview