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.
Mã: 
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if obstacleGrid[i][j] == 1 {
                dp[i][j] = 0
                continue
            }
            if i == 0 && j == 0 {
                dp[i][j] = 1
                continue
            }
            if i == 0 {
                dp[i][j] = dp[i][j-1]
                continue
            }
            if j == 0 {
                dp[i][j] = dp[i-1][j]
                continue
            }
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }

    return dp[m-1][n-1]
}
 
Hôm nay bài quy hoạch động điển hình rồi

C#: 
public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.Length, col = obstacleGrid[0].Length;
        int[,] dp = new int[row,col];

        for (var r = 0; r < row; r++)
        {
            for (var c = 0; c < col; c++)
            {
                if (obstacleGrid[r][c] == 1)
                    dp[r,c] = 0;
                else if (r == 0 && c == 0)
                    dp[r,c] = 1;
                else if (r == 0)
                    dp[r,c] = dp[r,c-1];
                else if (c == 0)
                    dp[r,c] = dp[r-1,c];
                else
                    dp[r,c] = dp[r-1,c] + dp[r,c-1];
            }
        }
        return dp[row-1,col-1];
    }
}
 
Nhìn là sẽ hướng về DP Bottom-up rồi
JavaScript: 
function uniquePathsWithObstacles(A: number[][]): number {
    const m = A.length, n = A[0].length;
    const dp = new Array(m + 1).fill(0).map(e => Array(n + 1).fill(0));
    dp[0][1] = 1;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = A[i-1][j-1] ? 0 : dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m][n]
};
hkNtitg.png

Còn có 1 cách khác, khi làm bài này sẽ thấy là mình chỉ cần dùng đến kết quả của dòng trước thôi. Thế nên không có lý do gì để lưu trữ thông tin cho cả table cả, mình chỉ cần lưu thông tin của dòng trước + dòng hiện tại thôi.
dp[0] cho dòng chẵn, dp[1] cho dòng lẻ
JavaScript: 
function uniquePathsWithObstacles(A: number[][]): number {
    const m = A.length, n = A[0].length;
    const dp = new Array(2).fill(0).map(e => Array(n + 1).fill(0));
    dp[0][1] = 1;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (i % 2 === 0) {
                dp[0][j] = A[i - 1][j - 1] ? 0 : dp[1][j] + dp[0][j - 1]
            } else {
                dp[1][j] = A[i - 1][j - 1] ? 0 : dp[0][j] + dp[1][j - 1]
            }
        }
    }
    return m % 2 === 0 ? dp[0][n] : dp[1][n]
};
 
submit 3 lần vì thiếu edge case :cry:
C++: 
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if(obstacleGrid[m - 1][n - 1] == 1)
            return 0;
        if(m == n && m == 1)
            return 1;
        int f[m][n];
        for(int i = 0; i<m; ++i)
            for(int j = 0; j<n; ++j)
                f[i][j] = 0;
        f[0][0] = 1;
        for(int i = 0; i<m; ++i)
            for(int j = 0; j<n; ++j){
                if(i > 0)
                    f[i][j] += f[i - 1][j] * (1 - obstacleGrid[i - 1][j]);
                if(j > 0)
                    f[i][j] += f[i][j - 1] * (1 - obstacleGrid[i][j - 1]);
            }  
        return f[m - 1][n - 1];
    }
};
 
O(1) mem mấy thằng kia tủi loz
JiZo9zf.png

C++: 
struct Solution {
    int uniquePathsWithObstacles(vector<vector<int>>& grid, int i = 0) {
        if (grid[0][0] == 1) return 0; else grid[0][0] = 1;
        for (i = 1; i < grid.size() && grid[i][0] != 1; ++i) grid[i][0] = 1;
        for (; i < grid.size(); ++i) grid[i][0] = 0;
        for (i = 1; i < grid[0].size() && grid[0][i] != 1; ++i) grid[0][i] = 1;
        fill(begin(grid[0]) + i, end(grid[0]), 0);
        for (i = 1; i < grid.size(); ++i)
            for (int j = 1; j < grid[0].size(); ++j)
                grid[i][j] += grid[i][j] == 1 ? -1 : grid[i-1][j] + grid[i][j-1];
        return grid.back().back();
    }
};
 
