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

chiyeuemthoi said:
dạo này toàn hard vậy đọc đề chả hiểu gì ai gth giúp em với ạ :beat_shot: :beat_shot:
Click to expand...

Spoiler chứa giải thích cho đề chứ không phải lời giải:

Có 3 kí tự:
  • 'A': Absent. => Vắng
  • 'L': Late. => Đi trễ
  • 'P': Present. => Có mặt (không vào trễ)
Một ông sinh viên đi học thì sẽ được record lại, vd:

"ALPP"

Là ổng có 4 buổi đi học, nhưng:
  • Buổi đầu cúp học.
  • Buổi sau biết có điểm danh nhưng đi trễ.
  • 2 buổi sau biết thân biết phận đi học đủ.


Giờ cuối kì rồi, tìm coi các ông nào đủ điều kiện mà thi, đếm các trường hợp đạt tiêu chuẩn (tham gia học đầy đủ):

  • Vắng ít hơn 2 buổi: có 1 "A" hoặc ko có "A" nào.
  • Không có liên tiếp 3 buổi trễ "L" => "LLL"

vd:

"APAP" => loại do có 2 "A"
"APPP" => ok
"LLLP" => loại do trễ 3 buổi liên tiếp
"LPLL" => ok
"LALP" => ok

:shame: Vậy cái ông "LLLP" hôm thứ 3 không vào lớp là thoát vì "LLAP" thoả. :(
Đề cho n là số buổi học của cả môn, tìm số trường hợp đủ tiêu chuẩn, xong chia dư cho "10^9 + 7"

"Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 10^9 + 7."

Vậy là có tổng 3^n trường hợp, phải tìm ra số trường hợp đủ tiêu chuẩn, lại còn chia dư. :amazed:

Mình hiểu tới vậy thôi, cũng méo biết giải sao.
 
Last edited:
Tự code với dp 7 trạng thái loằng ngoằng, xem giải mới biết chỉ cần 6 trạng thái gọn gàng hơn bao nhiêu :sad:
Python: 
class Solution(object):
    def checkRecord(self, n):
        """
        :type n: int
        :rtype: int
        """
        mod = 10**9 + 7
        dp = {
            'A': 1,
            'P': {
                'A0': 1,
                'A1': 0
            },
            'L': [
                {
                    'A0': 1,
                    'A1': 0
                },
                {
                    'A0': 0,
                    'A1': 0
                },
            ]
        }
        for i in range(1, n):
            temp = {
                'P': {},
                'L': [{}, {}]
            }
            
            temp['A'] = (dp['P']['A0'] + dp['L'][0]['A0'] + dp['L'][1]['A0']) % mod
            temp['P']['A0'] = (dp['P']['A0'] + dp['L'][0]['A0'] + dp['L'][1]['A0']) % mod
            temp['P']['A1'] = (dp['A'] +  dp['P']['A1'] + + dp['L'][0]['A1'] + dp['L'][1]['A1']) % mod
            temp['L'][0]['A0'] = dp['P']['A0']
            temp['L'][0]['A1'] = (dp['P']['A1'] + dp['A']) % mod
            temp['L'][1]['A0'] = dp['L'][0]['A0']
            temp['L'][1]['A1'] = dp['L'][0]['A1']
            dp = temp
        return (dp['A'] + dp['P']['A0'] + dp['P']['A1'] + dp['L'][0]['A0'] + dp['L'][1]['A0'] + dp['L'][0]['A1'] + dp['L'][1]['A1']) % mod
 
C++: 
class Solution {
public:
    int dp[100001][2][3];

    int checkRecord(int n) {
        const int mod = 1E9+7;
        memset(dp, -1, sizeof(dp));

        auto f = [&](auto &&self, int i, bool is_absent, int consecutive_late) -> int64_t {
            if (i == n) {
                return 1;
            }
            
            if (dp[i][is_absent][consecutive_late] != -1) {
                return dp[i][is_absent][consecutive_late];
            }

            int64_t ans = self(self, i + 1, is_absent, 0);
            if (consecutive_late < 2) {
                ans += self(self, i + 1, is_absent, consecutive_late + 1);
            }
            if (!is_absent) {
                ans += self(self, i + 1, true, 0);
            }

            ans %= mod;
            return dp[i][is_absent][consecutive_late] = ans;
        };

        return f(f, 0, false, 0);
    }
};
 
Python: 
class Solution:
    def checkRecord(self, n: int) -> int:
        dp = [[[-1, -1, -1] for _ in range(2)] for _ in range(n + 1)]
        MOD = 1000000007

        def backtracking(n, absent, late):
            if n == 0:
                return 1
            if dp[n][absent][late] != -1:
                return dp[n][absent][late]
            
            result = backtracking(n - 1, absent, 0) % MOD               # P
            if absent == 0:
                result += backtracking(n - 1, absent + 1, 0) % MOD      # A 
            if late < 2:
                result += backtracking(n - 1, absent, late + 1) % MOD   # L
            dp[n][absent][late] = result % MOD
            return dp[n][absent][late]
        return backtracking(n, 0, 0)
 
nchhnchh said:
Python: 
class Solution:
    def checkRecord(self, n: int) -> int:
        dp = [[[-1, -1, -1] for _ in range(2)] for _ in range(n + 1)]
        MOD = 1000000007

        def backtracking(n, absent, late):
            if n == 0:
                return 1
            if dp[n][absent][late] != -1:
                return dp[n][absent][late]
           
            result = backtracking(n - 1, absent, 0) % MOD               # P
            if absent == 0:
                result += backtracking(n - 1, absent + 1, 0) % MOD      # A
            if late < 2:
                result += backtracking(n - 1, absent, late + 1) % MOD   # L
            dp[n][absent][late] = result % MOD
            return dp[n][absent][late]
        return backtracking(n, 0, 0)
Click to expand...
memo tốn nhiều mem quá, xài lru_cache vậy :shame:
Python: 
MOD = 1000000007
@lru_cache(None)
def backtracking(n, absent, late):
    if n == 0:
        return 1
    result = backtracking(n - 1, absent, 0)
    if absent == 0:
        result += backtracking(n - 1, absent + 1, 0)
    if late < 2:
        result += backtracking(n - 1, absent, late + 1)
    return result % MOD

class Solution:
    def checkRecord(self, n: int) -> int:
        return backtracking(n, 0, 0)
 
Java: 
class Solution {
    int MOD = 1000000007;
    public int checkRecord(int n) {
        long[][] dp1 = new long[n + 1][3]; // 0 A
        long[][] dp2 = new long[n + 1][3]; // 1 A
        // 0 : P, 1 : 1L, 2 : 2L, 3 : A
        dp1[0][0] = 1; dp1[0][1] = 1; dp1[0][2] = 0;
        dp2[0][0] = 0; dp2[0][1] = 0; dp2[0][2] = 0;
        for (int i = 1; i < n; i++) {
            dp1[i][0] = (dp1[i - 1][0] + dp1[i - 1][1] + dp1[i - 1][2]) % MOD;
            dp1[i][1] = dp1[i - 1][0];
            dp1[i][2] = dp1[i - 1][1];
            dp2[i][0] = (dp2[i - 1][0] + dp2[i - 1][1]
                        + dp2[i - 1][2] + dp1[i - 1][0]) % MOD;
            dp2[i][1] = (dp2[i - 1][0] + dp1[i - 1][0]) % MOD;
            dp2[i][2] = dp2[i - 1][1];
        }
        long m = (dp1[n - 1][0] + dp1[n - 1][1] + dp1[n - 1][2]) % MOD;
        long p = (dp2[n - 1][0] + dp2[n - 1][1] + dp2[n - 1][2] + dp1[n - 1][0]) % MOD;
        return (int) (m + p) % MOD;
    }
}
 
Môt phát ăn ngay :still_dreaming:.
C#: 
public int CheckRecord(int n)
{
    int mod = 1000000007;
    var dp = new long[n + 1][][];
    for (int i = 0; i < dp.Length; i++)
    {
        dp[i] = new long[2][];
        for (int j = 0; j < dp[i].Length; j++)
        {
            dp[i][j] = new long[3];
        }
    }

    dp[1][0][0] = 1;
    dp[1][0][1] = 1;
    dp[1][1][0] = 1;

    for (int i = 2; i <= n; i++)
    {
        dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % mod;
        dp[i][0][1] = (dp[i - 1][0][0]) % mod;
        dp[i][0][2] = (dp[i - 1][0][1]) % mod;

        dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]
            + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % mod;

        dp[i][1][1] = (dp[i - 1][1][0]) % mod;
        dp[i][1][2] = (dp[i - 1][1][1]) % mod;
    }

    long sum = 0;
    for (int i = 0; i < dp[n].Length; i++)
    {
        for (int j = 0; j < dp[n][i].Length; j++)
        {
            sum += dp[n][i][j];
            sum = sum % mod;
        }
    }

    return (int)sum;
}
 
