23.02.06 Today’s Leetcode

1470. Shuffle the Array (easy)

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        n = len(nums) // 2
        a, b = nums[:n], nums[n:]
        res = []
        for i in range(n):
            res.append(a[i])
            res.append(b[i])
        return res

N-Queens (hard)

못풀었다. ㅇㅇ DFS로 해결하려고 했는데, 2차원 배열을 백트레킹하는 과정에서 deepcopy를 해야하는데 이걸 구현하는데 귀찮아서(?) 포기했다. i번째 column에서 queen의 index를 저장하는 1차원 배열로 DFS를 써서 푸는 풀이가 있어서 가져와보았다. 신기하네요.

class Solution:
    def solveNQueens(self, n):
        res = []
        self.dfs([-1]*n, 0, [], res)
        return res
 
    # nums is a one-dimension array, like [1, 3, 0, 2] means
    # first queen is placed in column 1, second queen is placed
    # in column 3, etc.
    def dfs(self, nums, index, path, res):
        if index == len(nums):
            res.append(path)
            return  # backtracking
        for i in range(len(nums)):
            nums[index] = i
            if self.valid(nums, index):  # pruning
                tmp = "." * len(nums)
                self.dfs(nums, index + 1, path + [tmp[:i] + "Q" + tmp[i+1:]], res)

    # check whether nth queen can be placed in that column
    def valid(self, nums, n):
        for i in range(n):
            if abs(nums[i] - nums[n]) == n - i or nums[i] == nums[n]:
                return False
        return True

88. Merge Sorted Array (easy)

beautiful!

class Solution:
    def merge(self, nums1, m, nums2, n):
        while m > 0 and n > 0:
            if nums1[m - 1] >= nums2[n - 1]:
                nums1[m + n-1] = nums1[m - 1]
                m -= 1
            else:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
        if n > 0:
            nums1[:n] = nums2[:n]