23.05.09 Today’s Leetcode

54. Spiral Matrix (medium)

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int i = 0, j = 0;
        int w = matrix.length;
        int h = matrix[0].length;

        int[] x = {1, 0, -1, 0};
        int[] y = {0, 1, 0, -1};
        int type = 0;
        while (true) {
            if (list.size() == w * h)
                break;
            list.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE;

            int I = i + y[type];
            int J = j + x[type];
            if (I < 0 || I > w - 1 || J < 0 || J > h - 1 || matrix[I][J] == Integer.MAX_VALUE) {
                type++;
                type %= 4;
            }
            i += y[type];
            j += x[type];
        }
        return list;
    }
}

638. Shopping Offers (medium)

TLE at 61/62

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        n = len(price)
        def check(a, b):
            res = []
            for i in range(len(a)):
                if a[i] < b[i]:
                    return []
                res.append(a[i] - b[i])
            return res

        def dfs(cur, cost):
            # print(cur, cost)
            if sum(cur) == 0:
                return cost

            res = cost
            for i in range(n):
                res += cur[i] * price[i]

            for s in special:
                temp = check(cur, s)
                # print('1', temp, res, s)
                if temp:
                    res = min(res, dfs(temp, cost + s[-1]))

            return res 
        
        return dfs(needs, 0)

solution with tuple

class Solution:
    def shoppingOffers(self, price: List[int], specials: List[List[int]], needs: List[int]) -> int:

        @lru_cache(None)
        def dfs(needs):
            cost = sum(map(mul, needs, price))
            for special in specials:
                tmp = tuple(map(sub, needs, special))
                # 처음보는 구문
                if tmp and min(tmp) < 0: continue
                cost = min(cost, dfs(tmp) + special[-1])
                
            return cost
        return dfs(tuple(needs))

1749. Maximum Absolute Sum of Any Subarray (medium)

TLE at 54/66

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        arr = [0]
        res = 0
        n = len(nums)
        for num in nums:
            arr.append(arr[-1] + num)
            # res = max(res, abs(arr[-1]))

        for i in range(n + 1):
            for j in range(i):
                res = max(res, abs(arr[i] - arr[j]))

        return res

accumulate : python의 누적합.

class Solution:
    def maxAbsoluteSum(self, A):
        return max(accumulate(A, initial=0)) - min(accumulate(A, initial=0))