KK's blog

LeetCode 256 Paint House

Posted on 2022-01-19 Edited on 2026-06-03 Disqus:

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:

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.

Example 2:

Input: costs = [[7,6,2]]
Output: 2

Constraints: costs.length == n
costs[i].length == 3 1 <= n <= 100
* 1 <= costs[i][j] <= 20

题目大意：

排屋相邻不同色地涂色(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

注意事项：

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

Python代码：

# 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 266 Palindrome Permutation

Posted on 2022-01-19 Edited on 2026-06-03 Disqus:

LeetCode

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

Example 1:

Input: s = “code”
Output: false

Example 2:

Input: s = “aab”
Output: true

Example 3:

Input: s = “carerac”
Output: true

Constraints:

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

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

统计字符频率，奇数频率的字符最多有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)

LeetCode 270 Closest Binary Search Tree Value

Posted on 2022-01-19 Edited on 2026-06-03 Disqus:

LeetCode

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

Constraints: The number of nodes in the tree is in the range [1, 104]. 0 <= Node.val <= 109 * -109 <= target <= 109

题目大意：

求BST中最接近target的值

解题思路：

接近target的值在BST搜索路径上，越后搜索到的(越后入栈的)越接近，但最接近的可能大于或小于target(predecessors or successors)，只能逐一比较.
类似于LeetCode 272 Closest Binary Search Tree Value II

解题步骤：

N/A

注意事项：

循环中用it，不能用root，注意检查
接近target的值在BST搜索路径上，逐一比较

Python代码：

def closestValue(self, root: TreeNode, target: float) -> int:
	closest_vals = []
	it = root
	while it:
		closest_vals.append(it.val)
		if target < it.val:
			it = it.left
		else:
			it = it.right
	min_val, res = float('inf'), 0
	for n in closest_vals:
		if abs(target - n) < min_val:
			min_val = abs(target - n)
			res = n
	return res

算法分析：

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

LeetCode 277 Find the Celebrity

Posted on 2022-01-19 Edited on 2026-06-03 Disqus:

LeetCode

Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is ask questions like: “Hi, A. Do you know B?” to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) that tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party.

Return the celebrity’s label if there is a celebrity at the party. If there is no celebrity, return -1.

Example 1:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

Example 2:

Input: graph = [[1,0,1],[1,1,0],[0,1,1]]
Output: -1
Explanation: There is no celebrity.

Constraints:

n == graph.length n == graph[i].length
2 <= n <= 100 graph[i][j] is 0 or 1.
graph[i][i] == 1

Follow up: If the maximum number of allowed calls to the API knows is `3 n`, could you find a solution without exceeding the maximum number of calls?

题目大意：

通过调用a是否认识b函数，找出名人。名人是除自己的所有人都认识他，他不认识其他所有人

解题思路：

类似于LeetCode 169 Majority Element，用水王法

解题步骤：

找出可能名人，通过查看是否i后面的每一个人都认识i，若不是将candidate换成当前下标
按定义验证第一步的结果是否名人，两步验证

注意事项：

按照定义，若i不认识candiate才换candidate，用not。因为edge case是没有边或者图存在循环
验证时候，第二步验证candidate若认识任意人就不是名人，排除candidate认识自己。题目条件candidate认识自己。

Python代码：

def findCelebrity(self, n: int) -> int:
	# find potential candidate
	candidate = 0
	for i in range(1, n):
		if not knows(i, candidate):
			candidate = i
	# validate
	for i in range(n):
		if not knows(i, candidate):
			return -1
	for i in range(n):
		if candidate != i and knows(candidate, i):
			return -1
	return candidate

算法分析：

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

LeetCode 268 Missing Number

Posted on 2022-01-19 Edited on 2026-06-03 Disqus:

LeetCode

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

n == nums.length 1 <= n <= 104
0 <= nums[i] <= n All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

题目大意：

数组缺失一个数，所有数应该在[0, n]内，求缺失数

排序法解题思路：

N/A

解题步骤：

N/A

注意事项：

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(nlogn)，空间复杂度O(1)

异或法解题思路II：

高斯原理

Python代码：

def missingNumber2(self, nums: List[int]) -> int:
	res = len(nums) # remember
	for i, n in enumerate(nums):
		res ^= i ^ n
	return res

算法分析：

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

数学法解题思路III：

高斯原理

Python代码：

1
2
3

def missingNumber3(self, nums: List[int]) -> int:
	n = len(nums)
	return (0 + n) * (n + 1) // 2 - sum(nums)

算法分析：

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