thanhdonguyen01 said:
Mấy thím cho em hỏi các thím cày lập trình thi đấu đến tầm bao nhiêu tuổi ạ? Ngày xưa lúc cấp 3 em có cày lập trình thi đấu 1 thời gian, mấy năm ĐH bỏ, giờ cũng ham mà đang phân vân không biết nên đi tiếp theo học các engine + framework (để làm game + server), hay cày cuốc lập trình thi đấu tiếp. Em cảm ơn :too_sad:
Click to expand...
Hôm trước em hỏi bên thread tán chuyện của box mà không thấy ai trả lời nên xin phép hỏi luôn trong thread ạ :sad: Em mấy năm nay cũng đang hứng lại bộ môn này, nhìn các thím mà ham :adore: Em cảm ơn trước ạ :adore:
 
Bài này làm topdown thì bị Memory limit exceed nên xài bottom up
Python: 
class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10**9 + 7
       
        dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(n + 1)]
       
        dp[0][0][0] = 1

        for i in range(1, n + 1):
            for j in range(2):
                for k in range(3):
                    dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][k]) % MOD
                   
                    if j > 0:
                        dp[i][j][0] = (dp[i][j][0] + dp[i-1][j-1][k]) % MOD
                   
                    if k > 0:
                        dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1]) % MOD

        result = 0
        for j in range(2):
            for k in range(3):
                result = (result + dp[n][j][k]) % MOD

        return result
