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

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
LCS, LIS, LCIS, DP classic
JavaScript: 
function longestCommonSubsequence(text1: string, text2: string): number {
    const dp = Array.from({length: text1.length + 1}, () => Array(text2.length + 1).fill(0));
    for (let i = 1; i <= text1.length; i++) {
        for (let j = 1; j <= text2.length; j++) {
            if (text1[i-1] === text2[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1]
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[text1.length][text2.length];
};
 
Mấy cái DP này em thấy tư duy kiểu bottom-up xong rút ra công thức truy hồi rồi qua top-down implement cho dễ
 
1706145647715.png

Á đù xưa làm rồi giải top down bằng C# nhanh gấp 4 lần Python, Memory cũng ít hơn. C# xịn thế ta :ah: Có lẽ nào việc nhảy thuyền từ C# qua Python là sai lầm =((
 
25/01/2024: Bài này thì nhắm mắt vào cũng code được, :ah: .
Nhớ cách đây tầm 7 năm, thằng bé ôn luyện để đi pv, gặp bài này trên hackerrank, mất ăn mất ngủ mấy ngày, code mấy trang giấy, for-while lồng nhau tá lả âm binh cũng k pass được. Sau đó đọc solution mới biết đến DP, coi lời giải chưa đến 10 dòng mà muốn cắn lưỡi. Cay quá nên luyện cái DP miết. Đúng là có học vẫn hơn, giờ gặp dp còn thấy dễ hơn mấy loại khác, :boss:

C++: 
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0));
        for (int i = 1; i <= text1.size(); ++i)
            for (int j = 1; j <= text2.size(); ++j)
                dp[i][j] = text1[i-1] == text2[j-1] ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);
        return dp.back().back();
    }
};

Python: 
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dfs(idx1=0, idx2=0):
            if idx1 == len(text1) or idx2 == len(text2):
                return 0
            if text1[idx1] == text2[idx2]:
                return 1 + dfs(idx1+1, idx2+1)
            return max(dfs(idx1+1, idx2), dfs(idx1,idx2+1))
        return dfs()
 
C#: 
public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        foreach(char c in text1) {
            map1[c - 'a']++;
        }
        foreach(char c in text2) {
            map2[c - 'a']++;
        }
        int[,] dp = new int[text1.Length, text2.Length];
        return recursion(text1, text2, 0, 0, dp, map1, map2);
    }

    public int recursion(string text1, string text2, int index1, int index2, int[,] dp, int[] map1, int[] map2) {
        if(index1 == text1.Length) {
            return 0;
        }
        if(index2 == text2.Length) {
            return 0;
        }

        if(dp[index1, index2] != 0) return dp[index1, index2];

        int max = 0;

        if(map1[text2[index2] - 'a'] <= 0) {
            map2[text2[index2] - 'a']--;
            max = recursion(text1, text2, index1, index2 + 1, dp, map1, map2);
            map2[text2[index2] - 'a']++;
        }
        else if(map2[text1[index1] - 'a'] <= 0) {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;
        }
        else if(text1[index1] == text2[index2]) {
            map1[text1[index1] - 'a']--;
            map2[text2[index2] - 'a']--;
            max = 1 + recursion(text1, text2, index1 + 1, index2 + 1, dp, map1, map2);
            map1[text1[index1] - 'a']++;
            map2[text2[index2] - 'a']++;
        }
        else {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;

            map2[text2[index2] - 'a']--;
            max = Math.Max(max, recursion(text1, text2, index1, index2 + 1, dp, map1, map2));
            map2[text2[index2] - 'a']++;
        }
        
        dp[index1, index2] = max;
        return max;
    }
}
 
Python: 
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dfs(x , y):
            if x == len(text1) or y == len(text2):
                return 0
            res = dfs(x + 1 , y + 1) + 1 if text1[x] == text2[y] else max(dfs(x + 1 , y) , dfs(x , y + 1))
            
            return res

        return dfs(0 , 0 )
ZJqL4rW.png
 
