KK's blog

LeetCode 009 Palindrome Number

Posted on 2021-12-22 Disqus:

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints: -2<sup>31</sup> <= x <= 2<sup>31</sup> - 1

Follow up: Could you solve it without converting the integer to a string?

题目大意：

判断是否回文数字

解题思路：

N/A

解题步骤：

N/A

注意事项：

Python代码：

1 2	def isPalindrome(self, x: int) -> bool: return str(x) == str(x)[::-1]

算法分析：

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

算法II解题思路：

Follow-up 不能用str，就求它的reversed数

注意事项：

x是用于计算过程，所以不断变化，最后一行不能用它来与reversed的结果比较

Python代码：

def isPalindrome2(self, x: int) -> bool:
	if x < 0:
		return False
	rev, original = 0, x
	while x > 0:
		rev = rev * 10 + x % 10 # 121
		x = x // 10 # 1
	return rev == original

算法分析：

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

LeetCode 021 Merge Two Sorted Lists

Posted on 2021-12-22 Disqus:

LeetCode

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50]. -100 <= Node.val <= 100
Both list1 and list2 are sorted in *non-decreasing order.

题目大意：

合并两个LL

解题思路：

N/A

解题步骤：

N/A

注意事项：

Fake Node的引入

Python代码：

def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
	fake_head = ListNode(0)
	it, it2, it_res = list1, list2, fake_head
	while it and it2:
		if it.val <= it2.val:
			it_res.next = it
			it = it.next
			it_res = it_res.next
		else:
			it_res.next = it2
			it2 = it2.next
			it_res = it_res.next
	if it:
		it_res.next = it
	if it2:
		it_res.next = it2
	return fake_head.next

算法分析：

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

LeetCode 174 Dungeon Game

Posted on 2021-12-22 Edited on 2022-01-31 Disqus:

LeetCode

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight’s health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Return the knight’s minimum initial health so that he can rescue the princess.

Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]
Output: 1

Constraints:

m == dungeon.length n == dungeon[i].length
1 <= m, n <= 200 -1000 <= dungeon[i][j] <= 1000

题目大意：

保持正数健康值从左上走到右下

DP解题思路(推荐)：

坐标型DP。
dp[n][m]为通过这一格前的最小健康值，也就是题目所求，这意味着需要保证通过最后一个后的健康值为1，所以引入它相邻的两个cell为1
递归式为：

1 2	dp[n][m] = -dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0 = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]} if dungeon[n][m] > 0

由于-dungeon[n][m] + min(dp[n+1][m]一定为正数，所以可以归并两种情况：

1	dp[n][m] = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]}

解题步骤：

N/A

注意事项：

从右下走回左上倒推初始值。每一格的最小健康值在为1，而初始健康值也最小为1.
递归式：一开始的递归式跟下和右格的极小值有关，所以DP数组(比原数组多出的)最右和最下边界初始值为正无穷；但根据公式，右下格会出现正无穷，所以需要特别处理，将右下格的相邻下右两格初始为1，可以这样理解，从右下格走出健康值必须是1
递归式：一开始写若该格dungeon值为负数，1 - dungeon[n][m] + min(dp[n+1][m], dp[n][m+1])这个1的确保证了最小健康值为1，但其实它只要加一次，而上述右下边界已经处理，所以递归式不需要+1，如[[-2, -3]], dp[0][1]=4, 而dp[0][0]为6即可
递归式：当dungeon为正数时，可以抵消它相邻格所要求的最低健康值，当然要保证健康值大于1，如[5, 4, -2], dp[0][0] = 1

Python代码：

# dp[n][m] = 1 - dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0
#          = 1 + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] > 0
# dp[n][m] = -dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0
#          = min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] > 0
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
	dp = [[float('inf') for _ in range(len(dungeon[0]) + 1)] for _ in range(len(dungeon) + 1)]
	dp[-1][-2] = dp[-2][-1] = 1
	for i in reversed(range(len(dungeon))):
		for j in reversed(range(len(dungeon[0]))):
			'''
			min_neighbor = float('inf')
			if i + 1 < len(dungeon):
				min_neighbor = min(min_neighbor, dp[i + 1][j])
			if j + 1 < len(dungeon[0]):
				min_neighbor = min(min_neighbor, dp[i][j + 1])
			if min_neighbor == float('inf'):
				min_neighbor = 0

			if dungeon[i][j] < 0:
				dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
			else:
				dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
			'''
			dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
	return dp[0][0]

算法分析：

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

Binary select算法II解题思路：

Binary select + DP
暴力法，假设某个初始健康值，然后用从左到右从上到下计算这一格后的健康值，dp[m][n] = max{dp[m-1][n], dp[m][n-1]} + dungeon[r][c], 可以看出dp定义和递归式max都是跟上述方法相反。求最后一个是否正数
暴力法是O(n^2), 而用binary select试0, 1000 * (m + n) + 1，1000是cell的最大值，m+n是路径长度，1是最小健康值，二分法试每个数值

参考https://leetcode.com/problems/dungeon-game/discuss/1498367

算法分析：

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

LeetCode 013 Roman to Integer

Posted on 2021-12-21 Disqus:

LeetCode

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

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

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:

Input: s = “III”
Output: 3
Explanation: III = 3.

Example 2:

Input: s = “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

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].

题目大意：

罗马数组转阿拉伯数字

解题思路：

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

解题步骤：

N/A

注意事项：

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

Python代码：

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 1570 Dot Product of Two Sparse Vectors

Posted on 2021-12-21 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代码：

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代码：

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