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

KimSoHyunGoddness said:
Đây là bài cá nhân bác ạ. Đề là như này nè.
View attachment 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
View attachment 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.
Click to expand...
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))
 
Fire Of Heart said:
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...)
Click to expand...
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.
 
cuc gach said:
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.
Click to expand...
Ồ, mình k thấy chữ liên tiếp. Nếu là liên tiếp thì bài này còn đơn giản hơn nhiều :D. Thanks bro.
 
_Gia_Cat_Luong_ said:
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))
Click to expand...
Em làm theo code của bác thì có vẻ là đáp án là hợp ý em. Nhưng với cái data đầu vào của em hơi khác, nên ko biết có apply cách bác được ko. Nhưng dù sao em cũng cảm ơn và em sẽ tham khảo cách của bác
 
_Gia_Cat_Luong_ said:
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))
Click to expand...
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.
 
Fire Of Heart said:
giải nhì hơi căng đấy :LOL:)
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 :D
Click to expand...
Nhìn chung thì thi VMO sẽ có 2 threshold:
giải nhì: mở ra cơ hội tuyển thẳng vào các lớp tài năng, tạch thì xác định cuộc đời tăm tối (do bọn thi mà tryhard để giải nhì thì hầu hết k đủ khả năng vật nhau với bọn cày đề đh)
IMO: mở ra cơ hội đến các xứ thiên đường, ratio gắt, commitment khủng,...
VOI thì ít punish hơn do còn APIO, nhưng đại để chung là đi theo cái này risk/reward lớn, anh nào không tự lượng sức là dễ sấp 8-)8-)
Btw chắc tôi k nhiều tuổi hơn thím đâu :LOL:
 
thuyduong2007 said:
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ỉ?
Click to expand...
Đệ quy bị giới hạn bởi bộ nhớ stack, nếu đệ quy quá sâu có thể bị tràn (stack overflow). Các bài giải được bằng đệ quy thì dễ code, dễ đọc hơn. Mình thì thích khử đệ quy :big_smile:
 
Đú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. :)
 
thuyduong2007 said:
Đú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. :)
Click to expand...
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 :D.
 
_Gia_Cat_Luong_ said:
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 :D.
Click to expand...
Thường là viết sai nên nó mới tràn, :D.
Nói vậy thôi chứ vẫn có trường hợp viết đúng mà nó vẫn tràn do testcase khủng quá. Còn thằng stack thì nó được cấp phát trên heap thì sẽ lớn hơn nhiều.
 
_Gia_Cat_Luong_ said:
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 :D.
Click to expand...
Cái stack memory mặc định có vài MB, nhiều bài toán đệ quy sâu quá bị tràn sao chạy được. Mô phỏng bằng stack thì nó cũng tương đương như đệ quy mà bộ nhớ lại scale thoải mái, mỗi tội code cực hơn. Algorithm đâu chỉ là mấy bài LC chạy 1s thế này :sweat:

via theNEXTvoz for iPhone
 
thuyduong2007 said:
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.
Click to expand...
  • 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
 
1627984799246.png

Giải bài này theo cách này được ko mấy bác.
 

Attachments

  • 1627984777371.png
    1627984777371.png
    509.5 KB · Views: 61

Similar threads

Zuytori
Tiếp nhận đơn xin khai thác 'kho báu' 3 tấn vàng dưới lòng sông ở Bình Thuận
Replies
8
Views
473
yokitonara
Y
Nobitadiradivo
Phê duyệt gần 14.000 tỷ đầu tư tuyến đường nối cao tốc Biên Hòa – Vũng Tàu
Replies
4
Views
367
TraChanhMuoiMe
TraChanhMuoiMe
BaryonicLord
Tính toán kịch bản đánh thuế tiêu thụ đặc biệt, đảo ngược xu hướng tiêu thụ đồ uống có đường
2 3
Replies
47
Views
3K
Cún Xjnh
Cún Xjnh
sankhaukich
Nước cống đen kịt xả ra vịnh Hạ Long
4 5 6
Replies
103
Views
8K
Han sara
Han sara
N
thắc mắc Tìm phim trộm vàng
Replies
2
Views
111
nottelling
N

Share this page

Back
Top