KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.


Example 2:

Input: n = 1, bad = 1
Output: 1


Constraints:

* 1 <= bad <= n <= 2<sup>31</sup> - 1

算法思路：

N/A

注意事项：

  1. 题目是先good再bad，所以用first position模板

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def firstBadVersion(self, n):
	start, end = 0, n
	while start + 1 < end:
		mid = start + (end - start) // 2
		if isBadVersion(mid):
			end = mid
		else:
			start = mid
	if isBadVersion(start):
		return start
	if isBadVersion(end):
		return end
	return -1

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int firstBadVersion(int n) {
	int start = 1, end = n;
	while(start + 1 < end) {
		int mid = start + (end - start) / 2;
		if(isBadVersion(mid)) 
			end = mid;
		else 
			start = mid;
	}
	if(isBadVersion(start))
		return start;
	else
		return end;
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

Input: pattern = “abab”, s = “redblueredblue”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “red”
‘b’ -> “blue”


Example 2:

Input: pattern = “aaaa”, s = “asdasdasdasd”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “asd”


Example 3:

Input: pattern = “abab”, s = “asdasdasdasd”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “a”
‘b’ -> “sdasd”
Note that ‘a’ and ‘b’ cannot both map to “asd” since the mapping is a bijection.


Example 4:

Input: pattern = “aabb”, s = “xyzabcxzyabc”
Output: false


Constraints:

1 <= pattern.length, s.length <= 20 pattern and s consist of only lower-case English letters.

算法思路：

类似于word break，但由于要存储处理过map和set，DP不能处理，所以只能用DFS

注意事项：

  1. 比较映射，用Map比较A->B的映射，如已有a->dog, 另一对映射a->cat通过查找Map知道不合法。B->A的映射可通过将map的所有value存到一个set中知道。如a->dog, b->dog. b不在Map中但b对应的dog在set中，不合法。
    DFS的API为dfs(pattern, word, pattern_to_word, used_set)
  2. 若pattern的字母出现过，如aba，不应进入循环，更不应该加入到map和set中，应该用startswith比较word判断是否合法，若是，直接下一轮DFS(Line 11 -15)
  3. 1中的两情况的第一种情况以及第二种情况的前半部分(b不在map中)在2中已经处理，所以只要在循环中处理第二种情况后半部分(b对应的dog在set中)即可(Line 22 - 23)

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 wordPatternMatch(self, pattern: str, s: str) -> bool:
	if not pattern or not s:
		return False
	return self.dfs(pattern, s, 0, 0, {}, set())

def dfs(self, pattern, s, start_p, start_s, pattern_to_s, s_set):
	if start_p >= len(pattern) and start_s >= len(s):
		return True
	if start_p >= len(pattern) or start_s >= len(s):
		return False
	char = pattern[start_p]
	if char in pattern_to_s:
		word = pattern_to_s[char]
		if not s[start_s:].startswith(word):
			return False
		return self.dfs(pattern, s, start_p + 1, start_s + len(word), pattern_to_s, s_set)
		
	for j in range(start_s, len(s)):
		matched_word = s[start_s:j + 1]
		'''if char in pattern_to_s and pattern_to_s[char] != matched_word:
			continue
		if char not in pattern_to_s and matched_word in s_set:  # remembers
			continue'''
		if matched_word in s_set:
			continue
		pattern_to_s[char] = matched_word
		s_set.add(matched_word)
		if self.dfs(pattern, s, start_p + 1, j + 1, pattern_to_s, s_set):
			return True
		s_set.remove(matched_word)
		pattern_to_s.pop(char)
	return False

算法分析：

时间复杂度为O(解大小)，空间复杂度为O(解大小)。

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
27
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).

Posted on Edited on Disqus:

LeetCode



Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

Any left parenthesis '(' must have a corresponding right parenthesis ')'. Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = “()”
Output: true


Example 2:

Input: s = “()”
Output: true


Example 3:

Input: s = “())”
Output: true


Constraints:

1 <= s.length <= 100 s[i] is '(', ')' or '*'.

题目大意：

求给定字符串带星号是否合法括号配对。

Stack算法思路(推荐)：

