KK's blog

LeetCode

<div>

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined).  Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Example 1:

<pre>Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] Output: [[3,4]] Explanation: There are a total of three employees, and all common free time intervals would be [-inf, 1], [3, 4], [10, inf]. We discard any intervals that contain inf as they aren't finite. </pre>

Example 2:

<pre>Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]] </pre>

Constraints:

• 1 <= schedule.length , schedule[i].length <= 50
• 0 <= schedule[i].start < schedule[i].end <= 10^8

</div>

题目大意：

给定员工的schedule，给所有员工的空余时间的区间

解题思路：

一开始考虑用Leetcode 056 merge intervals，然后求不能merge时的区间。后来想用Leetcode 253 meeting rooms II也是关于重合区间，只要active meetings为0时，就表示空余区间，此法更容易实现

解题步骤：

N/A

注意事项：

1. 用Leetcode 253 meeting rooms II的排序解法
2. 注意输入是每一个员工的schedule如[Interval(1, 2), Interval(5, 6)]，然后是所有员工schedule的列表

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 test(self):
	TestCases.compare(self, self.employeeFreeTime([[Interval(1, 2), Interval(5, 6)], [Interval(1, 3)], [Interval(4, 10)]]), [Interval(3, 4)])

def employeeFreeTime(self, schedule: [[Interval]]) -> [Interval]:
	schedule_endpoints = []
	for li in schedule:
		for s in li:
			schedule_endpoints.append((s.start, 0)) # [(1, 0),(2,1),(5,0), (6,1)]
			schedule_endpoints.append((s.end, 1))
	schedule_endpoints.sort()
	res, free_time, active_schedule = [], [], 0
	for i in range(len(schedule_endpoints)):
		if schedule_endpoints[i][1] == 0:
			active_schedule += 1 # 0
		else:
			active_schedule -= 1 #
		if active_schedule == 0:
			free_time.append(schedule_endpoints[i][0]) #[2,5]
		if active_schedule == 1 and len(free_time) == 1:
			free_time.append(schedule_endpoints[i][0])
			free_interval = Interval(free_time[0], free_time[1])
			res.append(free_interval)
			free_time = []
	return res

算法分析：

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

LeetCode

<div><p>Given an array of integers arr, find the sum of <code>min(b)</code>, where <code>b</code> ranges over every (contiguous) subarray of <code>arr</code>. Since the answer may be large, return the answer <strong>modulo</strong> <code>10⁹ + 7</code>.</p>

<p> </p> <p><strong>Example 1:</strong></p>

<pre><strong>Input:</strong> arr = [3,1,2,4] <strong>Output:</strong> 17 <strong>Explanation:</strong> Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17. </pre>

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> arr = [11,81,94,43,3] <strong>Output:</strong> 444 </pre>

<p> </p> <p><strong>Constraints:</strong></p>

<ul> <li><code>1 <= arr.length <= 3 * 10⁴</code></li> <li><code>1 <= arr[i] <= 3 * 10⁴</code></li> </ul> </div>

题目大意：

求所有子数组的最小值的和

算法思路：

求区间最值用Stack，因为是最小值，所以用递增栈
一开始考虑用类似DP，因为若知道[3, 2, 6]栈为[2, 6], 8入栈，8与每一个栈内元素计算最小值，优化是用栈内的累计和，如2和6对应的累计和而不用每个元素计算。
参考了网上算法，栈内每个元素向左向右区间内（包括自己）均是最小值，所以出栈时候进行计算即可。
如[3, 2, 8, 7, 6, 9, 10, 4]栈是[2, 6, 9, 10]对应的下标，现在4入栈，9和10出栈后，6准备出栈。
prev_idx为6的下标4， i是7，6是[8, 7, 6], [7, 6], [6]三个区间的最小值prev_idx - stack[-1] = 3个区间，
而这些区间的最小值的和还要再乘以后面的大于它的数，如[7, 6]这个区间可以和这些区间合并[7, 6], [7, 6, 9], [7, 6, 9, 10], 所以(i - prev_idx) = 3
这就是arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)的精髓