C++: 
class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        if(n == 2){
            if(nums[0] == nums[1])
                return 1;
            else
                return 0;
        }
        int f[n];
        // f[i] = 0 means invalid partition
        // f[i] = 1 means 2 equal elements
        // f[i] = 2 means 3 equal elements
        // f[i] = 3 means 3 consecutive increasing elements
        f[0] = 0;
        f[1] = nums[0] == nums[1];
        if(nums[0] == nums[1] && nums[1] == nums[2])
            f[2] = 2;
        else if(nums[0] + 1 == nums[1] && nums[1] + 1 == nums[2])
            f[2] = 3;
        else
            f[2] = 0;
        for(int i = 3; i < n; ++i){
            if(f[i - 2] != 0 && nums[i - 1] == nums[i])
                f[i] = 1;
            else if(f[i - 3] != 0 && nums[i - 2] == nums[i - 1] && nums[i - 1] == nums[i])
                f[i] = 2;
            else if(f[i - 3] != 0 && nums[i - 2] + 1 == nums[i - 1] && nums[i - 1] + 1 == nums[i])
                f[i] = 3;
            else
                f[i] = 0;
        }
        return f[n - 1] != 0;
    }
};
 
Lâu lắm mới có bài ez medium vào cuối tuần :ah:

Lần đầu tiên dùng đệ quy + memo thì submit ăn ngay. Sau đó phá đệ quy thì bị tạch mấy cái edge case :pudency:

C#: 
public class Solution {
    bool?[] memo;

    public bool ValidPartition(int[] nums) {
        memo = new bool?[nums.Length];
        return solve(nums, nums.Length-1);   
    }

    bool solve(int[] nums, int index)
    {
        if (index < 0)
            return true;
        if (memo[index] != null)
            return memo[index].Value;

        memo[index] = false;
        if (index > 0 && nums[index] == nums[index-1])
            memo[index] = memo[index] == true || solve(nums, index-2);
        if (index > 1 && ((nums[index] == nums[index-1] && nums[index]==nums[index-2]) || (nums[index] == nums[index-1] + 1 && nums[index-1] == nums[index-2] + 1)))
            memo[index] = memo[index] == true || solve(nums, index-3);

        return memo[index].Value;
    }
}

C#: 
public class Solution {
    public bool ValidPartition(int[] nums) {
        var ret = new bool[nums.Length];
        ret[0] = false;
        if (nums.Length > 1)
            ret[1] = nums[1] == nums[0];
        if (nums.Length > 2)
            ret[2] = (nums[2] == nums[1] && nums[1] == nums[0]) || (nums[2] == nums[1] + 1 && nums[1] == nums[0] + 1);

        for (var i = 3; i < nums.Length; i++)
        {
            ret[i] = (nums[i] == nums[i-1] && ret[i-2])
                || (nums[i] == nums[i-1] && nums[i] == nums[i-2] && ret[i-3])
                || (nums[i] == nums[i-1] + 1 && nums[i-1] == nums[i-2] + 1 && ret[i-3]);
        }
        return ret[nums.Length-1];
    }
}
 
JavaScript: 
var validPartition = function(nums) {
    const dd = [true, false];

    for (let i = 2; i <= nums.length; i++) {
        dd[i] = false;
        if (nums[i-1] === nums[i-2]) {
            dd[i] ||= dd[i-2];
        }
        if (i > 2 && nums[i-1] - nums[i-2] === nums[i-2] - nums[i-3] && [0, 1].includes(nums[i-1] - nums[i-2])) {
            dd[i] ||= dd[i-3];
        }
    }

    return dd[nums.length];
};
 
nãy ngồi đọc editor em thấy có cái toán tử |= này đọc vẫn chưa thông lắm bác nào gth giúp em với :beat_brick:
Mã: 
class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        memo = {-1:True}
        n = len(nums)
        def checkValid(i):
            if i in memo:
                return memo[i]
            ans = False
            if i > 0 and nums[i] == nums[i -1]:
                ans |= checkValid(i -2)
            if i > 1 and nums[i] == nums[i -1] == nums[i -2]:
                ans |= checkValid(i -3)
            if i > 1 and nums[i] == nums[i - 1] + 1 == nums[i -2] + 2:
                ans |= checkValid(i - 3)
            memo[i] = ans
            return ans
        return checkValid(n - 1)
 
