KK's blog

LeetCode

<div>

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

<pre>Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000</pre>

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

<pre>Input: s = "III" Output: 3 Explanation: III = 3. </pre>

Example 2:

<pre>Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3. </pre>

Example 3:

<pre>Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4. </pre>

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

</div>

题目大意：

罗马数组转阿拉伯数字

解题思路：

按照规则累加。有一个特别规则是需要做减法如IV。

解题步骤：

N/A

注意事项：

1. 先加再减的方法。
2. SYMBOL_TO_VAL的值可以哟用于判断先后顺序。

Python代码：

1
2
3
4
5
6
7
8
9
10

def romanToInt(self, s: str) -> int:
	SYMBOL_TO_VAL = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	res, num, prev = 0, 0, ''
	for symbol in s:
		num = SYMBOL_TO_VAL[symbol]
		if prev and SYMBOL_TO_VAL[prev] < SYMBOL_TO_VAL[symbol]:
			res -= SYMBOL_TO_VAL[prev] * 2
		res += num
		prev = symbol
	return res

算法分析：

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

LeetCode

<div>

Implement pow(x, n), which calculates x raised to the power n (i.e., x<sup>n</sup>).

Example 1:

<pre>Input: x = 2.00000, n = 10 Output: 1024.00000 </pre>

Example 2:

<pre>Input: x = 2.10000, n = 3 Output: 9.26100 </pre>

Example 3:

<pre>Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2^-2 = 1/2² = 1/4 = 0.25 </pre>

Constraints:

• -100.0 < x < 100.0
• -2<sup>31</sup> <= n <= 2<sup>31</sup>-1
• -10<sup>4</sup> <= x<sup>n</sup> <= 10<sup>4</sup>

</div>

题目大意：

求幂

解题思路：

DFS

解题步骤：

N/A

注意事项：

1. 保存dfs(x, n/2)的临时结果，避免重复计算
2. n可以是0，负数

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def myPow(self, x: float, n: int) -> float:
	if n >= 0:
		return self.dfs(x, n)
	else:
		return self.dfs(1 / x, -n)

def dfs(self, x, n):
	if n == 0:
		return 1
	if n == 1:
		return x
	if n % 2 == 0:
		tmp = self.dfs(x, n / 2)
		return tmp * tmp
	else:
		tmp = self.dfs(x, (n - 1) / 2)
		return tmp * tmp * x

算法分析：

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

LeetCode

<div>

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:

<pre>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 + 3*0 = 8 </pre>

Example 2:

<pre>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 + 0*2 = 0 </pre>

Example 3:

<pre>Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4] Output: 6 </pre>

Constraints:

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

</div>

题目大意：

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

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元素个数

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>Input: height = [1,1] Output: 1 </pre>

Constraints:

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

</div>

题目大意：

求两板之间的最大水量

解题思路：

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

解题步骤：

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)

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>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. </pre>

Example 3:

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

Constraints:

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10<sup>4</sup>
• 1 <= startTime[i] < endTime[i] <= 10<sup>9</sup>
• 1 <= profit[i] <= 10<sup>4</sup>

</div>

算法思路：

DP + 排序
一开始以为类似于meeting rooms II，所以用heap，但只能计算conflicts不能计算profits，但排序思想有用。
求最值问题第一时间考虑用DP，所以考虑以第i-1个job为结尾的最大利润：
<pre> 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
</pre> 复杂度为O(n^2)

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