注意事项：

1. 头尾加入最小值，加入头部因为公式需要栈内的前元素，这样可以处理只有一个元素出栈的情况。尾部加入最小值因为确保所有元素都出栈。

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def sumSubarrayMins(self, arr: List[int]) -> int:
	arr.insert(0, -sys.maxsize)
	arr.append(-sys.maxsize)
	stack, res = [], 0
	for i in range(len(arr)):
		while stack and arr[i] < arr[stack[-1]]:
			prev_idx = stack.pop()
			res += arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
			res = res % (pow(10, 9) + 7)
		stack.append(i)
	return res

算法分析：

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

LeetCode

<div>

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

<pre>Input: arr = [2,1,3,1,2,3,3] Output: [4,2,7,2,4,4,5] Explanation:

• Index 0: Another 2 is found at index 4. |0 - 4| = 4
• Index 1: Another 1 is found at index 3. |1 - 3| = 2
• Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
• Index 3: Another 1 is found at index 1. |3 - 1| = 2
• Index 4: Another 2 is found at index 0. |4 - 0| = 4
• Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
• Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5 </pre>

Example 2:

<pre>Input: arr = [10,5,10,10] Output: [5,0,3,4] Explanation:

• Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
• Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
• Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
• Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4 </pre>

Constraints:

• n == arr.length
• 1 <= n <= 10<sup>5</sup>
• 1 <= arr[i] <= 10<sup>5</sup>

</div>

题目大意：

求相同元素的下标差的和

解题思路：

暴力法是TLE，由于存在重复计算。用prefix和suffix来优化。
prefix为从某个元素为起点到前继节点下标差之和
suffix为从某个元素为起点到后继节点下标差之和
结果 = prefix[i] + suffix[i]

解题步骤：

1. 用Map来存储相同元素的下标
2. 用prefix和suffix来计算每个元素的结果

注意事项：

1. 一开始用presum表示从起点到其他下标的差之和。这不能用于某个元素的前继元素下标差之和。所以要改成从某个元素为起点到前继节点下标差之和

Python代码：

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

def getDistances(self, arr: List[int]) -> List[int]:
	val_to_index = collections.defaultdict(list)
	res = [0] * len(arr)
	for i in range(len(arr)):
		val_to_index[arr[i]].append(i)
	for val, indices in val_to_index.items():
		prefix, suffix = [0], [0]
		for i in range(1, len(indices)):
			prefix.append(prefix[-1] + i * abs(indices[i] - indices[i - 1]))
		for i in range(len(indices) - 2, -1, -1):
			suffix.append(suffix[-1] + (len(indices) - i - 1) * abs(indices[i] - indices[i + 1]))
		for i in range(len(indices)):
			res[indices[i]] = prefix[i] + suffix[len(indices) - i - 1]
	return res

算法分析：

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

LeetCode

<div>

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

• WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
• int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

<pre>Input ["WordDistance", "shortest", "shortest"] [[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]] Output [null, 3, 1]

Explanation WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]); wordDistance.shortest("coding", "practice"); // return 3 wordDistance.shortest("makes", "coding"); // return 1 </pre>

Constraints:

• 1 <= wordsDict.length <= 3 * 10<sup>4</sup>
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2
• At most 5000 calls will be made to shortest.

</div>

题目大意：

设计数据结构返回单词列表中两单词下标最短距离。单词列表含重复单词

解题思路：

记录word到下标列表。可以用logn搜索另一个列表，总时间复杂度为O(nlogn)。不如用mergesort的merge来计算，复杂度为O(n)

解题步骤：

N/A

注意事项：

Python代码：

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

class WordDistance(TestCases):

    def __init__(self, wordsDict: List[str]):
        self.word_to_indices = collections.defaultdict(list)
        for i in range(len(wordsDict)):
            self.word_to_indices[wordsDict[i]].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        indices1 = self.word_to_indices[word1]
        indices2 = self.word_to_indices[word2]
        i, j, res = 0, 0, float('inf')
        while i < len(indices1) and j < len(indices2):
            res = min(res, abs(indices1[i] - indices2[j]))
            if indices1[i] <= indices2[j]:
                i += 1
            else:
                j += 1
        return res

