KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given two sparse vectors, compute their dot product.

Implement class SparseVector:

SparseVector(nums) Initializes the object with the vector nums dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 10 + 03 + 00 + 24 + 30 = 8


Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 00 + 10 + 00 + 00 + 02 = 0


Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6


Constraints:

n == nums1.length == nums2.length 1 <= n <= 10^5
* 0 <= nums1[i], nums2[i] <= 100

题目大意：

稀疏数组乘法，设计类来存储且计算乘积

HashMap解题思路：

类似于Two sum，也是两种方法。HashMap的方法由于hash函数计算容易冲突，所以算法复杂度不够稳定。

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SparseVector(TestCases):

    def __init__(self, nums: List[int]):
        self.idx_to_num = collections.defaultdict(int)
        for i, n in enumerate(nums):
            if n > 0:
                self.idx_to_num[i] = n

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        res = 0
        for i, n in vec.idx_to_num.items():
            if i in self.idx_to_num:
                res += self.idx_to_num[i] * n
        return res

算法分析：

创建时间复杂度为O(n)，计算时间复杂度为O(L)，空间复杂度O(L)，L为非0元素个数

Mergesort算法II解题思路：

初始化复杂度比较稳定

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class SparseVector(TestCases):

    def __init__(self, nums: List[int]):
        self.non_zero_list = []
        for i, n in enumerate(nums):
            if n > 0:
                self.non_zero_list.append((i,n))

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        i, j, res = 0, 0, 0
        while i <= len(self.non_zero_list) - 1 and j <= len(vec.non_zero_list) - 1:
            if self.non_zero_list[i][0] == vec.non_zero_list[j][0]:
                res += self.non_zero_list[i][1] * vec.non_zero_list[j][1]
                i += 1
                j += 1
            elif self.non_zero_list[i][0] < vec.non_zero_list[j][0]:
                i += 1
            else:
                j += 1
        return res

算法分析：

创建时间复杂度为O(n)，计算时间复杂度为O(L1 + L2)，空间复杂度O(L)，L为非0元素个数

Posted on Edited on Disqus:

LeetCode



You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i<sup>th</sup> line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:



Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.


Example 2:

Input: height = [1,1]
Output: 1


Constraints:

n == height.length 2 <= n <= 10<sup>5</sup>
* 0 <= height[i] <= 10<sup>4</sup>

题目大意：

求两板之间的最大水量

解题思路：

贪婪法，求面积，然后移动矮的那条边

解题步骤：

N/A

注意事项：

  1. 贪婪法，求面积，然后移动矮的那条边

Python代码：

1
2
3
4
5
6
7
8
9
10
def maxArea(self, height: List[int]) -> int:
	res = 0
	i, j = 0, len(height) - 1
	while i < j:
		res = max(res, min(height[i], height[j]) * (j - i))
		if height[i] < height[j]:
			i += 1
		else:
			j -= 1
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:



Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job.
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.


Example 2:



Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job.
Profit obtained 150 = 20 + 70 + 60.


Example 3:



Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6


Constraints:

`1 <= startTime.length == endTime.length == profit.length <= 5 104*1 <= startTime[i] < endTime[i] <= 109*1 <= profit[i] <= 104`

算法思路：

DP + 排序
一开始以为类似于meeting rooms II，所以用heap，但只能计算conflicts不能计算profits，但排序思想有用。
求最值问题第一时间考虑用DP，所以考虑以第i-1个job为结尾的最大利润： 


dp[i] = max -> dp[j] + profits[i-1]), 第i个job的startTime[i-1] >= endTime[j], 第j个job与第i个job没有conflicts
            -> dp[j]                                                          第j个job与第i个job有conflicts

复杂度为O(n^2)

写出递归式后，求startTime >= endTime其实就是按endTime排序，这样有助于搜索这个条件. 这里有个难点是要加强命题至累计利润，因为正如Cooldown股票题一样，dp[j]不应该是以job j为结尾的最大利润，而应该是前j个job的最大利润，这些job不一定都是相邻
加强命题dp[i]是累计利润，也就是并不需要计算所有dp[j…i]的值（第一式子），公式变成 


