KK's blog

LeetCode 036 Valid Sudoku

Posted on 2022-01-03 Disqus:

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. 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:

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:

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.

题目大意：

判断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)

LeetCode 043 Multiply Strings

Posted on 2022-01-03 Disqus:

LeetCode

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = “2”, num2 = “3”
Output: “6”

Example 2:

Input: num1 = “123”, num2 = “456”
Output: “56088”

Constraints:

1 <= num1.length, num2.length <= 200 num1 and num2 consist of digits only.
* Both num1 and num2 do not contain any leading zero, except the number 0 itself.

题目大意：

求字符串乘法结果

解题思路：

模拟小学乘法

解题步骤：

N/A

注意事项：

模拟小学乘法，开一个大小为len(num1) + len(num2)的整数数组，内外循环计算每位结果。这位可能是大于20的数，如20, 30..。计算前先反转输入，得到最后结果后也反转。
结果要消除前缀0，但注意0乘以0的情况会返回空，所以要特别处理。

Python代码：

def multiply(self, num1: str, num2: str) -> str:
	digits = [0] * (len(num1) + len(num2))
	num1, num2 = num1[::-1], num2[::-1]
	for i in range(len(num1)):
		for j in range(len(num2)):
			digits[i + j] += int(num1[i]) * int(num2[j])
	carry, res = 0, ''
	for i in range(len(digits)):
		n = digits[i] + carry
		carry = n // 10
		res += str(n % 10)
	return '0' if res[::-1].lstrip('0') == '' else res[::-1].lstrip('0')

算法分析：

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

LeetCode 048 Rotate Image

Posted on 2022-01-02 Disqus:

LeetCode

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

n == matrix.length == matrix[i].length 1 <= n <= 20
* -1000 <= matrix[i][j] <= 1000

题目大意：

顺时针循环矩阵90度

解题思路：

先上下对称，再沿正对角线(左上到右下)对称。正对角线实现比较容易

解题步骤：

N/A

注意事项：

先上下对称，再沿正对角线(左上到右下)对称。正对角线实现比较容易

Python代码：

def rotate(self, matrix: List[List[int]]) -> None:
	for i in range(len(matrix) // 2):
		for j in range(len(matrix[0])):
			matrix[i][j], matrix[len(matrix) - 1 - i][j] = matrix[len(matrix) - 1 - i][j], matrix[i][j]

	for i in range(len(matrix)):
		for j in range(i, len(matrix[0])):
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

算法分析：

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

LeetCode 395 Longest Substring with At Least K Repeating Characters

Posted on 2022-01-01 Edited on 2022-02-02 Disqus:

LeetCode

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = “aaabb”, k = 3
Output: 3
Explanation: The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Example 2:

Input: s = “ababbc”, k = 2
Output: 5
Explanation: The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

Constraints:

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

题目大意：

求最长每种字符至少k个的子串

解题思路：

类似于L003 Longest Substring Without Repeating Characters用双指针法，难点是每种字符，用26字母存储法解决。

解题步骤：

N/A

注意事项：

按多少种不同字符来做sliding window。有1-26种。
子函数求给定种数下的最长子串，所以满足条件在外循环不在内循环，还需进一步统计每种字符是否符合k个。内循环为不满足条件的情况len(char_to_count) == n + 1
char_to_count记录每种字符个数, valid_count是子串[left, i]之间满足题意中个数大于等于k的种数。

Python代码：

def longestSubstring(self, s: str, k: int) -> int:
	res = 0
	for i in range(1, 27):
		res = max(res, self.longest_substring(s, k, i))
	return res

def longest_substring(self, s, k, n) -> int:
	left, char_to_count = 0, collections.defaultdict(int)
	res = 0
	for i in range(len(s)):
		char_to_count[ord(s[i]) - ord('a')] += 1
		while len(char_to_count) == n + 1:
			char_to_count[ord(s[left]) - ord('a')] -= 1 # use left not i
			if char_to_count[ord(s[left]) - ord('a')] == 0:
				char_to_count.pop(ord(s[left]) - ord('a'))
			left += 1
		valid_count = len([_ for _ in char_to_count.values() if _ >= k])
		if len(char_to_count) == valid_count:
			res = max(res, i - left + 1)
	return res

算法分析：

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

LeetCode 101 Symmetric Tree

Posted on 2021-12-30 Edited on 2021-12-31 Disqus:

LeetCode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

**Input:** root = [1,2,2,3,4,4,3]
**Output:** true

Example 2:

**Input:** root = [1,2,2,null,3,null,3]
**Output:** false

Constraints:

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

Follow up: Could you solve it both recursively and iteratively?

题目大意：

判断二叉树是否对称

解题思路：

Easy题，但难点是转化成比较两棵树是否对称

解题步骤：

N/A

注意事项：

难点是转化成比较两棵树是否对称
还要比较值相等，root.val == root2.val

Python代码：

def isSymmetric(self, root: TreeNode) -> bool:
	return self.is_symmetric(root.left, root.right)

def is_symmetric(self, root, root2):
	if not root and not root2:
		return True
	if not root or not root2:
		return False
	return root.val == root2.val and self.is_symmetric(root.left, root2.right) and self.is_symmetric(root.right, root2.left)

算法分析：

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