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

Python: 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        minValue, minColumn, secondMinValue, secondMinColumn  = inf, -1, inf, -1
        for i in range(n):
            if grid[n - 1][i] < minValue:
                secondMinValue, secondMinColumn, minValue, minColumn = minValue, minColumn, grid[n - 1][i], i
            elif grid[n - 1][i] < secondMinValue:
                secondMinValue, secondMinColumn = grid[n - 1][i], i
        for i in range(n - 2, -1, -1):
            cminValue, cminColumn, csecondMinValue, csecondMinColumn  = inf, -1, inf, -1
            for j in range(n):
                minSum = 0
                if j != minColumn:
                    minSum = grid[i][j] + minValue
                else:
                    minSum = grid[i][j] + secondMinValue
                if minSum < cminValue:
                    csecondMinValue, csecondMinColumn, cminValue, cminColumn = cminValue, cminColumn, minSum, j
                elif minSum < csecondMinValue:
                    csecondMinValue, csecondMinColumn = minSum, j
            minValue, minColumn, secondMinValue, secondMinColumn = cminValue, cminColumn, csecondMinValue, csecondMinColumn
            
        return minValue
 
Last edited:
Java: 
class Solution {
    public int minFallingPathSum(int[][] grid) {
        for (int i = 1; i < grid.length; ++i) {
            for (int j = 0; j < grid.length; ++j) {
                int currMin = Integer.MAX_VALUE;
                for (int k = 0; k < grid.length; ++k) {
                    if (j != k && grid[i - 1][k] < currMin) {
                        currMin = grid[i - 1][k];
                    }
                }
                grid[i][j] = currMin + grid[i][j];
            }
        }
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < grid.length; ++j) {
            min = Math.min(min, grid[grid.length - 1][j]);
        }

        return min;
    }
}
 
Python: 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 1: return grid[0][0]
        ans = int(1e9)

        @cache
        def dfs(i , j):
            res = int(1e9)
            if i == n: return 0
            for k in range(0 , n):
                if j != k: res = min(res , grid[i][k] + dfs(i + 1 , k))
           
            return res
       
        for i in range(n):
            ans = min(dfs(0 , i) , ans)
       
        return ans
lần đầu tiên tự giải dc hard k xem sol phê vcl
v1fmMDd.gif
chắc làm top down nên chậm vãi
uzQb2yt.png
 
Java: 
class Solution {
    fun minFallingPathSum(grid: Array<IntArray>): Int {
        val dp = Array(grid.size) { Array(grid.size) { Int.MAX_VALUE } }
        for (i in 0 until grid.size) {
            dp[0] = grid[0][i]
        }
        for (i in 1 until grid.size) {
            for (j in 0 until grid.size) {
                for (k in 0 until grid.size) {
                    if (k == j) {
                        continue
                    }
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + grid[i][j])
                }
            }
        }
        var ans = Int.MAX_VALUE
        for (i in 0 until grid.size) {
            ans = min(ans, dp[grid.size - 1][i])
        }
        return ans
    }
}
Hôm qua cũng DP medium thì không giải được, nay DP hard thì lại giải được, quái quá các bác ạ :shame:
Giải xong ngẫm lại, dùng mảng 1 chiều để chứa kết quả chắc sẽ tối ưu space hơn.
 
Last edited:
Java: 
class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = grid[0][i];
        }
        for (int i = 1; i < n; i++) {
            // find index of min value and 2nd min value
            int[] arr = dp[i - 1];
            int fIdx = 0, sIdx = 0;
            for (int j = 0; j < n; j++) {
                fIdx = arr[j] < arr[fIdx] ? j : fIdx;
            }
            sIdx = 0 == fIdx ? 1 : 0;
            for (int j = 0; j < n; j++) {
                sIdx = arr[j] < arr[sIdx] ? (j == fIdx ? sIdx : j) : sIdx;
            }
            // dp
            for (int j = 0; j < n; j++) {
                dp[i][j] = j == fIdx ? dp[i - 1][sIdx] + grid[i][j] : dp[i - 1][fIdx] + grid[i][j];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dp[n - 1][i]);
        }
        return res;
    }
}
bCeR3Ke.gif
tối ưu còn o(n^2) bằng preprocessing
bài này có lẽ là hard với ai chưa từng biết đến dp
 
