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

tdat00 · Jun 28, 2022

qhai_2009 said:
Instead of learning solutions of LeetCode questions, understand patterns!

For ex.

If input array is sorted then

Binary search

Two pointers

If asked for all permutations/subsets then
- Backtracking

If given a tree then

DFS

BFS

If given a graph then

DFS

BFS

If given a linked list then
- Two pointers

If recursion is banned then
- Stack

If must solve in-place then

Swap corresponding values

Store one or more different values in the same pointer

If asked for maximum/minimum subarray/subset/options then
- Dynamic programming

If asked for top/least K items then
- Heap

If asked for common strings then

Map

Trie

Else

Map/Set for O(1) time & O(n) space

Sort input for O(nlogn) time and O(1) space

Gì đây, mẹo ôn thi lý thuyết lái xe à

Sent from Samsung SM-A528B using vozFApp

qhai_2009 · Jun 28, 2022

tdat00 said:
Gì đây, mẹo ôn thi lý thuyết lái xe à

Sent from Samsung SM-A528B using vozFApp

cái này mới là tư duy thuật toán đó bác, nắm đc cái này thì mấy bài level medium ko còn quá challenging, kiểu như biết ng ra đề sẽ ra kiểu gì luôn

Lập Trình Viên Gà · Jun 28, 2022

qhai_2009 said:
cái này mới là tư duy thuật toán đó bác, nắm đc cái này thì mấy bài level medium ko còn quá challenging, kiểu như biết ng ra đề sẽ ra kiểu gì luôn

Cái này có đúng ko bác? @qhai_2009 @_Gia_Cat_Luong_ @tdat00 @qkhanhpro @Pepe.The.Frog

tdat00 · Jun 28, 2022

Lập Trình Viên Gà said:
Cái này có đúng ko bác? @qhai_2009 @_Gia_Cat_Luong_ @tdat00 @qkhanhpro @Pepe.The.Frog

Quan điểm của tôi là không, post trên chỉ list ra một số phương phổ biến thôi chứ không phải lúc nào cũng như vậy.

Sent from Samsung SM-A528B using vozFApp

Khac Cuong · Jun 28, 2022

trình gà nên giải khá thủ công nnay thôi các bác, em thấy các bác để ý đến nhiều thứ như thời gian chạy, số lần submit đúng sai, nên chắc cũng phải tập dần thói quen nvay thôi

. Tập thành thói quen sẽ leo rank nhanh hơn

C++:

class Solution {
public:
    int minDeletions(string s) {
        unordered_map<char, int> umap;
        for(int i = 0; i < s.size(); i++){
            umap[s[i]]++;
        }
        vector<int> sz;
        for(auto x : umap){
            sz.push_back(x.second);
        }
        sort(sz.begin(), sz.end(), greater<int>());
        int re = 0;
        for(int i = 0; i < sz.size() - 1; i++){
            for(int j = i + 1; j < sz.size(); j++){
                if(sz[i] == sz[j] && sz[i] != 0){
                    sz[j]--;
                    re++;
                }
            }
        }
        return re;
    }
};

Khac Cuong · Jun 28, 2022

cho em hỏi có bác nào ở đây từng thi mấy cuộc thi gg code jam hay fb hacker cup chưa, em thấy fb hacker cup cbi diễn ra vào tháng 8 thì từ h tập trung ôn k biết qua được vòng gửi xe k nhỉ :pudency:

huyhsbc · Jun 28, 2022

tdat00 said:
Gì đây, mẹo ôn thi lý thuyết lái xe à

Sent from Samsung SM-A528B using vozFApp

data structure and algorithm. Core course of IT.

_Gia_Cat_Luong_ · Jun 28, 2022

qhai_2009 said:
cái này mới là tư duy thuật toán đó bác, nắm đc cái này thì mấy bài level medium ko còn quá challenging, kiểu như biết ng ra đề sẽ ra kiểu gì luôn

