KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given a string s, find the longest palindromic subsequence‘s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.


Example 2:

Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.


Constraints:

1 <= s.length <= 1000 s consists only of lowercase English letters.

题目大意：

求字符串中最长回文序列

算法思路：

一开始看到子序列如LIS就想用DP，dp[i]表示以s[i]为结尾的最长回文子序列。但不容易推导公式，难点是没有限制左边界
所以应该扩展到二维dp[i][j]表示[i, j]之间的最长回文子序列。公式就简单多了

1
2
dp[i][j] = dp[i+1][j-1] + 2,             s[i] == s[j]
         = max(dp[i+1][j], dp[i][j-1]),  s[i] != s[j]

注意事项：

  1. 难点是想到用二维DP(区间型DP)。用区间型递归模板，注意dp[i + 1][j]并不是i - 1
  2. 初始值为dp[i][i] = 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def longestPalindromeSubseq(self, s: str) -> int:
	dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
	for i in range(len(s)):
		dp[i][i] = 1
	for k in range(1, len(s)):
		for i in range(len(s) - k):
			j = i + k
			if s[i] == s[j]:
				dp[i][j] = dp[i + 1][j - 1] + 2
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	return dp[0][-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the i<sup>th</sup> node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a<sub>j</sub>, b<sub>j</sub>] indicates that there is a directed edge from node a<sub>j</sub> to node b<sub>j</sub>.

A valid path in the graph is a sequence of nodes x<sub>1</sub> -> x<sub>2</sub> -> x<sub>3</sub> -> ... -> x<sub>k</sub> such that there is a directed edge from x<sub>i</sub> to x<sub>i+1</sub> for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:



Input: colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).


Example 2:



Input: colors = “a”, edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.


Constraints:

n == colors.length m == edges.length
1 <= n <= 10<sup>5</sup> 0 <= m <= 10<sup>5</sup>
colors consists of lowercase English letters. 0 <= a<sub>j</sub>, b<sub>j</sub> < n

题目大意：

给定一个图，有n个节点，每个节点的颜色已知，用a-z表示，求所有不循环路径上同种颜色的最大节点数，若有循环返回-1.

算法思路：

拓扑排序 + DP

  1. 看到侦测循环考虑用拓扑排序
  2. 拓扑排序的同时，如果知道父亲节点有最大的同种颜色数，容易计算儿子的同种颜色数dp[child]
    dp[child] = max(dp[parent]) for all the parents for the child
    由于有26种颜色，扩展到最大的第i种颜色数dp[child][i]表示以child为结尾的路径上第i种颜色的累计最大节点数 
    1
    2
    dp[child][i] = max(dp[parent][i] + 1) if color[child] == color[parent] for all the immediate parents for the child, i = 1..26 
    			= max(dp[parent][i])     if color[child] != color[parent]

    注意事项：

  3. 见到最值且跟图相关，就考虑用BFS，而且要侦测循环就要用拓扑排序。要记录父节点颜色的累计和，考虑用DP，DP跟颜色相关且颜色都是小写字母，也就是26种
  4. 递归式是所有直接父节点的最大值。因为若有两条路径到达child这个节点，路径1第a种颜色有2个，而路径上第a种颜色有5个。
  5. 计算dp值在知道边的始点和终点上，也就是入度数减一之前。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
	graph = [[] for _ in range(len(colors))]
	in_degree = [0] * len(colors)
	for _edge in edges:
		graph[_edge[0]].append(_edge[1])
		in_degree[_edge[1]] += 1
	res = []
	dp = [[0 for _ in range(26)] for _ in range(len(colors))]
	initial_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0]
	for _node in initial_nodes:
		dp[_node][ord(colors[_node]) - ord('a')] = 1
	queue = collections.deque(initial_nodes)
	while queue:
		node = queue.popleft()
		res.append(node)
		for j in graph[node]:
			for i in range(26):
				dp[j][i] = max(dp[j][i], dp[node][i] + (1 if ord(colors[j]) - ord('a') == i else 0)) # remember max(dp[j][i]
			in_degree[j] -= 1
			if in_degree[j] == 0:
				queue.append(j)
	return -1 if len(colors) != len(res) else max(map(max, dp))

算法分析：

时间复杂度为O(V + E)，空间复杂度O(V + E)

Posted on Edited on Disqus:

LeetCode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