Update, sau khi ngâm cứu thì top down cũng ok, do hay xài
@lru_cache(None) nên chết mẹ mất, đúng là học vẹt tai hại thật :ah:
Python: 
from functools import lru_cache

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10**9 + 7

        @lru_cache
        def numOfWays(current, consecutiveLate, totalAbsent):
            if current == 0:
                return 1

            ans = 0

            # Present
            ans = (ans + numOfWays(current - 1, 0, totalAbsent)) % MOD

            # Late
            if consecutiveLate < 2:
                ans = (ans + numOfWays(current - 1, consecutiveLate + 1, totalAbsent)) % MOD
            
            # Absent
            if totalAbsent < 1:
                ans = (ans + numOfWays(current - 1, 0, totalAbsent + 1)) % MOD

            return ans

        return numOfWays(n, 0, 0)
 
Last edited:
thanhdonguyen01 said:
Hôm trước em hỏi bên thread tán chuyện của box mà không thấy ai trả lời nên xin phép hỏi luôn trong thread ạ :sad: Em mấy năm nay cũng đang hứng lại bộ môn này, nhìn các thím mà ham :adore: Em cảm ơn trước ạ :adore:
Click to expand...
Cày mục đích để làm gì ấy chứ. Nếu để phỏng vấn thì làm gì thì làm phải cày cho bằng được 500 câu medium nhé fen.
 
thanhdonguyen01 said:
Hôm trước em hỏi bên thread tán chuyện của box mà không thấy ai trả lời nên xin phép hỏi luôn trong thread ạ :sad: Em mấy năm nay cũng đang hứng lại bộ môn này, nhìn các thím mà ham :adore: Em cảm ơn trước ạ :adore:
Click to expand...
Lập trình thi đấu thì chỉ cày để đi thi đấu thôi, giải leetcode thì cứ đều đều ngày 1 tiếng làm daily như thú vui tiêu khiển là đc, nói cày thì hơi quá
 
Python: 
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums = sorted(nums)
        n = len(nums)

        def bisearch(target):
            left = 0
            right = n - 1
            ans = n
            while left <= right:
                mid = left + (right - left)//2
                if nums[mid] >= target:
                    ans = mid
                    right = mid - 1
                else:
                    left = mid + 1

            return ans

        left = 1
        right = n
        while left <= right:
            mid = left + (right - left) //2
            count = n - bisearch(mid)
            if count > mid:
                left = mid + 1

            elif count == mid:
                return count

            else:
                right = mid - 1

        return -1
 
Python: 
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for i in range(0 , 1001):
            cnt = 0
            for num in nums:
                if num >=i: cnt += 1
            
            if cnt == i: return cnt
        
        return -1

luoi code BS qua thoi brute force vay
xjIzSG9.png
 

Similar threads

Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
612
heocon0123
heocon0123
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
151
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
16
Views
415
truonggiang!
T
@_shin
kiến thức PIXELVERSE kèo hot - inbox tele để lấy extension chạy auto đánh boss
Replies
0
Views
125
@_shin
@_shin
D
kiến thức Lộ trình tự học phát triển Website Fullstack - Fullstack Web Development
2
Replies
25
Views
2K
Kieft
Kieft

Share this page

Back
Top