dp[i] = max -> dp[j] + profits[i-1]), j = start[i-1]对应的Endtime下标, 第j个job与第i个job没有conflicts
            -> dp[j]                                                   第j个job与第i个job有conflicts

要找出这个j，就对刚才排序了的endtime数组用bisect找下标。类似于LIS, 复杂度为O(nlogn)

注意事项：

  1. bisect的使用求大于startTime的endTime下标，此下标j减一正是所求，但dp和数组中下标转换是差1，所以dp[j - 1 + 1]是前值的DP值。
  2. 加强命题至累计利润dp[i], 见line 9 - 10

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
	job_by_endtime, dp, max_profit = [], [0] * (len(startTime) + 1), 0
	for i in range(len(startTime)):
		job_by_endtime.append((endTime[i], startTime[i], profit[i]))
	job_by_endtime.sort()
	end_time_sorted = [pair[0] for pair in job_by_endtime]
	for i in range(1, len(dp)):
		j = bisect.bisect(end_time_sorted, job_by_endtime[i - 1][1]) # previous end time <= current start time
		dp[i] = max(max_profit, dp[j] + job_by_endtime[i - 1][2]) # remember
		max_profit = max(max_profit, dp[i]) # remember
	return dp[-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3. For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object. void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10<sup>-5</sup> of the actual answer will be accepted.

Example 1:

Input
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0


Constraints: -10<sup>5</sup> <= num <= 10<sup>5</sup>
There will be at least one element in the data structure before calling findMedian. At most 5 * 10<sup>4</sup> calls will be made to addNum and findMedian.

Follow up:

If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

题目大意：

求动态中位数

算法思路：

用max_heap, min_heap, 保证min_heap个数永远等于max_heap或多一个。插入元素先进max_heap, 再heappop将堆顶元素加入min_heap, 若此时比max_heap多2个，就再heappop加入到max_heap.

注意事项：

  1. 中位数有1-2个
  2. Python中的max_heap用负数实现，入堆出堆都要取反

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MedianFinder(TestCases):

    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.max_heap, -num)
        max_value = -heapq.heappop(self.max_heap)
        heapq.heappush(self.min_heap, max_value)
        if len(self.min_heap) - len(self.max_heap) >= 2:
            min_value = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -min_value)

    def findMedian(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return self.min_heap[0]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group’s length is 1, append the character to s. Otherwise, append the character followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”2”,”b”,”2”,”c”,”3”]
Explanation: The groups are “aa”, “bb”, and “ccc”. This compresses to “a2b2c3”.


Example 2:

Input: chars = [“a”]
Output: Return 1, and the first character of the input array should be: [“a”]
Explanation: The only group is “a”, which remains uncompressed since it’s a single character.


Example 3:

Input: chars = [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”]
Output: Return 4, and the first 4 characters of the input array should be: [“a”,”b”,”1”,”2”].
Explanation: The groups are “a” and “bbbbbbbbbbbb”. This compresses to “ab12”.


Example 4:

Input: chars = [“a”,”a”,”a”,”b”,”b”,”a”,”a”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”3”,”b”,”2”,”a”,”2”].
Explanation: The groups are “aaa”, “bb”, and “aa”. This compresses to “a3b2a2”. Note that each group is independent even if two groups have the same character.


Constraints:

1 <= chars.length <= 2000 chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

题目大意：

相邻相同字母用数字压缩

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 题目要求，如果是超过10，也要将这个数按多个字符populate到原数组，见populate_count的实现，用字符串处理
  2. 在循环外处理最后一部分

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def compress(self, chars: List[str]) -> int:
	res, count = 1, 1
	for i in range(1, len(chars)):
		if chars[i - 1] == chars[i]:
			count += 1
		else:
			if count > 1:
				res = self.populate_count(chars, res, count)
			count = 1
			chars[res] = chars[i]
			res += 1
	if count > 1:
		res = self.populate_count(chars, res, count)
	return res

def populate_count(self, chars, res, count):
	num_str = str(count)
	chars[res:res + len(num_str)] = [c for c in num_str]
	res += len(num_str)
	return res

算法分析：

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

Free mock interview