cherry5 đã nói:
C#: 
public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        foreach(char c in text1) {
            map1[c - 'a']++;
        }
        foreach(char c in text2) {
            map2[c - 'a']++;
        }
        int[,] dp = new int[text1.Length, text2.Length];
        return recursion(text1, text2, 0, 0, dp, map1, map2);
    }

    public int recursion(string text1, string text2, int index1, int index2, int[,] dp, int[] map1, int[] map2) {
        if(index1 == text1.Length) {
            return 0;
        }
        if(index2 == text2.Length) {
            return 0;
        }

        if(dp[index1, index2] != 0) return dp[index1, index2];

        int max = 0;

        if(map1[text2[index2] - 'a'] <= 0) {
            map2[text2[index2] - 'a']--;
            max = recursion(text1, text2, index1, index2 + 1, dp, map1, map2);
            map2[text2[index2] - 'a']++;
        }
        else if(map2[text1[index1] - 'a'] <= 0) {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;
        }
        else if(text1[index1] == text2[index2]) {
            map1[text1[index1] - 'a']--;
            map2[text2[index2] - 'a']--;
            max = 1 + recursion(text1, text2, index1 + 1, index2 + 1, dp, map1, map2);
            map1[text1[index1] - 'a']++;
            map2[text2[index2] - 'a']++;
        }
        else {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;

            map2[text2[index2] - 'a']--;
            max = Math.Max(max, recursion(text1, text2, index1, index2 + 1, dp, map1, map2));
            map2[text2[index2] - 'a']++;
        }
       
        dp[index1, index2] = max;
        return max;
    }
}
Nhấp để mở rộng...
cái map dùng làm gì đấy thím
28NOo1g.gif
 
chiyeuemthoi đã nói:
cái map dùng làm gì đấy thím
Nhấp để mở rộng...
Bị timeout cái test case
"ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc""bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
nên thêm vào check cho nhanh thôi bác
 
cherry5 đã nói:
Bị timeout cái test case
"ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc""bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
nên thêm vào check cho nhanh thôi bác
Nhấp để mở rộng...
hay python nó tính kiểu khác nhỉ mh code py mà k cần dùng map cũng pass
 
cherry5 đã nói:
C#: 
public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        foreach(char c in text1) {
            map1[c - 'a']++;
        }
        foreach(char c in text2) {
            map2[c - 'a']++;
        }
        int[,] dp = new int[text1.Length, text2.Length];
        return recursion(text1, text2, 0, 0, dp, map1, map2);
    }

    public int recursion(string text1, string text2, int index1, int index2, int[,] dp, int[] map1, int[] map2) {
        if(index1 == text1.Length) {
            return 0;
        }
        if(index2 == text2.Length) {
            return 0;
        }

        if(dp[index1, index2] != 0) return dp[index1, index2];

        int max = 0;

        if(map1[text2[index2] - 'a'] <= 0) {
            map2[text2[index2] - 'a']--;
            max = recursion(text1, text2, index1, index2 + 1, dp, map1, map2);
            map2[text2[index2] - 'a']++;
        }
        else if(map2[text1[index1] - 'a'] <= 0) {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;
        }
        else if(text1[index1] == text2[index2]) {
            map1[text1[index1] - 'a']--;
            map2[text2[index2] - 'a']--;
            max = 1 + recursion(text1, text2, index1 + 1, index2 + 1, dp, map1, map2);
            map1[text1[index1] - 'a']++;
            map2[text2[index2] - 'a']++;
        }
        else {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;

            map2[text2[index2] - 'a']--;
            max = Math.Max(max, recursion(text1, text2, index1, index2 + 1, dp, map1, map2));
            map2[text2[index2] - 'a']++;
        }
        
        dp[index1, index2] = max;
        return max;
    }
}
Nhấp để mở rộng...
Mai fence code vậy có thấy mệt không :shame:

via theNEXTvoz for iPhone
 