chiyeuemthoi đã nói:
nãy ngồi đọc editor em thấy có cái toán tử |= này đọc vẫn chưa thông lắm bác nào gth giúp em với :beat_brick:
Mã: 
class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        memo = {-1:True}
        n = len(nums)
        def checkValid(i):
            if i in memo:
                return memo[i]
            ans = False
            if i > 0 and nums[i] == nums[i -1]:
                ans |= checkValid(i -2)
            if i > 1 and nums[i] == nums[i -1] == nums[i -2]:
                ans |= checkValid(i -3)
            if i > 1 and nums[i] == nums[i - 1] + 1 == nums[i -2] + 2:
                ans |= checkValid(i - 3)
            memo[i] = ans
            return ans
        return checkValid(n - 1)
Nhấp để mở rộng...
Theo t nghĩ là |= là ans = ans or check(). Ban đầu ans = false sau đó gọi hàm check đoạn phía trước, nếu có bất kỳ một lần hàm trả về true thì đoạn sau cũng true luôn cho dù nhánh khác đoạn đầu trả về false. Mục đích là chỉ cần tìm ra 1 case true mà or thì chỉ cần 1 case true là true hết. Có gì sai mời các bác góp ý :)
 
chiyeuemthoi đã nói:
nãy ngồi đọc editor em thấy có cái toán tử |= này đọc vẫn chưa thông lắm bác nào gth giúp em với :beat_brick:
Mã: 
class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        memo = {-1:True}
        n = len(nums)
        def checkValid(i):
            if i in memo:
                return memo[i]
            ans = False
            if i > 0 and nums[i] == nums[i -1]:
                ans |= checkValid(i -2)
            if i > 1 and nums[i] == nums[i -1] == nums[i -2]:
                ans |= checkValid(i -3)
            if i > 1 and nums[i] == nums[i - 1] + 1 == nums[i -2] + 2:
                ans |= checkValid(i - 3)
            memo[i] = ans
            return ans
        return checkValid(n - 1)
Nhấp để mở rộng...
Same question :LOL:
 
Hi_guys đã nói:
Theo t nghĩ là |= là ans = ans or check(). Ban đầu ans = false sau đó gọi hàm check đoạn phía trước, nếu có bất kỳ một lần hàm trả về true thì đoạn sau cũng true luôn cho dù nhánh khác đoạn đầu trả về false. Mục đích là chỉ cần tìm ra 1 case true mà or thì chỉ cần 1 case true là true hết. Có gì sai mời các bác góp ý :)
Nhấp để mở rộng...

Python tôi ko rành nhưng C# thì khác nhé.

a |= b() tương đương a = a | b(), bất kể a là true hay false thì vẫn sẽ gọi hàm b()

a ||= b() tương đương a = a || b(), lúc này nếu a đang là true thì sẽ không gọi hàm b()
 
C++: 
class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        bool dp[n];
        memset(dp, false, sizeof(dp));
        
        dp[1] = nums[0] == nums[1];
        for(int i = 2; i < n; ++i){
            if (nums[i] == nums[i - 1]) dp[i] = dp[i - 2];
            if (!dp[i] && ((nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2]) ||
                (nums[i] == nums[i - 1] + 1 && nums[i - 1] == nums[i - 2] + 1)))
                dp[i] =  i < 3 || dp[i - 3];
        }
        return dp[n - 1];
    }
};
 
Ngôn từ không phù hợp
afatnan đã nói:
bool dp[n]; memset(dp, false, sizeof(dp));
Nhấp để mở rộng...
lịt pẹ 2 dòng này sao ko thay = 1 dòng vector<bool> dp(n); nhìn ngứa mắt vl vừa VLA ngu như chó vừa + thêm 1 dòng memset

chửi thêm cái nữa, viết vla thì cút qua C mà viết, xài C++ làm chó gì ko biết
 
Sửa lần cuối:
Quick select cho nó fancy :big_smile:
Python: 
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        left = 0
        right = len(nums) - 1
        target_index = len(nums) - k

        while left <= right:
            random_index = random.randint(left, right)
            nums[random_index], nums[left] = nums[left], nums[random_index]

            privot = left
            for index in range(left + 1, right + 1):
                if nums[index] < nums[privot]:
                    nums[index], nums[privot + 1] = nums[privot + 1], nums[index]
                    nums[privot], nums[privot + 1] = nums[privot + 1], nums[privot]
                    privot += 1

            while privot < target_index and nums[privot] == nums[privot + 1]:
                privot += 1
           
            if privot == target_index:
                return nums[privot]
            elif privot < target_index:
                left = privot + 1
            else:
                right = privot - 1
       
        return -1
 
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
838
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.585

Chia sẻ trang này

Quay lại
Lên đầu trang