Java: 
class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int ans = Integer.MAX_VALUE;
        int[][] dp = new int[n][n];
        for(int i=0;i<n;i++ ){
            dp[0][i]=grid[0][i];
        }
    
        for(int i=1;i<n;i++ ){
            for(int j = 0; j<n;j++){
                dp[i][j]=Integer.MAX_VALUE;
            }
            for(int j= 0;j<n;j++){
                for(int k = 0;k<n;k++){
                    if(j!=k){
                        dp[i][k]= Math.min(dp[i-1][j]+grid[i][k], dp[i][k]);
                    }
                }
            }
        }
        for(int j = 0 ; j<n;j++){
            ans=Math.min(ans, dp[n-1][j]);
        }
        return ans;
    }
}
bài này cùng kiểu mà còn dễ hơn Q3 contest cuối tuần r.
Java: 
class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int ans = Integer.MAX_VALUE;
        for(int i =1;i<n;i++){
            int min = 0;
            for(int j=1;j<n;j++){
                min = grid[i-1][min]<=grid[i-1][j]?min:j;
            }
            int secMin = 0;
            for(int j=0;j<n;j++){    
                if(j!=min){
                    if(secMin==min) secMin=j;
                    secMin = grid[i-1][secMin]<=grid[i-1][j]?secMin:j;
                }
            }
            for(int j=0;j<n;j++){
                if(j==min){
                    grid[i][j] = grid[i-1][secMin] + grid[i][j];
                }
                else{
                    grid[i][j] = grid[i-1][min] + grid[i][j];
                }
            }
         
        }
        for(int j=0;j<n;j++){
            ans = Math.min(ans, grid[n-1][j]);
        }
        return ans;
    }
}
 
Last edited:
Code: 
impl Solution {
    pub fn min_falling_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();

        if n == 1 {
            return grid[0][0];
        }

        let mut dp = vec![vec![0; n]; n];

        for j in 0..n {
            dp[0][j] = grid[0][j];
        }

        for i in 1..n {
            for j in 0..n {
                let mut min = 2i32.pow(31) - 1;

                for k in 0..n {
                    if k == j {
                        continue;
                    }

                    if dp[i - 1][k] < min {
                        min = dp[i - 1][k];
                    }
                }

                dp[i][j] = min + grid[i][j];
            }
        }

        *dp[n - 1].iter().min().unwrap()
    }
}
 
Bài này thì làm bài hôm qua rồi thì nhìn phát ra luôn thôi
Python: 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[0 for j in range(n)] for i in range(n)]
        for j in range(n):
            dp[0][j] = grid[0][j]
        for i in range(1, n):
            min1, min2 = 0, 1
            for j in range(1, n):
                if dp[i-1][j] < dp[i-1][min1]:
                    min2 = min1
                    min1 = j
                elif dp[i-1][j] < dp[i-1][min2]:
                    min2 = j
            for j in range(0, min1):
                dp[i][j] = dp[i-1][min1] + grid[i][j]
            dp[i][min1] = dp[i-1][min2] + grid[i][min1]
            for j in range(min1 + 1, n):
                dp[i][j] = dp[i-1][min1] + grid[i][j]
        return min(dp[n-1])
 
nchhnchh said:
ez đó bác. t nghĩ Hard là do submit failed do cái example nó đơn giản với đọc đề ko kỹ thoi
Click to expand...
LmaoSuVuong said:
tuần rồi leetcode mới ra đề mới trong contest na ná bài này thì chỉ còn rate medium thôi fen
MH42Kgo.png

Click to expand...
riêng Daily thì thấy Easy/Medium thì mình làm chứ thấy Hard xác định khỏi làm luôn, sáng đến súc miệng 1 bài LC thôi rồi ăn sáng, bài Hard thì để cuối tuần :beauty:
 
LmaoSuVuong said:
tuần rồi leetcode mới ra đề mới trong contest na ná bài này thì chỉ còn rate medium thôi fen
MH42Kgo.png

Click to expand...
Q3 cuối tuần rồi khó hơn bài hôm nay 1 chút. Bài hôm nay dùng top-down hơi chậm nhưng k cần phải nghĩ luôn, :p

Python: 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        @cache
        def dfs(i = 0, prev_j = -1):
            if i == len(grid):
                return 0
            ret = inf
            for k, val in enumerate(grid[i]):
                if k == prev_j:
                    continue
                ret = min(ret, val + dfs(i + 1, k))
            return ret
        return dfs()
 
Bổ sung thêm cách viết ngắn hơn, :beauty:

Python: 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        @cache
        def dfs(i = 0, prev_j = -1):
            return 0 if i == len(grid) else reduce(lambda acc, x: acc if x[0] == prev_j else min(acc, x[1] + dfs(i + 1, x[0])), enumerate(grid[i]), inf)
        return dfs()
 
Java: 
class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;

        int[][] dp = new int[n][n];
        // First line always min
        for (int i = 0; i < n; i++) {
            dp[0][i] = grid[0][i];
        }

        int curL = 1, preL = 0;
        // Loop lines
        for (int line = 1; line < n; line++) {
            for (int i = 0; i < n; i++) {
                dp[curL][i] = findMinExceptIndex(i, dp[preL], n) + grid[line][i];
            }
            curL = 1 - curL;
            preL = 1 - preL;
        }
        // get Min
        int res = findMinExceptIndex(-1, dp[preL], n);

        return res;
    }

    public static int findMinExceptIndex(int id, int pre[], int n) {
        int res = id != 0 ? pre[0] : pre[1];
        for (int i = 0; i < n; i++) {
            if (i == id) continue;
            if (pre[i] < res) res = pre[i];
        }
        return res;
    }
}

