KK's blog

常用知识点

数据类型

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

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

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;
}

TypeScript基础

LeetCode

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.

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

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

题目大意：

数组中求最小差值的所有数值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)

LeetCode

<div>

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:

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

Constraints:

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

</div>

题目大意：

实现循环队列

解题思路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)

LeetCode

<div>

Special binary strings are binary strings with the following two properties:

• The number of 0's is equal to the number of 1's.
• Every prefix of the binary string has at least as many 1's as 0's.

You are given a special binary string s.

A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.

Return the lexicographically largest resulting string possible after applying the mentioned operations on the string.

Example 1:

<pre>Input: s = "11011000" Output: "11100100" Explanation: The strings "10" [occuring at s[1]] and "1100" [at s[3]] are swapped. This is the lexicographically largest string possible after some number of swaps. </pre>

Example 2:

<pre>Input: s = "10" Output: "10" </pre>

Constraints:

• 1 <= s.length <= 50
• s[i] is either '0' or '1'.
• s is a special binary string.

</div>

题目大意：

Special string由0和1组成，数目一样且每个前缀1的数目大于等于0的数目。可以交换其内部的子特别字符串，让其数值最大

解题思路：

一开始考虑用统计presum的方法LeetCode 696 Count Binary Substrings，然后如果后者1的数目大于前者0的数目，表示可以交换。但这里只考虑到相邻特别子串的关系，并没有考虑特别字串的内部也是需要排序的。

此题特别串是含有递归定义，所以考虑DFS。首先，一个特别字符串是由多个特别子串连续组成，所以需要找出它们，且进行排序
第二，更难的是每个字串内部特别字串也需要重新排序比如11011000中的10和1100就需要互换。这个串不是直接由内部特殊字串组成而是1+特殊串+0组成(递归式). 根据特殊串定义，是以1开头0结束，类似于统计左右括号数，这点规律比较难找。

总结而已，这题是catalan递归但不是递归两边是，多边。且每个递归都是由总结出来的规律获得1+f(s[start+1:i])获得

解题步骤：

N/A

注意事项：

1. 如果遇到0，count要减一
2. 倒序排序：parts.sort(reverse=True)

Python代码：

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

def makeLargestSpecial(self, s: str) -> str:
	parts = []
	count = 0
	start = 0
	for i in range(len(s)):
		if s[i] == '1':
			count += 1
		else:
			count -= 1 #attn
		if count == 0:
			sorted_part = '1'+ self.makeLargestSpecial(s[start+1:i]) + '0'
			parts.append(sorted_part)
			start = i + 1
	parts.sort(reverse=True) #attn
	return ''.join(parts)

算法分析：

next时间复杂度为O(n^2)，空间复杂度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
25
26
27
28
29
30
31
32
33
34
35
36

def makeLargestSpecial(self, s: str) -> str:
	count, presum = 1, []
	for i in range(1, len(s)):
		if s[i] == s[i-1]:
			count += 1
		else:
			presum.append(count)
			count = 1
	if count > 0:
		presum.append(count)
	print(presum)

	def move(presum):
		is_moved = False
		for i in range(2, len(presum), 2):
			if presum[i] > presum[i-1]:
				presum[i-2] += -presum[i-1] + presum[i]
				presum[i+1] += -presum[i] + presum[i-1]
				presum[i-1], presum[i] = presum[i], presum[i-1]
				print(presum)
				is_moved = True
		return is_moved
	
	move_res = True
	while move_res:
		move_res = move(presum)

	res, c = '', '1'
	for n in presum:
		res += c * n
		if c == '1':
			c = '0'
		else:
			c = '1'
	print(res)
	return res

LeetCode

<div>

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

Example 1:

<pre>Input: nums = [1,0,1,0,1], goal = 2 Output: 4 Explanation: The 4 subarrays are bolded and underlined below: [<u>1,0,1</u>,0,1] [<u>1,0,1,0</u>,1] [1,<u>0,1,0,1</u>] [1,0,<u>1,0,1</u>] </pre>

Example 2:

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

Constraints:

• 1 <= nums.length <= 3 * 10<sup>4</sup>
• nums[i] is either 0 or 1.
• 0 <= goal <= nums.length

</div>

题目大意：

有0和1组成的字符串，求所有子数组的和等于goal的个数

解题思路Presum(推荐)：

求子数组和第一时间想到presum，然后就是presum-goal是否在hashmap中，类似于Two sum。

解题步骤：

N/A

注意事项：

1. presum初始值为0，因为如果单元素数组，才能得到它的差值。
2. val_to_freq的计算要在循环中，类似于Two sum，不能提前用Counter计算，否则会有重复，比如[0, 0], goal=0, 不应该为4.

Python代码：

1
2
3
4
5
6
7
8
9
10

def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	presum = [0]
	for i in range(len(nums)):
		presum.append(presum[-1] + nums[i])
	val_to_freq, res = collections.defaultdict(int), 0
	for i in range(len(presum)):
		if presum[i] - goal in val_to_freq:
			res += val_to_freq[presum[i] - goal]
		val_to_freq[presum[i]] += 1 #attn
	return res

算法分析：

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

算法II解题思路Sliding Window：

此法虽然空间复杂度较优，但较难想。求字串的和可以考虑用Two pointers两边夹。这里求所有可能性，比如0011100, goal=3, 必须包括前缀0和后缀0，所以用Two pointers最长串的模板
类似于LeetCode 340 Longest Substring with At Most K Distinct Characters，不满足条件为窗口和大于goal，所以满足条件为小于等于goal(类似于at most k)。 所以要用at_most(goal) - at_most(goal - 1)才能得到最后结果。
计算的时候，是i-left+1代表窗口和<=subgoal的以nums[i]为结尾的子数组个数，比如10101, i指向最后一个1, left指向第一个0, res是4个，对应1, 01, 101, 0101

注意事项：

1. 模板满足条件在内循环外，所以计算结果在内循环结束后。
2. subgoal如果小于0，返回0。比如goal为0，nums=[0,0]

Python代码：

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

def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
	def at_most(subgoal):
		if subgoal < 0: #attn
			return 0
		window_sum, left, res = 0, 0, 0
		i = 0
		for i in range(len(nums)):
			window_sum += nums[i]
			while window_sum > subgoal:
				window_sum -= nums[left]
				left += 1
			res += i - left + 1 # ending with nums[i]
		return res

	return at_most(goal) - at_most(goal - 1)

算法分析：

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