thảo luận Leetcode mỗi ngày

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int N = grid.length;
        if(N == 1)
            return grid[0][0];
        for(int i=0; i<N-1; i++){
            int firstMin = grid[i][0], secondMin = Integer.MAX_VALUE, firstMinIndex = 0, secondMinIndex = 0;
            for(int j=1; j<N; j++){
                int num = grid[i][j];
                if(num < firstMin){
                    secondMin = firstMin;
                    firstMin = num;
                    firstMinIndex = j;
                }else if(num < secondMin){
                    secondMin = num;
                }
            }
            for(int k=0; k<N; k++){
                grid[i+1][k] += (k == firstMinIndex ? secondMin : firstMin);

            }
        }

        int min = Integer.MAX_VALUE;
        for(int i=0; i<N; i++)
            min = Math.min(min, grid[N-1][i]);
        return min;
    }
}

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        smallest = []
        heap = []
        for row in range(n):
            for col in range(m):
                if row == 0:
                    heappush(heap, (grid[row][col], col))
                elif col != smallest[0][1]:
                    heappush(heap, (grid[row][col] + smallest[0][0], col))
                else:
                    heappush(heap, (grid[row][col] + smallest[1][0], col))
            smallest = []
            while heap and len(smallest) < 2:
                smallest.append(heappop(heap))
            heap = []
        return smallest[0][0]

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        auto n = grid.size();
        vector<vector<int>> dp(n, vector<int>(n,INT_MAX));
        for(auto i = 0;i< n;++i)
        {
            dp[0][i] = grid[0][i];
        }
        for(auto r=1;r<n;++r)
        {
            for(auto c=0;c<n;++c)
            {
                for(auto index=0;index<n;++index)
                {
                    if(index != c)
                    {
                        dp[r][c] = min (dp[r][c], dp[r-1][index] + grid[r][c]);
                    }
                }
            }
        }
        int re = INT_MAX;
        for(int c=0;c<n;++c)
        {
            re = min(re,dp[n-1][c]);
        }
        return re;
    }
};

class Solution {
  public:
    int minFallingPathSum(vector<vector<int>> const &grid) {
        int rows = grid.size(), cols = grid[0].size();
        // minimum value, index of minimum value, second minimum value
        vector<int> curr(3, INT_MAX), prev(3, INT_MAX);
        // first row
        for (int c = 0; c < cols; ++c) {
            if (grid[0][c] < prev[0]) prev = {grid[0][c], c, prev[0]};
            else if (grid[0][c] < prev[2]) prev[2] = grid[0][c];
        }
        // remaining rows
        for (int r = 1; r < rows; ++r) {
            curr = {INT_MAX, INT_MAX, INT_MAX};
            for (int c = 0; c < cols; ++c) {
                // Update current row
                int v = grid[r][c];
                if (c == prev[1]) v += prev[2];
                else v += prev[0];
                // Update curr
                if (v < curr[0]) curr = {v, c, curr[0]};
                else if (v < curr[2]) curr[2] = v;
            }
            prev = curr;
        }
        return prev[0];
    }
};

  n = len(grid)
        min1, min1_idx, min2, min2_idx = 100, -1, 99, -1
        for i in range(n):
            if grid[0][i] <= min1:
                min2, min2_idx, min1, min1_idx = min1, min1_idx, grid[0][i], i
            elif grid[0][i] < min2:
                min2, min2_idx = grid[0][i], i
        for i in range(1, n):
            curr_min, min2_idx, curr_min2, curr_min2_idx = min2 + grid[i][min1_idx], min1_idx, 99, -1
            for j in range(n):
                if j != min1_idx:
                    temp = min1 + grid[i][j]
                    if temp <= curr_min:
                        curr_min2, curr_min2_idx, curr_min, min2_idx = curr_min, min2_idx, temp, j
                    elif temp < curr_min2:
                        curr_min2, curr_min2_idx = temp, j
            min1, min1_idx, min2, min2_idx = curr_min, min2_idx, curr_min2, curr_min2_idx
        return min1

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        occurs = collections.defaultdict(list)
        for i, char in enumerate(ring):
            occurs[char].append(i)

        def distance(f: int, t: int) -> int:
            mn = min(f, t)
            mx = max(f, t)
            return min(mx - mn, (n - mx) + mn)

        @cache
        def memorize(pos: int, curr: int) -> int:
            if pos == len(key):
                return 0

            ans = float('inf')
            char = key[pos]
            for i in occurs[char]:
                ans = min(ans, 1 + distance(curr, i) + memorize(pos + 1, i))
            return ans

        return memorize(0, 0)