KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6


Example 2:

Input: lists = []
Output: []


Example 3:

Input: lists = [[]]
Output: []


Constraints:

k == lists.length 0 <= k <= 10^4
0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order. The sum of lists[i].length won’t exceed 10^4.

算法思路：

N/A

注意事项：

  1. heap不能比较ListNode大小，要实现lt函数或者将(node.val, node)对加入到heap中(此法Leetcode有编译错误但PyCharm可过)
  2. 出堆后node的next赋None不需要，因为每个节点next都会重复赋值，而最后一个节点本来也没有next

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode.__lt__ = lambda x, y: x.val < y.val
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        fake_head = ListNode(0)
        for head in lists:
            if head:
                heappush(heap, head)
        it = fake_head
        while heap:
            node = heappop(heap)
            if node.next:
                heappush(heap, node.next)
            # node.next = None
            it.next = node
            it = it.next
        return fake_head.next

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(k).

算法II解题思路：

Devide and Conquer

注意事项：

  1. k.next = None因为删除节点，所以赋None，这句不加也行，但作为良好习惯建议加，且不能在i = i.next前加，否则i会变空。
  2. 查lists是否为空

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
def mergeKLists2(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	return self.merge_sort(lists, 0, len(lists) - 1)

def merge_sort(self, lists, start, end):
	if start >= end:
		return lists[start]
	mid = start + (end - start) // 2
	li = self.merge_sort(lists, start, mid)
	li2 = self.merge_sort(lists, mid + 1, end)
	return self.merge_two_lists(li, li2)

def merge_two_lists(self, li, li2):
	i, j, res = li, li2, ListNode(0)
	k = res
	while i and j:
		if i.val < j.val:
			k.next = i
			i = i.next
			k = k.next
			k.next = None
		else:
			k.next = j
			j = j.next
			k = k.next
			k.next = None
	if i:
		k.next = i
	if j:
		k.next = j
	return res.next

算法分析：

不管多少次递归，每次递归的一层总的节点数为n，而对k做二分，所以递归数为logk, 时间复杂度为O(nlogk)，空间复杂度O(1).

算法III解题思路：

算法二的迭代法

注意事项：

  1. 输入大小的奇偶处理
  2. 返回值是lists[0]而不是lists

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def mergeKLists3(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	while len(lists) > 1:
		tmp = []
		if len(lists) % 2 == 1:
			lists.append([])
		for i in range(0, len(lists), 2):
			tmp.append(self.merge_two_lists(lists[i], lists[i + 1]))
		lists = tmp
	return lists[0]

算法分析：

同算法二.

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.


Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4


Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1


Constraints:

1 <= nums.length <= 2500 -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

DP算法思路：

N/A

注意事项：

  1. 初始化从1开始，因为一个数是递增序列
  2. 返回值不是dp[-1]，而是所有dp的最大值

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[3, 5, 1, 3, 9, 5, 6] 1, 3, 5, 6
[1, 0]
dp[i] = max(dp[j]) + 1, if nums[i-1] > nums[j-1], 1 <= j < i
	
def lengthOfLIS(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res = 1
	# dp = [0, 1, 0]
	dp = [1] * (len(nums) + 1)
	for i in range(1, len(dp)):
		# i = 2
		# j = 1
		for j in range(1, i):
			if nums[i - 1] > nums[j - 1]:
				dp[i] = max(dp[i], dp[j] + 1)
		res = max(res, dp[i])
	return res

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2).

打印路径算法思路：

N/A

注意事项：

  1. path数组大小和原数组一样，因为path数组的下标和值都是下标，这样不用-1，直接nums[pos]，不容易错
  2. 多了Line 11 - 12和14 - 15，需要记录产生最大值的下标
  3. 打印的时候path数组的下标和值都是下标，而值是前一个下标，所以是pos = positions[pos]，循环次数为dp值，开始下标为dp值对应的下标path[:biggest_pos + 1]。

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 lengthOfLIS_with_path(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res, path = 1, [0] * len(nums)  # remember no + 1
	biggest_pos = -1
	dp = [1] * (len(nums) + 1)
	for i in range(1, len(dp)):
		for j in range(1, i):
			if nums[i - 1] > nums[j - 1]:
				dp[i] = max(dp[i], dp[j] + 1)
				if dp[i] == dp[j] + 1:
					path[i - 1] = j - 1
		res = max(res, dp[i])
		if res == dp[i]:
			biggest_pos = i - 1
	path_list = self.print_path(nums, path[:biggest_pos + 1], res)
	return path_list

def print_path(self, nums, path, dp_value):
	pos, res = len(path) - 1, []
	for _ in range(dp_value):
		res.append(nums[pos])
		pos = path[pos]
	return res[::-1]

bisect算法II解题思路：

N/A

注意事项：

  1. bisect_left类似于greater_or_equal_position但若equal时，取第一个，但greater_or_equal_position是取最后一个，此题没关系，因为相等的数会被替换掉，递增序列中不会存在相等的数

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLIS(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res = []
	for i in range(len(nums)):
		pos = bisect.bisect_left(res, nums[i])
		if pos < len(res):
			res[pos] = nums[i]
		else:
			res.append(nums[i])
	return len(res)

算法分析：

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

Posted on Edited on Disqus:

LeetCode

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.



Given an integer n, return the nth ugly number.



 


Example 1:



Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.


Example 2:



Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.


 


Constraints:




  • 1 <= n <= 1690


题目大意：

求第n个丑数，丑数是由2,3,5相乘获得

Heap算法思路(推荐)：

Heap

注意事项：

  1. 与BFS模板一样，visited要在if里面。可以理解为一个数有三条边产生三个新数，所以和BFS模板一样

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def nthUglyNumber(self, n: int) -> int:
	heap, visited = [1], set([1])
	primes = [2, 3, 5]
	res = 0
	while n >= 1:
		res = heappop(heap)
		for factor in primes:
			tmp = factor * res
			if tmp not in visited:
				heappush(heap, tmp)
				visited.add(tmp)
		n -= 1
	return res

算法分析：

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

双指针算法II解题思路：

比较难想，不推荐，但思路可用于其他题如L373。指针的数乘以指向数组的数，此题中指针为p2, p3, p5, 分别代表2， 3， 5， 数组为res数组，每次比较它们的积。

注意事项：

  1. 与上题一样要去重，此时，3个乘积中可能会相同且最小，同时移动这些指针

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nthUglyNumber(self, n: int) -> int:
        res = [1]
        p2, p3, p5 = 0, 0, 0
        while n > 1:
            num = min(2 * res[p2], 3 * res[p3], 5 * res[p5])
            if num == 2 * res[p2]:
                p2 += 1
            if num == 3 * res[p3]:
                p3 += 1
            if num == 5 * res[p5]:
                p5 += 1
            res.append(num)
            n -= 1
        return res[-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

FirstUnique(int[] nums) Initializes the object with the numbers in the queue. int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
void add(int value) insert value to the queue.

Example 1:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”showFirstUnique”,”add”,”showFirstUnique”,”add”,”showFirstUnique”]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1


Example 2:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”add”,”add”,”add”,”add”,”showFirstUnique”]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:
[null,-1,null,null,null,null,null,17]
Explanation:
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17


Example 3:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”showFirstUnique”]
[[[809]],[],[809],[]]
Output:
[null,809,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809);          // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1


Constraints: 1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8 1 <= value <= 10^8
* At most 50000 calls will be made to showFirstUnique and add.

算法思路：

Dict + LL (1次) + Set (2次)。此题非常类似于LRU, 相当于实习LinkedHashMap。

注意事项：

  1. 注意两种情况，节点不在Map, 在Map中，对应的LL操作同样是add_to_tail和remove_node不过少了move_to_tail。
  2. 头尾dummy node，初始化要相连。
  3. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
  4. 区别还有ListNode不需要key，因为输入是单值，不是key-value对。数据结构多了set来记录出现两次及以上的元素，直接忽略

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 FirstUnique(TestCases):

    '''
    2, 3, 5, 5
    dict:
    {2:1
     3:1
     5:2 (remove)
     }
    LinkedList: 2, 3, 5(r), 5(r)
    dict:
    {
        2: Node(2)
        3: Node(3)
        5: Node(5)
    }
    
    '''

    def __init__(self, nums: List[int]):
        self.head = ListNode(0)  # only store unique elements
        self.tail = ListNode(0)
        self.key_to_node = {}  # only store unique elements
        self.non_unique_set = set()
        self.head.next, self.tail.prev = self.tail, self.head

        for n in nums:
            self.add(n)

    def showFirstUnique(self) -> int:
        if len(self.key_to_node) == 0:
            return -1
        return self.head.next.val
    # 2, 3, 5, 5
    def add(self, value: int) -> None:
        if value in self.non_unique_set:
            return

        if value not in self.key_to_node:
            new_node = ListNode(value)
            self.add_to_tail(new_node)
            self.key_to_node[value] = new_node
        else:
            to_be_removed_node = self.key_to_node[value]
            self.key_to_node.pop(value)
            self.remove_node(to_be_removed_node)
            self.non_unique_set.add(value)

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

    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, val, next = None, prev = None):
        self.val = val
        self.next = next
        self.prev = prev

算法分析：

每个操作时间复杂度为O(1)，空间复杂度O(n).

Posted on Edited on Disqus:

LeetCode



Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object. bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

Input
[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.


Constraints:

-2<sup>31</sup> <= val <= 2<sup>31</sup> - 1 At most 2 * ``10<sup>5</sup> calls will be made to insert, remove, and getRandom.
There will be *at least one element in the data structure when getRandom is called.

算法思路：

Dict + List

注意事项：

  1. 检查若删除最后一个元素发现问题，remove中删除key要放在最后，不能放中间

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
class RandomizedSet(TestCases):

    def __init__(self):
        self.nums = []
        self.key_to_index = {}

    def insert(self, val: int) -> bool:
        if val in self.key_to_index:
            return False
        self.nums.append(val)
        self.key_to_index[val] = len(self.nums) - 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.key_to_index:
            return False
        index = self.key_to_index[val]
        last_val = self.nums[len(self.nums) - 1]
        self.nums[index] = last_val
        self.key_to_index[last_val] = index
        self.key_to_index.pop(val)  # remember to put it last
        self.nums.pop()
        return True

    def getRandom(self) -> int:
        return self.nums[random.randint(0, len(self.nums) - 1)]

算法分析：

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

Free mock interview