Bài này thì có rất nhiều chỗ để cải tiến nhưng do lười nên cải tiến 1 bước thôi
 
Java: 
class Solution {
    public int minFallingPathSum(int[][] grid) {
        int ans = Integer.MAX_VALUE;
        int[][] dp = new int[grid.length][grid.length];
        for (int i = 0; i < grid.length; i++) {
            dp[0][i] = grid[0][i];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                for (int k = 0; k < grid.length; k++) {
                    if (k != j) {
                        dp[i][j] = Math.min(dp[i - 1][k] + grid[i][j], dp[i][j]);
                    }
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            ans = Math.min(dp[grid.length - 1][i], ans);
        }
        return ans;
    }
}
 
C#: 
public class Solution
{
    public int MinFallingPathSum(int[][] grid)
    {
        int rows = grid.Length;
        int cols = grid[0].Length;
        int[,] dp = new int[rows, cols];
        for (int i = 0; i < cols; i++)
        {
            dp[0, i] = grid[0][i];
        }
        for (int row = 1; row < rows; row++)
        {
            for (int col = 0; col < cols; col++)
            {
                dp[row, col] = grid[row][col] + FindMin(dp, col, row - 1);
            }
        }
        int minSum = int.MaxValue;
        for (int i = 0; i < cols; i++)
        {
            minSum = Math.Min(minSum, dp[rows - 1, i]);
        }

        return minSum;
    }

    private int FindMin(int[,] dp, int excludedCol, int row)
    {
        int min = int.MaxValue;
        for (int i = 0; i < dp.GetLength(1); i++)
        {
            if (i == excludedCol)
            {
                continue;
            }
            min = Math.Min(min, dp[row, i]);
        }

        return min;
    }
}
 
nay medium trá hình chứ không đến nỗi Hard quá, Hard chắc là do có một cái bài Minimum Falling Path Sum (không có II) nó để label Medium rồi nên bài này nó cho lên Hard
Python: 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[inf] * n for i in range(n)]
        dp[-1] = grid[-1]
        for i in range(n-2,-1,-1):
            for j in range(n):
                if j == 0:
                    dp[i][j] = grid[i][j] + min(dp[i+1][1:])
                elif j == n-1:
                    dp[i][j] = grid[i][j] + min(dp[i+1][:n-1])
                else:
                    dp[i][j] = grid[i][j] + min(dp[i+1][0:j] + dp[i+1][j+1:])
        return min(dp[0])
 
Các bác gạch ác quá. Bổ sung thêm cách tối ưu. :beauty:
C++: 
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        array<pair<int,int>, 2> q = {{{-1,0}, {-1,0}}};
        for (int i = 0; i < grid.size(); ++i) {
            array<pair<int,int>, 2> tmp_q = {{{0,INT_MAX}, {0,INT_MAX}}};
            for (int j = 0; j < grid[0].size(); ++j) {
                if (j != q[1].first && q[1].second + grid[i][j] < tmp_q[0].second) {
                    tmp_q[0] = {j, q[1].second + grid[i][j]};
                } else if ( q[0].second + grid[i][j] < tmp_q[0].second){
                    tmp_q[0] = {j, q[0].second + grid[i][j]};
                }
                if (tmp_q[0].second < tmp_q[1].second) swap(tmp_q[0], tmp_q[1]);
            }
            q = tmp_q;
        }
        return q[1].second;
    }
};
 
JavaScript: 
var minFallingPathSum = function(grid) {
    const n = grid.length;
    let last = grid[0];
    for (let i = 1; i < n; i++) {
        const current = grid[i], r = [...current];
        current.fill(+Infinity);
        for (let j = 1, msf = last[0]; j < n; msf = Math.min(msf, last[j]), j++) {
            current[j] = msf + r[j];
        }
        for (let j = n - 2, msf = last[n - 1]; j >= 0; msf = Math.min(msf, last[j]), j--) {
            current[j] = Math.min(current[j], msf + r[j]);
        }
        last = current;
    }
    return _.min(last);
};
 

Similar threads

hatayquelua
thắc mắc Cần kiến thức gì để được nhận thực tập Dev
2 3
Replies
40
Views
1K
thapnhat111
thapnhat111
L
kiến thức 100 ngày tự học CNTT (AI&Data)
Replies
5
Views
361
vieethang
V
Build Back Better
  • Locked
Bỡn cợt cô giáo lớn tuổi trên TikTok, giới trẻ đang làm gì vậy?
6 7 8
Replies
154
Views
9K
Wind.G
Wind.G
trustnetvn
thảo luận Ríp tồ: Cho các Fan cuồng BTC, ETH
Replies
0
Views
92
trustnetvn
trustnetvn
T
thắc mắc Làm thế nào để tự động hóa việc thiết lập môi trường dev khi khởi động Windows?
Replies
15
Views
795
shazam
shazam

Share this page

Back
Top