算法分析：

shortest时间复杂度为O(L)，空间复杂度O(1)。L为两单词下标列表的最短长度

LeetCode

<div>

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

• LFUCache(int capacity) Initializes the object with the capacity of the data structure.
• int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
• void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Example 1:

<pre>Input ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation // cnt(x) = the use counter for key x // cache=[] will show the last used order for tiebreakers (leftmost element is most recent) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // return 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.   // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1. // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // return 4 // cache=[3,4], cnt(4)=2, cnt(3)=3 </pre>

Constraints:

• 0 <= capacity <= 10<sup>4</sup>
• 0 <= key <= 10<sup>5</sup>
• 0 <= value <= 10<sup>9</sup>
• At most 2 * 10<sup>5</sup> calls will be made to get and put.

<span style="display: none;"> </span></div>

双Map+分区LL解题思路(推荐)：

类似于LRU，但本质上区别较大。一开始思路可参考算法II，它的缺点是move_up需要从该层的某个位置删除加入到上一个freq较大的下一层的末尾。为了避免此问题，考虑不用单一链表，而是对应不同freq的多个链表。所以引入freq_map来记录每个LL的起点。由于每个LL都是从旧到新（跟LRU一样），新的插入到末尾，删除的从头删除，所以需要是循环链表，最终是一个循环双向LL。ListNode的next和prev都指向自己

move_up解决了，另一个难点是get_lfu_node，这里引入min_freq来记录当前最小的freq。它的更新由三方面引起:新节点min_freq=1，get的move_up和旧节点move_up。后两者是一样的，都是move_up后查看min_freq所以的LL是否为空。

总结一下与LRU的区别：

• set也是三种情况但要更新min_freq
• ListNode多了freq，next prev指向自己形成循环LL，key，val含默认值
• Cache中多了freq map和min_freq
• 链表操作为move_up和get_lru_node，这点和算法II一样
• 节点操作为remove_node, add_to_tail和LRU一样。add_to_tail是分层LL末尾不是总链表末尾

注意事项：

