22.12.13 Today’s Leetcode

1442. Count Triplets That Can Form Two Arrays of Equal XOR (Medium)

xor의 inverse function은 xor임을 이용하는 풀이.

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 2:
            return 0
        ans = 0
        xors = [0]
        for i in range(n):
            xors.append(xors[-1] ^ arr[i])
        for i in range(n-1):
            for k in range(i + 1, n):
                if xors[i] == xors[k + 1]:
                    ans += k - i
        return ans

931. Minimum Falling Path Sum (Medium)

DP를 이용한 풀이 및 주어진 matrix 값을 그대로 이용하는 방법. 처음에는 2차원 dict를 이용하여 구현했으나, JAVA에서 구현한것과 마찬가지로 Time limit exceeded가 떠서 다른 방식으로 구현함.

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        row = matrix[0]
        
        m, n = len(matrix), len(matrix[0])
        
        for i in range(1, m):
            for j in range(n):
                
                if j == 0:
                    p1 = matrix[i-1][j]
                    p2 = matrix[i-1][min(n - 1, j + 1)]
                    p3 = p2
                elif j == n - 1:
                    p1 = matrix[i-1][j]
                    p2 = matrix[i-1][max(0, j - 1)]
                    p3 = p2
                else:
                    p1 = matrix[i-1][j-1]
                    p2 = matrix[i-1][j]
                    p3 = matrix[i-1][j+1]
                    
                matrix[i][j] += min(p1, p2, p3)
                
        return min(matrix[-1])

258. Missing Number (Easy)

[0, n] 의 숫자로 이루어진 배열에서 누락된 숫자를 찾는 문제, 배열의 총합이 $n * (n + 1) / 2$이 되어야함을 이용하여 쉽게 해결함.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        total = n * (n + 1) // 2
        return total - sum(nums)