括号题优先考虑用Stack。如果不带星号，回忆合法括号题，有三种不合法情况，此题只需考虑两种，不需考虑多种括号类型
三种不合法情况： ‘[‘ (stack有余), ‘]’ (要匹配的时候stack为空)
难点：

  1. 在于要去想多一个栈来存星号，因为星号可以作为左括号备选去match右括号。右括号在两个栈中优先配对左括号，星号可以为空。如果两个栈均为空，处理了第一种不合法情况
  2. 循环后，如果两栈有余，分4中情况讨论：
    1) 左括号栈有余星号栈空，正是第二种不合法情况
    2) 左括号栈空星号栈空，合法
    3) 左括号栈空星号栈有余，合法，星号可为空
    4) 都有余，这是难点二。星号可以作为右括号去配对左括号，前提条件是星号在左括号之后，考虑*(，这是不合法

注意事项：

  1. 如果for循环出来后，两栈不为空，要比较先后顺序
  2. for loop后，L18 - Line 19记得pop，否则死循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def checkValidString(self, s: str) -> bool:
	stack_left, stack_star = [], []
	for i in range(len(s)):
		if s[i] == '(':
			stack_left.append(i)
		if s[i] == '*':
			stack_star.append(i)
		if s[i] == ')':
			if stack_left:  # match ( first rather than * because * can be empty
				stack_left.pop()
			elif stack_star:
				stack_star.pop()
			else:
				return False
	while stack_left and stack_star:  # use * to match (
		if stack_left[-1] > stack_star[-1]:  # consider *(
			return False
		stack_left.pop()
		stack_star.pop()
	return len(stack_left) == 0  # stack_star can be non empty

算法分析：

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

统计算法II解题思路：

括号题另一个常用思路是用统计左右括号数。此题较难想到是用一个左括号数量范围去验证。
lo为左括号的最少合法个数，hi为左括号的最大合法个数，有范围是因为星号可以变成左右括号或空。
遇到左括号，都加1，遇到右括号，都减1，遇到星号，假设星号为右括号，所以lo减1，hi加1.
如果hi小于0，表示最大左括号数小于右括号数，不满足此法的规则一，不合法

难点在于lo设为非负。因为lo是最少且合法，合法意思是lo不是单纯地将所有星号变成右括号，而是当左括号不足时，用提高下限，将星号变成空，体现在令lo为非负。
for循环后，lo必须为0，运用了法则二，左右括号相等。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def checkValidString(self, s: str) -> bool:
	lo = hi = 0
	for char in s:
		if char == '(':
			lo += 1
			hi += 1
		if char == '*':
			if lo > 0:  # treat * as empty space
				lo -= 1
			hi += 1
		if char == ')':
			if lo > 0:  # treat the previous * as empty space
				lo -= 1
			hi -= 1
		if hi < 0:  # the num of right parenthesis > left ones
			return False
	return lo == 0  # the num of right parenthesis should equal to left ones

算法分析：

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

DP算法III解题思路：

基本情况为s[i], s[j] 分别在(*, )* 就合法
如果用单边DP，并不能确定区间内那些合法，所以只能用区间型DP
dp[i][j] = s[i-1] == ‘*‘ and dp[i+1][j] 星号不匹配
= s[i-1] in ‘(*‘ and dp[i+1][k-1] and s[k-1] in (‘)*‘) and dp[k+1][j] 星号匹配

具体参考leetcode答案
DP基本情况比较难想出来且递归是复杂，实现易错，不推荐。不过可以多了解区间型DP的模式

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x<sub>1</sub> - x<sub>2</sub>)<sup>2</sup> + (y<sub>1</sub> - y<sub>2</sub>)<sup>2</sup>).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:



Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].


Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.


Constraints:

1 <= k <= points.length <= 10<sup>4</sup> -10<sup>4</sup> < x<sub>i</sub>, y<sub>i</sub> < 10<sup>4</sup>

算法思路：

最大堆

注意事项：

  1. 求最小距离用最大堆，距离的相反数入堆
  2. 与堆顶比较，跟模板一样仍然是大于号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
	if not points or not points[0]:
		return 0
	heap, res = [], []
	for i in range(len(points)):
		x, y = points[i][0], points[i][1] # x=-2, y=2
		if i < k: # i=1, k=1
			heapq.heappush(heap, (-(x * x + y * y), x, y)) # -10, 1, 3
		elif -(x * x + y * y) > heap[0][0]: # -8 > -10
			heapq.heapreplace(heap, (-(x * x + y * y), x, y)) # -8, -2, -2

	while heap:
		(dis, x, y) = heapq.heappop(heap) # -8, -2, -2
		res.append([x, y])
	return res

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
public int[][] kClosest(int[][] points, int K) {
	PriorityQueue<Point> maxHeap = new PriorityQueue<Point>(K,
			new Comparator<Point>() {
				@Override
				public int compare(Point o1, Point o2) {
					return distance(o2, o1); // descending
				}
			}
	);
	
	for(int i = 0; i < points.length; i++) {
		Point p = new Point(points[i][0], points[i][1]);
		if(maxHeap.size() < K)
			maxHeap.offer(p);
		else if(distance(p, maxHeap.peek()) < 0) {
			maxHeap.poll();
			maxHeap.offer(p);
		}
	}
	int[][] res = new int[K][2];
	int j = 0;
	while(!maxHeap.isEmpty()) {
		Point p = maxHeap.poll();
		res[j][0] = p.x;
		res[j][1] = p.y;
		j++;
	}
	return res;
}

int distance(Point o1, Point o2) {
	return (o1.x * o1.x + o1.y * o1.y) - (o2.x * o2.x + o2.y * o2.y);
}

class Point {
	 int x;
	 int y;
	 Point() { x = 0; y = 0; }
	 Point(int a, int b) { x = a; y = b; }
}

算法分析：

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

Free mock interview