Bài tập Recursion - Nâng cao

def flatten(lst):
    # [1, [2, [3, 4], 5], 6] -> [1, 2, 3, 4, 5, 6]
    pass
 
# Test
nested = [1, [2, [3, 4], 5], 6, [7, [8, 9]]]
print(flatten(nested))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

def sum_nested(lst):
    pass
 
# Test
nested = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
print(sum_nested(nested))  # 45

def binary_search(lst, target, left=0, right=None):
    # Trả về index của target, hoặc -1 nếu không tìm thấy
    pass
 
# Test
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(numbers, 7))   # 3
print(binary_search(numbers, 11))  # 5
print(binary_search(numbers, 20))  # -1

def merge_sort(lst):
    pass
 
def merge(left, right):
    # Hàm phụ để merge hai list đã sắp xếp
    pass
 
# Test
numbers = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(numbers))
# [3, 9, 10, 27, 38, 43, 82]

def quick_sort(lst):
    pass
 
# Test
numbers = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(numbers))
# [3, 9, 10, 27, 38, 43, 82]

def permutations(lst):
    # Trả về list of lists
    pass
 
# Test
items = [1, 2, 3]
perms = permutations(items)
print(len(perms))  # 6
print(perms)
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

def combinations(lst, k):
    pass
 
# Test
items = [1, 2, 3, 4]
combs = combinations(items, 2)
print(combs)
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

def tower_of_hanoi(n, source, target, auxiliary):
    # In ra các bước di chuyển
    pass
 
# Test
tower_of_hanoi(3, 'A', 'C', 'B')
# Output:
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C

def subsets(lst):
    pass
 
# Test
items = [1, 2, 3]
result = subsets(items)
print(result)
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

def partition(lst, pivot):
    # Trả về (smaller, equal, larger)
    pass
 
# Test
numbers = [3, 7, 2, 9, 1, 5, 8]
smaller, equal, larger = partition(numbers, 5)
print(smaller)  # [3, 2, 1]
print(equal)    # [5]
print(larger)   # [7, 9, 8]

def generate_parentheses(n):
    pass
 
# Test
print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

# Tree represented as nested dict
# {'value': 5, 'left': {...}, 'right': {...}}
 
def path_sum(tree, target, path=[]):
    pass
 
# Test
tree = {
    'value': 5,
    'left': {'value': 4, 'left': {'value': 11, 'left': None, 'right': None}, 'right': None},
    'right': {'value': 8, 'left': None, 'right': {'value': 4, 'left': None, 'right': None}}
}
print(path_sum(tree, 20))  # [5, 4, 11]

def count_ways(n):
    # Có bao nhiêu cách leo n bậc thang?
    pass
 
# Test
print(count_ways(3))  # 3: (1+1+1), (1+2), (2+1)
print(count_ways(4))  # 5
print(count_ways(5))  # 8

def word_break(s, word_dict, memo=None):
    pass
 
# Test
word_dict = {"leet", "code", "leetcode"}
print(word_break("leetcode", word_dict))  # True
print(word_break("catsandog", {"cats", "dog", "sand", "and", "cat"}))  # False

def longest_common_subsequence(s1, s2):
    pass
 
# Test
print(longest_common_subsequence("abcde", "ace"))  # 3 (ace)
print(longest_common_subsequence("abc", "abc"))    # 3
print(longest_common_subsequence("abc", "def"))    # 0

def edit_distance(s1, s2):
    # Số phép insert, delete, replace tối thiểu
    pass
 
# Test
print(edit_distance("horse", "ros"))   # 3
print(edit_distance("kitten", "sitting"))  # 3

def n_queens(n):
    # Trả về tất cả các cách đặt n quân hậu
    pass
 
def is_safe(board, row, col):
    # Kiểm tra vị trí có an toàn không
    pass
 
# Test
solutions = n_queens(4)
print(len(solutions))  # 2
for solution in solutions:
    for row in solution:
        print(row)
    print()

def sudoku_solver(board):
    # board: list 9x9, 0 là ô trống
    # Trả về True nếu giải được
    pass
 
def is_valid(board, row, col, num):
    pass
 
# Test
board = [
    [5,3,0,0,7,0,0,0,0],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,0,0,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [0,0,0,0,8,0,0,7,9]
]
sudoku_solver(board)

def expression_parser(expr):
    # Parse và tính "2 + 3 * 4"
    pass
 
# Test
print(expression_parser("2 + 3"))        # 5
print(expression_parser("2 + 3 * 4"))    # 14
print(expression_parser("(2 + 3) * 4"))  # 20

def maze_solver(maze, start, end, visited=None):
    # maze: 2D list, 0 = đường đi, 1 = tường
    # Trả về đường đi hoặc None
    pass
 
# Test
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]
path = maze_solver(maze, (0, 0), (4, 4))
print(path)
# [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]