**Input:** root = [1,2,2,3,4,4,3]
**Output:** true

Example 2:

**Input:** root = [1,2,2,null,3,null,3]
**Output:** false

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

题目大意：

判断二叉树是否对称

解题思路：

Easy题，但难点是转化成比较两棵树是否对称

解题步骤：

N/A

注意事项：

  1. 难点是转化成比较两棵树是否对称
  2. 还要比较值相等，root.val == root2.val

Python代码：

1
2
3
4
5
6
7
8
9
def isSymmetric(self, root: TreeNode) -> bool:
	return self.is_symmetric(root.left, root.right)

def is_symmetric(self, root, root2):
	if not root and not root2:
		return True
	if not root or not root2:
		return False
	return root.val == root2.val and self.is_symmetric(root.left, root2.right) and self.is_symmetric(root.right, root2.left)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Numbers can be regarded as the product of their factors.

For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

Example 1:

Input: n = 1
Output: []


Example 2:

Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]


Example 3:

Input: n = 37
Output: []


Constraints: 1 <= n <= 10<sup>7</sup>

题目大意：

求所有因式分解

解题思路：

求所有解，所以用DFS。类似于LeetCode 039 Combination Sum元素可复用。

解题步骤：

N/A

注意事项：

  1. 类似于元素可复用的组合和。但更似全组合模板，append发生在循环中，而不是终止条件中。比如12，遇到2就把商[2, 6]加入到结果
  2. 数值区间的组合，start和target都是数值，而不是数组长度。i是从start开始，而不是从2开始，保证path里的数有序
  3. target // i < i 保证path里的数有序，否则12=232，不可行
  4. i从start循环到math.sqrt(n) + 1，否则会TLE

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getFactors(self, n: int) -> List[List[int]]:
	res = []
	self.dfs(n, 2, n, [], res)
	return res

def dfs(self, n, start, target, path, res):
	if target == 1:
		return
	for i in range(start, int(math.sqrt(n) + 1)): # remember to use start
		if target % i != 0 or target // i < i: # remember
			continue
		path.append(i)
		res.append(list(path + [target // i]))
		self.dfs(n, i, target // i, path, res) 
		path.pop()

算法分析：

时间复杂度为O(2n)，空间复杂度O(# of prime factors)

Posted on Edited on Disqus:

LeetCode



You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendarTwo class:

MyCalendarTwo() Initializes the calendar object. boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
[“MyCalendarTwo”, “book”, “book”, “book”, “book”, “book”, “book”]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15);  // return False, The event ca not be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.


Constraints:

0 <= start < end <= 10<sup>9</sup> At most 1000 calls will be made to book.

暴力法算法思路(推荐)：

存储所有区间和重合区间

注意事项：

  1. 区间比较难写，用符合加入会议条件的相反来写，not (start >= root.end or end <= root.start)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyCalendar(TestCases):
    def __init__(self):
        self.calendar = []
        self.overlaps = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.overlaps:
            if not (start >= e or end <= s):
                return False

        for s, e in self.calendar:
            if not (start >= e or end <= s):
                self.overlaps.append((max(start, s), min(end, e)))
        self.calendar.append((start, end))
        return True

算法分析：

时间复杂度为O(n2), 空间复杂度O(n)

算法II解题思路：

有重复区间，考虑用meeting rooms的方法二。用一个map来存储endpoint包括start和end的频率，若遇到start，map[start]++, 若遇到end, map[end]–，插入一个区间后，遍历所有endpoints，若超过3就返回False
虽然复杂度稍差，系数更大。但此法更有推广性，如果允许重复会议更多，此法可扩展

注意事项：

  1. 先插入有序区间，然后统计看是否有重复区间超过2.
  2. 若是False，用remove这个函数要删除刚插入的。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MyCalendar(TestCases):
    def __init__(self):
        self.calendar = []

    def book(self, start: int, end: int) -> bool:
        bisect.insort(self.calendar, (start, 1))
        bisect.insort(self.calendar, (end, -1))
        active_meeting = 0
        for endpoint, _type in self.calendar:
            if _type == 1:
                active_meeting += 1
            else:
                active_meeting -= 1
            if active_meeting >= 3:
                self.calendar.remove((start, 1))
                self.calendar.remove((end, -1))
                return False
        return True

算法分析：

时间复杂度为O(n2), 空间复杂度O(n)

Free mock interview