cherry5 đã nói:
C#: 
public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        foreach(char c in text1) {
            map1[c - 'a']++;
        }
        foreach(char c in text2) {
            map2[c - 'a']++;
        }
        int[,] dp = new int[text1.Length, text2.Length];
        return recursion(text1, text2, 0, 0, dp, map1, map2);
    }

    public int recursion(string text1, string text2, int index1, int index2, int[,] dp, int[] map1, int[] map2) {
        if(index1 == text1.Length) {
            return 0;
        }
        if(index2 == text2.Length) {
            return 0;
        }

        if(dp[index1, index2] != 0) return dp[index1, index2];

        int max = 0;

        if(map1[text2[index2] - 'a'] <= 0) {
            map2[text2[index2] - 'a']--;
            max = recursion(text1, text2, index1, index2 + 1, dp, map1, map2);
            map2[text2[index2] - 'a']++;
        }
        else if(map2[text1[index1] - 'a'] <= 0) {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;
        }
        else if(text1[index1] == text2[index2]) {
            map1[text1[index1] - 'a']--;
            map2[text2[index2] - 'a']--;
            max = 1 + recursion(text1, text2, index1 + 1, index2 + 1, dp, map1, map2);
            map1[text1[index1] - 'a']++;
            map2[text2[index2] - 'a']++;
        }
        else {
            map1[text1[index1] - 'a']--;
            max = recursion(text1, text2, index1 + 1, index2, dp, map1, map2);
            map1[text1[index1] - 'a']++;

            map2[text2[index2] - 'a']--;
            max = Math.Max(max, recursion(text1, text2, index1, index2 + 1, dp, map1, map2));
            map2[text2[index2] - 'a']++;
        }
       
        dp[index1, index2] = max;
        return max;
    }
}
Nhấp để mở rộng...
Đọc lú quá mai phen :after_boom:.
 
Java: 
class Solution {
    public static int longestCommonSubsequence(String text1, String text2) {
        int i = 1;
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        while (i <= text1.length()) {
            int j = 1;
            while (j <= text2.length()) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
                j++;
            }
            i++;
        }
        return dp[text1.length()][text2.length()];
    }
}
 
Java: 
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        int[][] dp = new int[m+1][n+1];

        for(int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j>= 0; j--) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i+1][j+1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }

        return dp[0][0];
    }
}
 
C++: 
class Solution {
public:
    int dp[1003][1003];
    int longestCommonSubsequence(string text1, string text2) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < text1.size(); ++i) {
            for (int j = 0; j < text2.size(); ++j) {
                if (text1[i] == text2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};
 
Java: 
class Solution {
    public int width;
    public int height;
    public static final int UP = 0;
    public static final int DOWN = 1;
    public static final int LEFT = 2;
    public static final int RIGHT = 3;
    public static final int[][] DIRECTION = {
        {0, -1},
        {0, 1},
        {-1, 0},
        {1, 0}
    };
    public static final int D_ROW = 0;
    public static final int D_COL = 1;
    public static final int MOD = 1_000_000_007;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        width = n;
        height = m;
        int[][][] memo = new int[height][width][maxMove + 1];
        for (int row = 0; row < height; row++) {
            for (int col = 0; col < width; col++) {
                for (int move = 0; move <= maxMove; move++) {
                    memo[row][col][move] = -1;
                }
            }
        }
        return generate(startRow, startColumn, maxMove, memo);
    }
    public int generate(int curRow, int curCol, int remainingMove, int[][][] memo) {
        if (remainingMove == 0) {
            if (isReachToBoundary(curRow, curCol)) return 1;
            return 0;
        }
        if (isReachToBoundary(curRow, curCol)) {
            return 1;
        }
        if (memo[curRow][curCol][remainingMove] != -1) {
            return memo[curRow][curCol][remainingMove];
        }
        int totalPathToBoundary = 0;
        for (int direction = UP; direction <= RIGHT; direction++) {
            int nextCellRow = DIRECTION[direction][D_ROW] + curRow;
            int nextCellCol = DIRECTION[direction][D_COL] + curCol;
            totalPathToBoundary += generate(nextCellRow, nextCellCol, remainingMove - 1, memo);
            totalPathToBoundary %= MOD;
        }
        memo[curRow][curCol][remainingMove] = totalPathToBoundary;
        return totalPathToBoundary;
    }
    public boolean isReachToBoundary(int curRow, int curCol) {
        return !(curRow < height && curRow >= 0 && curCol < width && curCol >= 0);
    }
}
Vừa làm hôm kia xong, lấy code cũ submit luôn.
 
Sửa lần cuối:
Trạng thái
Không mở để trả lời thêm.

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
1K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
842
giayasics
giayasics

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.212.982

Chia sẻ trang này

Quay lại
Lên đầu trang