UNIST, CSE 3th

2 minute read

667. Beautiful Arrangement II (medium)

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        res = [1]
        sign = 1
        for i in range(k, 0, -1):
            last = res[-1]
            res.append(last + i * sign)
            sign *= -1

        for i in range(n - k - 1):
            res.append(2 + k + i)
        
        return res

526. Beautiful Arrangement (medium)

DFS, memoization

class Solution:
    def countArrangement(self, n: int) -> int:

        nums = []
        for i in range(1, n + 1):
            nums.append(i)

        visited = [False] * n
        d = dict()

        def dfs(cur):
            nonlocal nums, visited, d
            if cur > n:
                return 1
            ans = 0
            c = tuple(visited)
            if c in d:
                return d.get(c)

            for i in range(n):
                if not visited[i] and (nums[i] % cur == 0 or cur % nums[i] == 0):
                    visited[i] = True
                    ans += dfs(cur + 1)
                    visited[i] = False
            d[c] = ans
            return ans

        return dfs(1)
        

class Solution:
    def countArrangement(self, n: int) -> int:
        # Initialize a list of integers from 1 to n
        nums = list(range(1, n+1))
        self.count = 0
        
        # Define a recursive function to generate all possible permutations
        def backtrack(start):
            # Base case: If all elements have been permuted, increment the count
            if start == n:
                self.count += 1
            # Recursive case: Generate all possible permutations
            for i in range(start, n):
                # Swap the current element with the start element
                nums[start], nums[i] = nums[i], nums[start]
                # Check if the current permutation is beautiful
                if nums[start] % (start+1) == 0 or (start+1) % nums[start] == 0:
                    # Recurse with the next element
                    backtrack(start+1)
                # Swap the current element back to restore the original list
                nums[start], nums[i] = nums[i], nums[start]
        
        # Call the recursive function with the first element
        backtrack(0)
        return self.count

688. Knight Probability in Chessboard (medium)

TLE with DFS

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:

        def on_board(pos):
            return (0 <= pos[0] and pos[0] < n) and (0 <= pos[1] and pos[1] < n)
        
        def dfs(cur, k):
            if not on_board(cur):
                return 0
            if k == 0:
                if on_board(cur):
                    # print(cur)
                    return 1
                return 0
            x_dirs = [2, 1, -2, -1,  2,  1, -2, -1]
            y_dirs = [1, 2, -1, -2, -1, -2,  1,  2]
            temp = 0
            for i in range(8):
                new_pos = (cur[0] + x_dirs[i], cur[1] + y_dirs[i])
                temp += dfs(new_pos, k - 1)
            
            return temp
        
        return dfs((row, column), k) / (8 ** k)

DP

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dp = [[0] * n for _ in range(n)]
        dp[row][column] = 1

        moves = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]

        for move in range(1, k + 1):
            new_dp = [[0] * n for _ in range(n)]
            for r in range(n):
                for c in range(n):
                    for m in moves:
                        new_r = r + m[0]
                        new_c = c + m[1]
                        if 0 <= new_r < n and 0 <= new_c < n:
                            new_dp[r][c] += dp[new_r][new_c] / 8.0
            dp = new_dp

        probability = 0.0
        for r in range(n):
            for c in range(n):
                probability += dp[r][c]

        return probability

You may also enjoy