KK's blog

LeetCode 016 3Sum Closest

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

<div>

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

<pre>Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). </pre>

Example 2:

<pre>Input: nums = [0,0,0], target = 1 Output: 0 </pre>

Constraints:

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10<sup>4</sup> <= target <= 10<sup>4</sup>

</div>

题目大意：

三数和最接近target

解题思路：

N/A

解题步骤：

N/A

注意事项：

此题不需去重，若等于target可直接返回

Python代码：

def threeSumClosest(self, nums: List[int], target: int) -> int:
	nums.sort()
	res = float('inf')
	for i in range(len(nums)):
		left, right = i + 1, len(nums) - 1
		while left < right:
			temp = nums[i] + nums[left] + nums[right]
			if abs(temp - target) < abs(res - target):
				res = temp
			if temp < target:
				left += 1
			elif temp > target:
				right -= 1
			else:
				return target
	return res

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度O(1)

LeetCode 088 Merge Sorted Array

Posted on 2022-01-04 Edited on 2026-06-29 Disqus:

LeetCode

<div>

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

<pre>Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [<u>1</u>,<u>2</u>,2,<u>3</u>,5,6] with the underlined elements coming from nums1. </pre>

Example 2:

<pre>Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1]. </pre>

Example 3:

<pre>Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1. </pre>

Constraints:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10<sup>9</sup> <= nums1[i], nums2[j] <= 10<sup>9</sup>

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

</div>

题目大意：

合并两有序数组，最后结果储存在第一个数组

解题思路：

从后往前合并

解题步骤：

N/A

注意事项：

i从m - 1而不是len(nums1) - 1开始，m和n是数组实际长度。‘
i小于0就取j那一边，而nums1[i] < nums2[j]就必须保证j也大于等于0，i肯定是了。

算法I解题思路(推荐)：

Python代码：

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
	"""
	Do not return anything, modify nums1 in-place instead.
	"""
	i, j, k= m - 1, n - 1, len(nums1) - 1
	while i >= 0 or j >= 0:
		if i < 0 or (j >= 0 and nums1[i] < nums2[j]):
			nums1[k] = nums2[j]
			j -= 1
			k -= 1
		else:
			nums1[k] = nums1[i]
			i -= 1
			k -= 1

算法II解题思路：

Python代码：

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
	i, j, k = m - 1, n - 1, len(nums1) - 1
	while i >= 0 and j >= 0:
		if nums1[i] > nums2[j]:
			nums1[k] = nums1[i]
			k -= 1
			i -= 1
		else:
			nums1[k] = nums2[j]
			k -= 1
			j -= 1
	while i >= 0:
		nums1[k] = nums1[i]
		k -= 1
		i -= 1
	while j >= 0:
		nums1[k] = nums2[j]
		k -= 1
		j -= 1

算法分析：

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

LeetCode 102 Binary Tree Level Order Traversal

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

LeetCode

<div>

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

<pre>Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] </pre>

Example 2:

<pre>Input: root = [1] Output: [[1]] </pre>

Example 3:

<pre>Input: root = [] Output: [] </pre>

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

</div>

题目大意：

二叉树按层遍历

解题思路：

用BFS模板

解题步骤：

N/A

注意事项：

res.append(level)不是res.append(list(level))因为level = []已重新初始化。
关键行：多这一行level.append(node.val)，其他一样

Python代码：

def levelOrder(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	queue, res = collections.deque([root]), []
	while queue:
		level = []
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node.val)

			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		res.append(level)
	return res

算法分析：

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

LeetCode 387 First Unique Character in a String

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

LeetCode

<div>

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

<pre>Input: s = "leetcode" Output: 0 </pre>

Example 2:

<pre>Input: s = "loveleetcode" Output: 2 </pre>

Example 3:

<pre>Input: s = "aabb" Output: -1 </pre>

Constraints:

1 <= s.length <= 10<sup>5</sup>
s consists of only lowercase English letters.

</div>

题目大意：

求字符串中第一个唯一的字符下标

解题思路：

Easy题。先统计频率，然后再遍历一次字符串找到频率为1的字符

解题步骤：

N/A

注意事项：

Python代码：

def firstUniqChar(self, s: str) -> int:
	char_to_count = collections.Counter(s)
	for i in range(len(s)):
		if char_to_count[s[i]] == 1:
			return i
	return -1

算法分析：

时间复杂度为O(n)，空间复杂度O(1), 26个字母为常量空间

LeetCode 036 Valid Sudoku

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

LeetCode

<div>

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

<pre>Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] Explanation: The input board is shown above and the only valid solution is shown below:

</pre>

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.
It is guaranteed that the input board has only one solution.

</div>

题目大意：

判断Sudoku是否合法

解题思路：

类似于Leetcode 037，用3个global的dict

解题步骤：

N/A

注意事项：

此题和L37有点不同，可以当版上的数是一个个填上的，所以无需初始化将数直接加入到dict中。而是每一位判断是否合法再加入。

Python代码：

def isValidSudoku(self, board: List[List[str]]) -> bool:
	row_dict = [collections.defaultdict(int) for _ in range(len(board))]
	col_dict = [collections.defaultdict(int) for _ in range(len(board))]
	box_dict = [collections.defaultdict(int) for _ in range(len(board))]
	for i in range(len(board)):
		for j in range(len(board[0])):
			if board[i][j] == '.':
				continue
			if not self.is_valid(i, j, board[i][j], row_dict, col_dict, box_dict):
				return False
			row_dict[i][board[i][j]] = 1
			col_dict[j][board[i][j]] = 1
			box_dict[i // 3 * 3 + j // 3][board[i][j]] = 1
	return True

def is_valid(self, i, j, val, row_dict, col_dict, box_dict):
	if val in row_dict[i] or val in col_dict[j] or val in box_dict[i // 3 * 3 + j // 3]:
		return False
	return True

算法分析：

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