This is merely my personal review of all the typical problems that constitute the mindset for Data Structures and Algorithms (DSA). python solution provided
For the remaining types of problems, please refer to my channel.
everecursion-CSDN博客everecursion关注python,github,chatgpt领域.https://blog.csdn.net/gcsyymm
Valid Sudoku
Valid Sudoku
https://leetcode.cn/problems/valid-sudoku/
Difficulty:MED
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# check each row is valid
for row in board:
row_set = set()
for num in row:
if num != ".":
if num in row_set:
return False
row_set.add(num)
# check each col is valid
for c in range(9):
col_set = set()
for r in range(9):
cur = board[r][c]
if cur != ".":
if cur in col_set:
return False
col_set.add(cur)
# check each box is valid
for i in range(0, 9, 3):
for j in range(0, 9, 3):
box_set = set()
for x in range(i, i + 3):
for y in range(j, j + 3):
cur = board[x][y]
if cur != ".":
if cur in box_set:
return False
box_set.add(cur)
return True
Spiral Matrix
Spiral Matrixhttps://leetcode.cn/problems/spiral-matrix/Difficulty:MED
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# directions vectors (row movement, col movement)
directions = (0, 1), (1, 0), (0, -1), (-1, 0)
# row index, col index, direction index
i = j = di = 0
res = []
for _ in range(len(matrix) * len(matrix[0])):
res.append(matrix[i][j])
matrix[i][j] = "visited"
# check if next movement is valid
next_i, next_j = i + directions[di][0], j + directions[di][1]
# if it is not valid, change direction index
if (
not 0 <= next_i < len(matrix)
or not 0 <= next_j < len(matrix[0])
or matrix[next_i][next_j] == "visited"
):
di = (di + 1) % 4
i += directions[di][0]
j += directions[di][1]
return res
Rotate Image
Rotate Imagehttps://leetcode.cn/problems/rotate-image/
Difficulty:MED
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# rotate from diagnal first
for i in range(len(matrix)):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# then rotate horizontally;
for i in range(len(matrix)):
matrix[i] = matrix[i][::-1]
# IMPORTANT: YOU CANT ROTATE HORIZONTAL LIKE:
# for row in matrix:
# row = row[::-1]
# bc list is mutable and you are just edit the reference to
# the local variable, the original matrix is not changed
Game of Life
Game of Lifehttps://leetcode.cn/problems/game-of-life/ Difficulty:MED
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
for i in range(len(board)):
for j in range(len(board[0])):
live_nbrs = 0
# calculating living neighbours
for ni in range(i - 1, i + 2):
for nj in range(j - 1, j + 2):
if (
not (ni == i and nj == j)
and 0 <= ni < len(board)
and 0 <= nj < len(board[0])
and abs(board[ni][nj]) == 1
):
live_nbrs += 1
# using abs(val)==1 determine it is living at current
if board[i][j] == 1 and not (2 <= live_nbrs <= 3):
board[i][j] = -1
# using val > 0 determine next state is living
if board[i][j] == 0 and live_nbrs == 3:
board[i][j] = 2
# change each cell to its next state
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] > 0:
board[i][j] = 1
else:
board[i][j] = 0
For the remaining types of problems, please refer to my channel.
everecursion-CSDN博客everecursion关注python,github,chatgpt领域.https://blog.csdn.net/gcsyymm