thảo luận [Học Tập] Topic thuật toán

KimSoHyunGoddness đã nói:

Đây là bài cá nhân bác ạ. Đề là như này nè.
Xem tệp đính kèm 689192
Em có danh sách cấp độ như thế này. GIờ yêu cầu là chuyển nó về dạng bảng như thế này
Xem tệp đính kèm 689194
Hiện tại là được giới hạn ở level 10. Nhưng trong tương lai là có thể sẽ hơn nữa.

Nhấp để mở rộng...

class Level {
    name: string = '';
    subLevels: Level[] = []

    constructor(name: string, subLevels: Level[] = []) {
        this.name = name
        this.subLevels = subLevels
    }

    flatten() {
        if (!this.subLevels.length) return [[this.name]]
        return this.subLevels.reduce((arr, subLevel) => arr.concat(subLevel.flatten().map(detail => [this.name, ...detail])), [])
    }
}

const levels = [
    new Level('Level 1 - 1', [
        new Level('Level 2 - 1'),
        new Level('Level 2 - 2', [new Level('Level 3 - 1')]),
        new Level('Level 2 - 3', [new Level('Level 3 - 2')])
    ]),
    new Level('Level 1 - 2', [
        new Level('Level 2 - 4'),
    ])
]

const result = levels.reduce((arr, level) => arr.concat(level.flatten()), [])

console.log(JSON.stringify(result))

Fire Of Heart đã nói:

Cho các thím làm thử bài này, đề thi hsg quốc gia ngày xưa nè:

Tìm chuỗi con liên tục tăng dài nhất, với điều kiện, các số trong chuỗi phải là các số thuộc dãy sau:

u1 = 1, uk = uk-1 + k

ví dụ dãy: 8 8 2000 1 6 6 15 399

Thì đáp án là 3, vì dãy 6 6 15 là chuỗi tăng dài nhất, thỏa mãn là các số thuộc dãy trên: (u1 = 1, u2 = 3, u3 = 6, u 4 = 10, u5 = 15)
// note: u(k) tức là phần tử thứ k trong dãy.

(giá mà ngày xưa mình thi tin thay toán thì ngon cmnr...)

Nhấp để mở rộng...

cuc gach đã nói:

Dễ thấy uk = 1 + 2 + ... + (k - 1) + k = k * (k + 1) / 2. Đưa về bài toán kiểm tra xem ứng với mỗi ai có tồn tại nghiệm nguyên k hay không.
Thường mấy bài này 1 <= ai <= 1e9 thì dùng map cho k chạy từ 1 -> 1e5 luôn cũng được.
Vì là dãy con liên tiếp nên ta có thể dùng two pointer để tìm độ dài của dãy con cho đơn giản.

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Mình nghĩ đây là bài đệ quy flatMap thôi, bạn thử tham khảo đoạn dưới đây nha:

JavaScript:

class Level {
    name: string = '';
    subLevels: Level[] = []

    constructor(name: string, subLevels: Level[] = []) {
        this.name = name
        this.subLevels = subLevels
    }

    flatten() {
        if (!this.subLevels.length) return [[this.name]]
        return this.subLevels.reduce((arr, subLevel) => arr.concat(subLevel.flatten().map(detail => [this.name, ...detail])), [])
    }
}

const levels = [
    new Level('Level 1 - 1', [
        new Level('Level 2 - 1'),
        new Level('Level 2 - 2', [new Level('Level 3 - 1')]),
        new Level('Level 2 - 3', [new Level('Level 3 - 2')])
    ]),
    new Level('Level 1 - 2', [
        new Level('Level 2 - 4'),
    ])
]

const result = levels.reduce((arr, level) => arr.concat(level.flatten()), [])

console.log(JSON.stringify(result))

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Tiếp tục chuyên mục mỗi ngày một leetcode. Các bài mình làm ngày hôm nay:

#396. (Medium) https://leetcode.com/problems/rotate-function
#397. (Medium) https://leetcode.com/problems/integer-replacement
#398. (Medium) https://leetcode.com/problems/random-pick-index

Mình sẽ share về bài Integer Replacement:
#397. (Medium) https://leetcode.com/problems/integer-replacement

Phân tích bài toán:

• 1 <= n <= 2^31 - 1: Với constraint này thì chỉ có O(logn) và O(1) là work
• Nhận thấy nếu n là số chẵn thì đáp án sẽ là 1 + integerReplacement(n / 2)
• Nếu n là số lẻ thì sẽ là 1 + min(integerReplacement(n + 1), integerReplacement(n - 1)).
• Vì n là số lẻ => n + 1 và n - 1 sẽ là số chẵn => Tiếp theo sẽ được chia 2.
• Nếu theo flow bình thường thì độ phức sẽ là O(logn). Vì số n sau mỗi lần đệ quy sẽ giảm đi một nửa. => Works

Solution:

Python:

class Solution:
    def integerReplacement(self, n: int) -> int:
        if n == 1:
            return 0
    
        if n % 2 == 0:
            return 1 + self.integerReplacement(n // 2)

        return 1 + min(self.integerReplacement(n + 1), self.integerReplacement(n - 1))

Optimization:

• Solution trên chưa tối ưu nếu ta để ý kĩ trong trường hợp n lẻ, ta cần đệ quy cho 2 trường hợp
• Các bạn cần để ý là thông thường việc đệ quy nó sẽ tăng theo cấp số nhân. Đệ quy cho 2 trường hợp thì sẽ dễ dẫn đến độ phức tạp 2^n
• Thử tưởng tượng nếu n lẻ, sau đó (n + 1) / 2 và (n - 1) / 2 cũng là số lẻ. Lúc đó ta sẽ phải tính cho 4 trường hợp.
• Suy rộng ra nếu cứ mỗi bước đệ quy ta phải tính 2 trường hợp thì sau logn bước, ta cần phải tính cho 2^logn = O(n) cho trường hợp xấu nhất
• Vậy làm sao để tránh vấn đề này ? Ý tưởng là sử dụng quy hoạch động để tránh giải lại các bài toán con gối nhau.
• Trong bài trên thì memoization là giải pháp đơn giản mà k làm thay đổi cấu trúc Solution. Với python thì thêm cái decoration @cache vào là đc. What an easy method.

Python:

class Solution:
    @cache
    def integerReplacement(self, n: int) -> int:
        if n == 1:
            return 0
    
        if n % 2 == 0:
            return 1 + self.integerReplacement(n // 2)

        return 1 + min(self.integerReplacement(n + 1), self.integerReplacement(n - 1))

Nhấp để mở rộng...

class Solution {
public:
    int integerReplacement(int n) {
        unordered_map<int,int> memoi;
        return integerReplacementRecursive(memoi, n);
    }

    int integerReplacementRecursive(unordered_map<int, int> &memoi, int n) {
        if (memoi.find(n) != memoi.end()) return memoi[n];
        if (n == 1){
           memoi[n] = 0;
        }else if (n == INT_MAX){
            memoi[n] = 32;
        }else if (n % 2 == 0){
            memoi[n] = 1 + integerReplacementRecursive(memoi, n/2);
        } else {
            memoi[n] = min(1 + integerReplacementRecursive(memoi, n+1),
                           1 + integerReplacementRecursive(memoi, n-1));
        }
        return memoi[n];
    }
};

Fire Of Heart đã nói:

giải nhì hơi căng đấy )
muốn nhì thì phải ôn đủ kiểu anh ơi, tầm giải nhì là coi như tạm đủ tầm thi IMO cmnr

Nhấp để mở rộng...

thuyduong2007 đã nói:

Theo như quan sát của mình thì hầu như bài nào giải được bằng stack thì đều giải được bằng đệ quy và ngược lại. Do chương trình quản lý function, local variable,... bằng stack. Cái này không biết có nghiên cứu nào so sánh 2 giải thuật này chưa nhỉ?

Nhấp để mở rộng...

thuyduong2007 đã nói:

Đúng rồi, dùng đệ quy có thể gây ra tràn stack. Nhưng viết đệ quy nếu quen thì sẽ thấy nhanh và dễ hơn là dùng cấu trúc dữ liệu stack.

Nhấp để mở rộng...

KimSoHyunGoddness đã nói:

Sau khi nhờ bác @_Gia_Cat_Luong_ giúp đỡ thì thấy bản thân mình kém đệ quy quá.
KO biết giờ làm sao ôn lại đê quy từ cơ bản tới mức vừa phải mấy bác.

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Nếu đệ quy mà để gây tràn stack thì dùng stack khử đệ quy thiết nghĩ cái stack đó cũng sẽ consume memory sml thôi. Căn bản là cách mình dùng, còn đệ quy hay stack chỉ là công cụ. Thấy cái nào thuận tay thì xài cái đó là được .

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Nếu đệ quy mà để gây tràn stack thì dùng stack khử đệ quy thiết nghĩ cái stack đó cũng sẽ consume memory sml thôi. Căn bản là cách mình dùng, còn đệ quy hay stack chỉ là công cụ. Thấy cái nào thuận tay thì xài cái đó là được .

Nhấp để mở rộng...

thuyduong2007 đã nói:

Mình thêm cách làm bằng C++. Bài này nói chung không có gì nhiều để nói.

C++:

class Solution {
public:
    int integerReplacement(int n) {
        unordered_map<int,int> memoi;
        return integerReplacementRecursive(memoi, n);
    }

    int integerReplacementRecursive(unordered_map<int, int> &memoi, int n) {
        if (memoi.find(n) != memoi.end()) return memoi[n];
        if (n == 1){
           memoi[n] = 0;
        }else if (n == INT_MAX){
            memoi[n] = 32;
        }else if (n % 2 == 0){
            memoi[n] = 1 + integerReplacementRecursive(memoi, n/2);
        } else {
            memoi[n] = min(1 + integerReplacementRecursive(memoi, n+1),
                           1 + integerReplacementRecursive(memoi, n-1));
        }
        return memoi[n];
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Integer Replacement.
Memory Usage: 10.3 MB, less than 7.65% of C++ online submissions for Integer Replacement.

Nhấp để mở rộng...

• 1 <= n <= 2^31 - 1: Với constraint này thì chỉ có O(logn) và O(1) là work. Bạn cho mình xin cách tính ra tại sao lại là O(logn) và O(1) với

Thạch Sanh_4.0 đã nói:

• 1 <= n <= 2^31 - 1: Với constraint này thì chỉ có O(logn) và O(1) là work. Bạn cho mình xin cách tính ra tại sao lại là O(logn) và O(1) với

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Cái này là kinh nghiệm thôi fen. Fen đọc lại post này của mình nha.
https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/post-11061621

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Cái này là kinh nghiệm thôi fen. Fen đọc lại post này của mình nha.
https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/post-11061621

Nhấp để mở rộng...

KimSoHyunGoddness đã nói:

Xem tệp đính kèm 690745
Giải bài này theo cách này được ko mấy bác.

Nhấp để mở rộng...

Thạch Sanh_4.0 đã nói:

hi vọng bác vẫn ra bài đều đều để mợi người học hỏi

Nhấp để mở rộng...