1. 用了一小时debug min_freq的更新，move_up发生时候，检查min_freq所在的LL，若为空，增加1，而不是检查node_freq所在的LL。新节点令min_freq变成1
2. 思路上：LRU是Map to Node in 全局双向LL，而LRU是Map to Node in 分区双向循环LL。存在多条LL，每个LL的起点终点存在freq map中。min_freq记录要删除的LFU节点对应的频率。
3. 思路上：再LRU基础上增加freq域默认为1，key, val默认为0，prev和next指向自己，形成双向循环LL
4. capacity可能为0，LRU那天capacity大于0
5. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.key_to_node = collections.defaultdict(ListNode)
        self.freq_to_head = collections.defaultdict(ListNode)
        self.min_freq = 1
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node_freq = node.freq
            self.move_up(node)
            # if self.freq_to_head[node_freq].next == self.freq_to_head[node_freq]:
              #  self.min_freq = node.freq
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self.move_up(node)
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
        elif self.capacity > 0:
            if len(self.key_to_node) == self.capacity:
                lru_node = self.get_lru_node()
                self.key_to_node.pop(lru_node.key)
                self.remove_node(lru_node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node
            self.min_freq = 1

    def move_up(self, node):
        self.remove_node(node)
        node.freq += 1
        self.add_to_tail(node)

    def get_lru_node(self):
        head = self.freq_to_head[self.min_freq]
        return head.next

    def add_to_tail(self, node):
        head = self.freq_to_head[node.freq]
        predecessor, successor = head.prev, head
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None

class ListNode:

    def __init__(self, key=0, val=0, freq=1):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = self # self-pointed
        self.next = self

算法分析：

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

类LRU算法II解题思路(不推荐)：

似乎Leetcode改变了要求，之前此法是可以通过的，但现在put要求O(1)了，所以TLE了。

注意事项：

1. 再LRU基础上增加freq域默认为1，新节点插入doubly LL末尾，LL以freq从大到小，同一个频率从最旧到最新(LRU)。所以若满容量要删除节点从freq=1中往前找到该层的首节点
2. capacity可能为0，LRU那天capacity大于0
3. move_up是往前搜索, it = it.prev而不是用next。比较条件为it.freq < node.freq，加入到同一频率的末尾
4. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = collections.defaultdict(ListNode)
        # newly inserted to tail
        self.head, self.tail = ListNode(0, 0), ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            self.move_up(self.key_to_node[key])
            return self.key_to_node[key].val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            self.key_to_node[key].val = value
            self.move_up(self.key_to_node[key])
        elif self.capacity > 0: # remember
            if len(self.key_to_node) == self.capacity:
                node = self.get_lfu_node()
                self.key_to_node.pop(node.key)
                self.remove(node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node

    def get_lfu_node(self):
        it = self.tail.prev
        min_freq = it.freq
        while it != self.head and it.freq == min_freq:
            it = it.prev # remember prev not next
        return it.next

    def move_up(self, node):
        node.freq += 1
        it = node.prev
        self.remove(node)
        while it != self.head and it.freq < node.freq: # remember <=
            it = it.prev # remember prev not next
        predecessor, successor = it, it.next
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def add_to_tail(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor # remember

    def remove(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:

    def __init__(self, key, val, freq=1, prev=None, next=None):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = prev
        self.next = next

注意事项：

1. 在LRU基础上，ListNode引入freq域， 当频率增加时候，找到新的频率对应的末节点插入。其它基本不变。插入最差是O(n). 要提高的话，需要加入map<freq, ListNodeHead>和minFreq来迅速定位下一个插入位置。第一个Map不变，但LL不再是一串，而是按频率大小的多串。

Java代码：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

Map<Integer, ListNode> map;
ListNode head; // from most frequent to less
ListNode tail;
int capacity;
public L460LFUCache(int capacity) {
	this.capacity = capacity;
	head = new ListNode(-1, -1, Integer.MAX_VALUE);
	tail = new ListNode(-1, -1, Integer.MIN_VALUE);
	head.next = tail;
	tail.prev = head;
	map = new HashMap<>();
}

public int get(int key) {
	if(!map.containsKey(key))
		return -1;
	moveUp(key);
	return map.get(key).val;
}

public void put(int key, int value) {
	if(capacity == 0)
		return;
	
	if(map.containsKey(key)) {
		moveUp(key);
		map.get(key).val = value; // remember to update the value
	}
	else {
		if(map.size() == capacity) {
			map.remove(tail.prev.key);
			deleteNode(tail.prev);
		}
		// add new key
		ListNode newNode = new ListNode(key, value);
		addNode(newNode, tail);
		map.put(key, newNode);
		moveUp(key);
	}
}

void moveUp(int key) {
	ListNode curNode = map.get(key);
	curNode.addOne();
	ListNode iterNode = curNode;
	while(iterNode.freq <= curNode.freq)
		iterNode = iterNode.prev;
	if(iterNode != curNode) {
		deleteNode(curNode);
		addNode(curNode, iterNode.next);
	}
}

void addNode(ListNode curNode, ListNode nextNode) {
	ListNode prevNode = nextNode.prev;
	prevNode.next = curNode;
	curNode.prev = prevNode;
	curNode.next = nextNode;
	nextNode.prev = curNode;
}
// delete head node and updated node
void deleteNode(ListNode curNode) {
	ListNode nextNode = curNode.next;
	ListNode prevNode = curNode.prev;
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
	curNode.next = null;
	curNode.prev = null;
}

public class ListNode {
	public int key;
	public int val;
	public int freq = 1;
	public ListNode next;
	public ListNode prev;

	public ListNode(int key, int val) {
		this.key = key;
		this.val = val;
	}
	
	public ListNode(int key, int val, int freq) {
		this.key = key;
		this.val = val;
		this.freq = freq;
	}
	
	public void addOne() {
		freq++;
	}
}

算法分析：

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