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



There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that you must take course b<sub>i</sub> first if you want to take course a<sub>i</sub>.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].


Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].


Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]


Constraints: 1 <= numCourses <= 2000
`0 <= prerequisites.length <= numCourses (numCourses - 1)*prerequisites[i].length == 2*0 <= ai, bi < numCourses*ai != bi* All the pairs[ai, bi]` are distinct.

题目大意：

课程有先修课要求，求修课的顺序

算法思路：

拓扑排序的经典题

注意事项：

  1. 注意题目要求课程可能存在循环，记得第四部侦测循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
	in_degree = [0] * numCourses
	graph = [[] for _ in range(numCourses)]
	for li in prerequisites:
		in_degree[li[0]] += 1
		graph[li[1]].append(li[0])
	queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 0])
	res = []
	while queue:
		node = queue.popleft()
		res.append(node)
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	return res if numCourses == len(res) else []

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
public int[] findOrder(int numCourses, int[][] prerequisites) {
	ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> res = new ArrayList<>();
	for(int i=0;i<numCourses;i++)
		graph.add(new ArrayList<Integer>());
	int[] inDegree = new int[numCourses];
	//populate inDegree & convert to graph
	for(int i=0;i<prerequisites.length;i++){
		//[0,1] means 1->0
		inDegree[prerequisites[i][0]]++;
		graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
	}
	Queue<Integer> q = new LinkedList<Integer>();
	for(int i=0;i<inDegree.length;i++){
		if(inDegree[i]==0)
			q.offer(i);
	}
	int count = 0;
	while(!q.isEmpty()){
		Integer v = q.poll();
		res.add(v);
		count++;
		for(int neighbor : graph.get(v)){
			if(--inDegree[neighbor]==0)
				q.add(neighbor);
		}
	}
	if(count != numCourses)
		res.clear();

	return res.stream().mapToInt(i->i).toArray();
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.


Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.


Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 400

算法思路：

N/A

注意事项：

  1. 循环不是模板中的1开始，而是从2开始，因为i-2>=0

Python代码：

1
2
3
4
5
6
def rob(self, nums: List[int]) -> int:
	dp = [0] * (len(nums) + 1)
	dp[1] = nums[0]
	for i in range(2, len(dp)):
		dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
	return dp[-1]

算法分析：

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

Posted on Edited on Disqus:

算法思路：

left is left pointer, i is right pointer

求最短串

Python代码：

1
2
3
4
5
6
7
8
def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <meets condition>:
			res = min(res, i - left + 1)
			<anti-calculate condition such as char_to_count>
			left += 1
	return <result>

求最长串

Python代码：

1
2
3
4
5
6
7
8
def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <does not meet condition>:
			<anti-calculate condition such as char_to_count>
			left += 1
		res = max(res, i - left + 1)
	return <result>

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.


Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1


Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0


Constraints:

1 <= target <= 10<sup>9</sup> 1 <= nums.length <= 10<sup>5</sup>
1 <= nums[i] <= 10<sup>5</sup>

*Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

算法思路：

N/A

注意事项：

  1. 求最小值，所以min_len初始化最大值
  2. 长度为i - j + 1写例子来计算

Python代码：

1
2
3
4
5
6
7
8
9
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
	min_len, num_sum, left = float('inf'), 0, 0
	for i in range(len(nums)):
		num_sum += nums[i]
		while num_sum >= target:
			min_len = min(min_len, i - left + 1)
			num_sum -= nums[left]
			left += 1
	return 0 if min_len == float('inf') else min_len

算法分析：

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

Free mock interview