KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



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:

Input: nums = [1,3,4,2,2]
Output: 2


Example 2:

Input: nums = [3,1,3,4,2]
Output: 3


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?

题目大意：

给定数值范围[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)

Posted on Edited on Disqus:

LeetCode



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

注意事项：

  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)

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

Posted on Edited on 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 <= 10<sup>4</sup>
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

注意事项：

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

异或法解题思路II：

高斯原理

Python代码：

1
2
3
4
5
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)

Posted on Edited on 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, 10<sup>4</sup>]. 0 <= Node.val <= 10<sup>9</sup> * -10<sup>9</sup> <= target <= 10<sup>9</sup>

题目大意：

求BST中最接近target的值

解题思路：

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

解题步骤：

N/A

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)

Free mock interview