KK's blog

LeetCode

<div>

Given a 2D matrix matrix, handle multiple queries of the following type:

• Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

• NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
• int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example 1:

<pre>Input ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]] Output [null, 8, 11, 12]

Explanation NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle) </pre>

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -10<sup>5</sup> <= matrix[i][j] <= 10<sup>5</sup>
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• At most 10<sup>4</sup> calls will be made to sumRegion.

</div>

题目大意：

求子矩阵和

解题思路：

计算presum公式:

1

dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j] - dp[i-1][j-1]

计算子矩阵公式：

1

res = presum[x][y] - left - top + diag

解题步骤：

N/A

注意事项：

1. dp有左上边界，计算子矩阵注意dp和输入差1

Python代码：

1
2
3
4
5
6
7
8
9
10

class NumMatrix(TestCases):

    def __init__(self, matrix: List[List[int]]):
        self.dp = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
        for i in range(1, len(self.dp)):
            for j in range(1, len(self.dp[0])):
                self.dp[i][j] = matrix[i - 1][j - 1] + self.dp[i - 1][j] + self.dp[i][j - 1] - self.dp[i - 1][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.dp[row2 + 1][col2 + 1] - self.dp[row2 + 1][col1] - self.dp[row1][col2 + 1] + self.dp[row1][col1]

算法分析：

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

LeetCode

<div>

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

<pre>Input: nums = [1,3,4,2,2] Output: 2 </pre>

Example 2:

<pre>Input: nums = [3,1,3,4,2] Output: 3 </pre>

Constraints:

• 1 <= n <= 10<sup>5</sup>
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

</div>

题目大意：

给定数值范围[1, n]找重复的数，只有一个重复数，但可能重复多次。题目要求不能用额外空间，不能修改数组

解题思路：

数值二分法

解题步骤：

N/A

注意事项：

1. 比较mid和count的关系，用例子来写程序，如[1, 2, 2, 3, 4]
2. 重复的数可能重复多次，所以不能用异或法

Python代码：

1
2
3
4
5
6
7
8
9
10

def findDuplicate(self, nums: List[int]) -> int:
	start, end, epsilon = min(nums), max(nums), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = len([n for n in nums if n <= mid])
		if count <= mid:
			start = mid
		else:
			end = mid
	return int(end)

算法分析：

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

LeetCode

<div>

You are given an m x n grid rooms initialized with these three possible values.

• -1 A wall or an obstacle.
• 0 A gate.
• INF Infinity means an empty room. We use the value 2<sup>31</sup> - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:

<pre>Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]] Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]] </pre>

Example 2:

<pre>Input: rooms = [[-1]] Output: [[-1]] </pre>

Constraints:

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 2<sup>31</sup> - 1.

</div>

题目大意：

求所有房间到门的最短距离

解题思路：

属于多始点BFS类型

解题步骤：

N/A

注意事项：

1. 门的距离不更新，所以出列后要判断该点是否为门，不是用距离来判断

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

OFFSET = [(-1, 0), (1, 0), (0, 1), (0, -1)]
class Solution(TestCases):

    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        gates = []
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0:
                    gates.append((i, j, 0))
        queue = collections.deque(gates)
        visited = set(gates)
        while queue:
            x, y, distance = queue.popleft()
            if rooms[x][y] != 0: # not distance != 0
                rooms[x][y] = distance
            for _dx, _dy in OFFSET:
                _x, _y = x + _dx, y + _dy
                if _x < 0 or _x >= len(rooms) or _y < 0 or _y >= len(rooms[0]) or \
                        rooms[_x][_y] == -1 or (_x, _y) in visited:
                    continue
                queue.append((_x, _y, distance + 1))
                visited.add((_x, _y))

算法分析：

时间复杂度为O(nm)，空间复杂度O(mn)

LeetCode

<div>

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

• For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

Example 1:

<pre>Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10. </pre>

Example 2:

<pre>Input: costs = [[7,6,2]] Output: 2 </pre>

Constraints:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

</div>

题目大意：

排屋相邻不同色地涂色(3色)的最低成本

解题思路：

低频题。最值且涉及数值考虑用DP。由于相邻不能同色，所以是多状态DP，有3个状态，不妨多用一维表示，第二维只有3值。 dp[i][j]定义为第i间屋涂上第j色的最低总费用，递归式为

1

dp[i][j] = min(dp[i-1][(j+1)%3] + costs[i-1][j], dp[i-1][(j+2)%3] + costs[i-1][j])

解题步骤：

N/A

注意事项：

1. 递归5步曲，多1，初始，多1，少1，答案。记得第一步初始化数组多1

Python代码：

1
2
3
4
5
6
7

# dp[i][j] = min(dp[i-1][(j+1)%3] + costs[i-1][j], dp[i-1][(j+2)%3] + costs[i-1][j])
def minCost(self, costs: List[List[int]]) -> int:
	dp = [[0] * 3 for _ in range(len(costs) + 1)]
	for i in range(1, len(dp)):
		for j in range(3):
			dp[i][j] = min(dp[i - 1][(j + 1) % 3] + costs[i - 1][j], dp[i - 1][(j + 2) % 3] + costs[i - 1][j])
	return min(dp[-1][0], dp[-1][1], dp[-1][2])

算法分析：

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

LeetCode

<div>

Given a string s, return true if a permutation of the string could form a palindrome.

Example 1:

<pre>Input: s = "code" Output: false </pre>

Example 2:

<pre>Input: s = "aab" Output: true </pre>

Example 3:

<pre>Input: s = "carerac" Output: true </pre>

Constraints:

• 1 <= s.length <= 5000
• s consists of only lowercase English letters.

</div>

题目大意：

字符串的任一全排列是否存在回文字符串

解题思路：

数学题，也就是统计字符频率，奇数频率的字符最多有1个

解题步骤：

N/A

注意事项：

1. 统计字符频率，奇数频率的字符最多有1个

Python代码：

1
2
3

def canPermutePalindrome(self, s: str) -> bool:
	char_to_count = collections.Counter(s)
	return False if len([count for count in char_to_count.values() if count % 2 == 1]) > 1 else True

算法分析：

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