Lập Trình Viên Gà said:
Cái này có đúng ko bác? @qhai_2009 @_Gia_Cat_Luong_ @tdat00 @qkhanhpro @Pepe.The.Frog

Đúng, nếu như bác hiểu bản chất của các cái được list trong map đó và tại sao nó lại được xây dựng như vậy. Nói chung cái map đưa ra pattern thường gặp của các bài toán, giúp người học dễ hiểu và tiếp cận tốt hơn trong việc giải bài tập thuật toán. Đừng học vẹt theo nó mà coi nó như một công cụ hỗ trợ là được.

Violet_7 · Jun 29, 2022

29/6/2022:

1 câu medium khá hay
Đọc đề 3 phút mới hiểu cái đề

_ ý tưởng chính: sort theo chiều giảm dần -> xét từ các phần tử lớn nhất

vd: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] -> sort : [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
các phần tử sau sẽ chắc chắn nhỏ hơn hoặc bằng các phần tử trước
nên cứ insert lần lượt các phần tử lớn nhất vào mảng result thì các phần tử sau auto <= các phần tử trong mảng result, từ đó ms có thể đặt vào vị trí chính xác có đúng số người cao hơn được
đầu tiên mảng result = [[7, 0]] -> [[7, 0], [7, 1]]

-> [[7, 0], [6, 1], [7, 1]] (do person 6 có 1 người cao hơn hoặc bằng nên insert vào vị trí 1)
-> [[5, 0], [7, 0], [6, 1], [7, 1]] (do person 5 ko có người cao hơn hoặc bằng nên insert vào vị trí 0)
-> ..... cứ insert như thế cho đến khi ra đáp án
- Time: O(n^2)
Code: https://leetcode.com/submissions/detail/733842640/

mất hơn 15p để giải câu này
đọc discuss thì thấy câu này còn solution o(nlogn) nữa mà h bận r, tí về làm sau.

tdat00 · Jun 29, 2022

Bài sáng nay làm phương pháp thô thiển nhất thấy pass luôn nên chưa tìm hiểu cách tối ưu hơn:

Sort cái mảng theo k desc, h asc. Ý tưởng là số người trước mặt người p càng ít thì khả năng người p xếp đầu hàng sẽ rất cao.
Tạo 1 cái List result để chưa kết quả, khởi đầu List sẽ không có item nào.
Với từng người p trong mảng people, đếm (tuần tự) số người trong result cao hơn hoặc bằng p. Khi thấy vị trí phù hợp thì insert vào result.
Độ **** tạp O(n^2) vì tuy hàm insert của List có độ **** tạp O(n), nhưng thực tế nó chỉ move các item sau vị trí insert => kết hợp với vòng for tìm vị trí insert thì chỉ mất n lần.

C#:

public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        Array.Sort(people, (p0, p1) => p0[1] == p1[1] ? p0[0] - p1[0] : p0[1] - p1[1]);
        //wl(string.Join(',', people.Select(p => $"[{p[0]},{p[1]}]")));
  
        List<int[]> ret = new ();
        foreach (var p in people)
        {
            int i = 0, count = 0;
            for (i = 0; i < ret.Count; i++)
            {
                if (ret[i][0] >= p[0])
                {
                    count++;
              
                    if (count > p[1])
                        break;
                }
            }
            ret.Insert(i, p);
            //wl(string.Join(',', ret.Select(p => $"[{p[0]},{p[1]}]")));
        }
  
        return ret.ToArray();
    }
 
    private void wl(string s)
    {
        Console.WriteLine(s);
    }
}

...Batman... · Jun 29, 2022

Violet_7 said:
29/6/2022:

1 câu medium khá hay

Đọc đề 3 phút mới hiểu cái đề

_ ý tưởng chính: sort theo chiều giảm dần -> xét từ các phần tử lớn nhất

vd: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] -> sort : [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

các phần tử sau sẽ chắc chắn nhỏ hơn hoặc bằng các phần tử trước

nên cứ insert lần lượt các phần tử lớn nhất vào mảng result thì các phần tử sau auto <= các phần tử trong mảng result, từ đó ms có thể đặt vào vị trí chính xác có đúng số người cao hơn được

đầu tiên mảng result = [[7, 0]] -> [[7, 0], [7, 1]]

-> [[7, 0], [6, 1], [7, 1]] (do person 6 có 1 người cao hơn hoặc bằng nên insert vào vị trí 1)
-> [[5, 0], [7, 0], [6, 1], [7, 1]] (do person 5 ko có người cao hơn hoặc bằng nên insert vào vị trí 0)
-> ..... cứ insert như thế cho đến khi ra đáp án
- Time: O(n^2)
Code: https://leetcode.com/submissions/detail/733842640/

mất hơn 15p để giải câu này

đọc discuss thì thấy câu này còn solution o(nlogn) nữa mà h bận r, tí về làm sau.

Bài này tương đương với sort 1 lần theo giá trị k và sort tiếp lần 2 theo giá trị h.
Cho em hỏi tí là mấy dạng bài này có được dùng các hàm sort có sẵn trong ngôn ngữ ko nhỉ :shame:

hay nếu cần sort hay gì đó phải tự implement :shame:

ITBACHKHOA(k cơ khí) · Jun 29, 2022

Violet_7 said:
29/6/2022:

1 câu medium khá hay

Đọc đề 3 phút mới hiểu cái đề

_ ý tưởng chính: sort theo chiều giảm dần -> xét từ các phần tử lớn nhất

vd: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] -> sort : [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

các phần tử sau sẽ chắc chắn nhỏ hơn hoặc bằng các phần tử trước

nên cứ insert lần lượt các phần tử lớn nhất vào mảng result thì các phần tử sau auto <= các phần tử trong mảng result, từ đó ms có thể đặt vào vị trí chính xác có đúng số người cao hơn được

đầu tiên mảng result = [[7, 0]] -> [[7, 0], [7, 1]]

-> [[7, 0], [6, 1], [7, 1]] (do person 6 có 1 người cao hơn hoặc bằng nên insert vào vị trí 1)
-> [[5, 0], [7, 0], [6, 1], [7, 1]] (do person 5 ko có người cao hơn hoặc bằng nên insert vào vị trí 0)
-> ..... cứ insert như thế cho đến khi ra đáp án
- Time: O(n^2)
Code: https://leetcode.com/submissions/detail/733842640/

mất hơn 15p để giải câu này

đọc discuss thì thấy câu này còn solution o(nlogn) nữa mà h bận r, tí về làm sau.

Để đẩy xuống onlogn thì đưa tất cả các chỉ số 0->people.size()-1 vào set, sau đó với mỗi ki, find_by_order(ki) để xem nó ứng với chỉ số nào trong queue mới và sau đó erase chỉ số đó khỏi set.

ITBACHKHOA(k cơ khí) · Jun 29, 2022

https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/

Lập Trình Viên Gà · Jun 29, 2022

tdat00 said:
Bài sáng nay làm phương pháp thô thiển nhất thấy pass luôn nên chưa tìm hiểu cách tối ưu hơn:

Sort cái mảng theo k desc, h asc. Ý tưởng là số người trước mặt người p càng ít thì khả năng người p xếp đầu hàng sẽ rất cao.

Tạo 1 cái List result để chưa kết quả, khởi đầu List sẽ không có item nào.

Với từng người p trong mảng people, đếm (tuần tự) số người trong result cao hơn hoặc bằng p. Khi thấy vị trí phù hợp thì insert vào result.

Độ **** tạp O(n^2) vì tuy hàm insert của List có độ **** tạp O(n), nhưng thực tế nó chỉ move các item sau vị trí insert => kết hợp với vòng for tìm vị trí insert thì chỉ mất n lần.

C#:

public class Solution { public int[][] ReconstructQueue(int[][] people) { Array.Sort(people, (p0, p1) => p0[1] == p1[1] ? p0[0] - p1[0] : p0[1] - p1[1]); //wl(string.Join(',', people.Select(p => $"[{p[0]},{p[1]}]"))); List<int[]> ret = new (); foreach (var p in people) { int i = 0, count = 0; for (i = 0; i < ret.Count; i++) { if (ret[i][0] >= p[0]) { count++; if (count > p[1]) break; } } ret.Insert(i, p); //wl(string.Join(',', ret.Select(p => $"[{p[0]},{p[1]}]"))); } return ret.ToArray(); } private void wl(string s) { Console.WriteLine(s); } }

Ơ leetcode cũng dùng đc linq trong c# à

tdat00 · Jun 29, 2022

Lập Trình Viên Gà said:
Ơ leetcode cũng dùng đc linq trong c# à

Này là Linq to Objects chứ không phải Linq to Sql thím, xài được nhưng chỉ nên để debug thôi chứ performance kém.

Sent from Samsung SM-A528B using vozFApp

Lập Trình Viên Gà · Jun 29, 2022

tdat00 said:
Này là Linq to Objects chứ không phải Linq to Sql thím, xài được nhưng chỉ nên để debug thôi chứ performance kém.

Sent from Samsung SM-A528B using vozFApp

Thím cho e hỏi ngu, đi phỏng vấn mà nó cho mình bài code thì mình có được dùng LINQ ko?>

_Gia_Cat_Luong_ · Jun 29, 2022

Lập Trình Viên Gà said:
Thím cho e hỏi ngu, đi phỏng vấn mà nó cho mình bài code thì mình có được dùng LINQ ko?>

Nếu được thì tránh dùng. Nếu bí quá thì cũng đành dùng chứ biết sao, méo mó có hơn không.

thuyduong2007 · Jun 29, 2022

Ý tưởng của t để giải bài LC ngày hôm nay https://leetcode.com/problems/queue-reconstruction-by-height/ như sau:

B1: sort cái mảng đầu vào theo chiều tăng dần của h, nếu h bằng nhau thì theo chiều giảm dần của k (cái này rất quan trọng, phục vụ cho bước 2).
VD: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] => [[4,4],[5,2],[5,0],[6,1],[7,1],[7,0]]

B2: Loop ngược cái dãy này từ cuối lên và xoay trái k phần tử như dưới đây để các ô về đúng vị trí.
[7,0] -> [7,0]
[7,1],[7,0] -> [7,0], [7,1]
[6,1],[7,0],[7,1] -> [7,1],[6,1],[7,0]
[5,0],[7,1],[6,1],[7,0] -> [5,0],[7,1],[6,1],[7,0]
[5,2],[5,0],[7,1],[6,1],[7,0] -> [5,0],[7,1],[5,2],[6,1],[7,0]
[4,4],[5,0],[7,1],[5,2],[6,1],[7,0] -> [5,0],[7,1],[5,2],[6,1],[4,4],[7,0]

C++:

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(),
                        [] (auto &a, auto &b) {
                            return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
                        });
        for (int i = people.size() - 2; i >= 0; --i){
            rotate(people.begin() + i, people.begin() + i + 1, people.begin() + i + 1 + people[i][1]);
        }
        return people;
    }
};

Cách này TC = O(n^2), SC = O(1)

tdat00 · Jun 29, 2022

Lập Trình Viên Gà said:
Thím cho e hỏi ngu, đi phỏng vấn mà nó cho mình bài code thì mình có được dùng LINQ ko?>

Tùy theo người phỏng vấn, nhưng đa phần là cứ sử dụng trước cho gọn đã vì các hàm thư viện thường đều rất đơn giản không có gì quá khó hiểu. Nếu người phỏng vấn muốn thím implement lại thì họ sẽ nói sau.

NudeDuck · Jun 29, 2022

bài hôm nay e cũng giải cách thô thiển luôn

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

Đã tốn tiền

Junior Member

Senior Member

Đã tốn tiền

Member

Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Member

Đã tốn tiền

Junior Member

Similar threads

Share this page