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

Với 2 người có h bằng nhau thì người có k lớn hơn sẽ xếp sau.
Sort mảng theo thứ tự h giảm dần, nếu h bằng nhau thì xếp theo k tăng dần.
Giờ chỉ việc add vào queue. Người add vào sau luôn có h nhỏ hơn hoặc bằng h của các số trong queue nên ta chỉ việc add vào queue với index = k

VD: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] => [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

[[7,0]] => [[7,0]]
[[7,0],[7,1]] => [[7,0],[7,1]]
[[7,0],[7,1],[6,1]] => [[7,0],[6,1],[7,1]]
[[7,0],[7,1],[6,1],[5,0]] => [[5,0],[7,0],[6,1],[7,1]]
[[7,0],[7,1],[6,1],[5,0],[5,2]] => [[5,0],[7,0],[5,2],[6,1],[7,1]]
[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]] => [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

C#: 
public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        List<int[]> queue = new List<int[]>();
        Array.Sort(people, (a,b) => a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        foreach(var person in people){
           queue.Insert(person[1], person);
        }
        return queue.ToArray();
    }
}
 
Bài này hay, thấy mỗi người làm một kiểu.
Cách của mình là sort theo thứ tự k asc, h asc. Mục đích là sau khi sort sẽ được giống kết quả nhất có thể, vì k càng nhỏ thì càng có khả năng đứng đầu. Sau này nếu có phải đổi vị trí thì số phép hoán đổi vẫn là ít nhất. Theo kiểm tra thì không có case nào phải swap nhiều hơn n^2/6 lần.

Với cách sort này thì không có cách nào để biết một cặp (h, k) cần ở đâu, nên phải đếm lại từ đầu. Tại thời điểm mà số lượng số >= nó lớn hơn k thì rotate.

Độ phức tạp thời gian: O(n^2), bộ nhớ O(1) vì dùng ngay vector đầu vào làm kết quả.

C++: 
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        std::sort(begin(people), end(people), [](auto &v1, auto &v2) {
            return (v1[0] | (v1[1] << 20)) < (v2[0] | (v2[1] << 20));
        });

        int shift = 0;
        for (auto it = begin(people); it != end(people); ++it) {
            int kki = 0;
            auto h = (*it)[0], k = (*it)[1];

            for (auto it2 = begin(people); it2 != it; ++it2) {
                if ((*it2)[0] >= h) {
                    ++kki;
                    if (kki > k) {
                        // shift
                        std::rotate(it2, it, it + 1);
                        break; 
                    }
                }
            }
        }
     
        return people;
    }
};
 
giờ mới để ý các thím trên này dùng C++ nhiều nhỉ?
không biết do công việc của các thím có dùng C++ hay vẫn nhớ từ đại học :burn_joss_stick::burn_joss_stick::burn_joss_stick:
 
Sunday_Sunday said:
giờ mới để ý các thím trên này dùng C++ nhiều nhỉ?
không biết do công việc của các thím có dùng C++ hay vẫn nhớ từ đại học :burn_joss_stick::burn_joss_stick::burn_joss_stick:
Click to expand...

Công việc thì 3 năm không đụng đến C++ rồi.
Nhưng mà về thuật toán thì C++ không có đối thủ: vừa performance cao vừa có thư viện STL đủ các CTDL và thuật toán cơ bản.
 
Bài này phải đọc mất cái hint đầu mới ngộ ra được :cry:
Sắp xếp theo h tăng dần, nếu h bằng nhau thì k giảm dần.
Khởi tạo mảng res chứa kết quả.
Duyệt từ đầu, với mỗi người (h, k) thì sẽ đặt vào res[p] là vị trí trống thứ k tính từ đầu của res do những người sau đều có h lớn hơn người hiện tại sẽ được xếp vào những vị trí trống < k.
Lưu vị trí trống dùng SortedList nên khi pop ra chỉ mất log(n) ==> Time complexity = O(nlogn + nlogn) = O(nlogn)

Python: 
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        from functools import cmp_to_key
        def compare(p1, p2):
            if p1[0] == p2[0]:
                return p2[1] - p1[1]
            return p1[0] - p2[0]
people = sorted(people, key=cmp_to_key(compare))

res = [None] * len(people)

from sortedcontainers import SortedList
all_positions = SortedList(list(range(len(people))))

for p in people:
res[all_positions[p[1]]] = p
all_positions.pop(p[1])

return res
 
bribnt said:
Công việc thì 3 năm không đụng đến C++ rồi.
Nhưng mà về thuật toán thì C++ không có đối thủ: vừa performance cao vừa có thư viện STL đủ các CTDL và thuật toán cơ bản.
Click to expand...
Tui cũng nghĩ vậy cho tới khi thấy mấy thím code = java trên LC. Chả hiểu sao toàn nhanh hơn cả C++ :v.
 
_Gia_Cat_Luong_ said:
Tui cũng nghĩ vậy cho tới khi thấy mấy thím code = java trên LC. Chả hiểu sao toàn nhanh hơn cả C++ :v.
Click to expand...

Cách đây vài page có bác post rồi. C++ nó compile với flags AddressSanitizer nên chậm hơn tí.
Search thêm thì nhiều người cho là với Java nó không tính thời gian compile + load JVM còn với C++ thì tính thêm cả compile time.
 
T vẫn dùng C++ cho công việc đây. Nên làm LC daily bài nào làm lần 1 thì t sẽ chọn C++, lần 2 thì chọn python, lần 3 thì chọn JS.
 
Last edited:
Em cũng đang bắt đầu luyện LC để chuẩn bị đi pv lại, dạo gần đây thấy topic này mới biết thằng LC có cái daily challenge khá hay ho :beauty: tham gia luyện chung với các bác cho vui :big_smile:

Bài này khá nhiều cách để làm, như cách ban đầu của em O(N^2) với cách hiện tại O(Nlog(N)) (sau khi xem hint mới nghĩ ra :smile:) là đã khác nhau rồi.

Đầu tiên ta sort mảng theo thứ tự h tăng dần (nếu h bằng thì k giảm dần), sau đó sẽ tìm vị trí cho từng thằng theo thứ tự từ thằng thấp đến cao.
Vd như với test đề bài, sau khi sort sẽ thành [4,4], [5,2], [5,1], [6,1], [7,1], [7,0].

Giả sử mảng kết quả ban đầu có n slot còn trống [, __, __, __, __, __], dễ thấy thằng thấp nhất [4,4] sẽ phải nhường 4 slot cho mấy thằng khác lớn hơn nó, nên thằng này sẽ được điền vào slot thứ 5 [, __, __, __, [4,4], __].

Tương tự với các thằng sau:
  • [5,2] -> nhường slot cho 2 thằng khác, nên điền vào slot 3 [__, __, [5,2], __, [4,4], __]
  • [5,1] -> nhường slot cho 1 thằng khác, điền vào slot 2 [__, [5,1], [5,2], __, [4,4], __]
  • [6,1] -> nhường slot cho 1 thằng khác, tuy nhiên slot 2 và 3 đã bị chiếm, nên thằng này bị đẩy xuống slot 4 [__, [5,1], [5,2], [6,1], [4,4], __]
  • [7,1] -> nhường slot cho 1 thằng khác, nhưng slot từ 2 -> 5 đã bị chiếm, nên phải điền vào slot 6 [__, [5,1], [5,2], [6,1], [4,4], [7,1]]
  • [7,0] -> không cần nhường slot cho thằng nào cả, nên được điền vào slot 1 [[7,0], [5,1], [5,2], [6,1], [4,4], [7,1]]
Như vậy có thể rút ra kết luận được rằng, thằng thứ i sẽ được điền vào slot còn trống thứ k+1. Khi đó ta có thể chạy thuật toán với đpt O(N^2) như sau:
  • Sort mảng people (h tăng dần, k giảm dần)
  • For loop với mỗi thằng people = {h, k}:
    • Khởi tạo biến đếm slotCount = 0
    • For loop trên mảng kết quả result:
      • If result[j] còn trống thì slotCount++
      • If slotCount == k+1
        • result[j] = people
          [*]break






Ngoài ra ta còn có thể cải tiến thành O(NlogN), giả sử ta có 1 mảng position với giá trị bằng 0 hoặc 1 (position[j] = 0 -> slot thứ j đã bị chiếm, position[j] = 1 -> slot còn trống). Ban đầu tất cả các slot đều còn trống nên position[j] = 1 với toàn bộ j. Khi đó, bài toán tìm slot còn trống thứ k+1 cho thằng i sẽ trở thành:
  • Tìm thằng j nhỏ nhất sao cho sum(pos[1...j]) = k+1
    [*]result[j] = people
    [*]Cập nhật thằng position[j] về 0 sau khi thằng này đã bị chiếm

Bài toán dạng này thường có khá nhiều cấu trúc dữ liệu cây để giải (Segment Tree, Binary Indexed Tree, ...), nhưng đối với thao tác tìm thằng j nhỏ nhất thì cần phải add thêm binary search nữa nên đpt là O(N*logN^2), có thể cải tiến thành O(N*logN) nếu dùng Quick Select để tìm.

Code: https://leetcode.com/submissions/detail/733945724/
 
Bài sáng nay suy nghĩ chứng minh toán học tá lả hoài cả tiếng không ra, vào discuss xem tụi nó làm thế nào thì chả thấy đứa nào chứng minh phương pháp đó là hợp lý. Chán hẳn, chả buồn làm tiếp.

  • Gọi f() là hàm trả về giá trị X sao cho tổng khoảng cách từ X đến các item trong mảng nums sẽ là nhỏ nhất.
  • Giả sử các item trong mảng nums sẽ tăng dần.
  • Nếu nums có 1 item => f(1) = nums[1]
  • Nếu nums có 2 items => f(2) = (nums[1] + nums[2])/2
  • Nếu nums có 3 items => chứng minh quy nạp các kiểu để tìm ra quy luật, mà tìm hoài chưa ra :cry:
 
tdat00 said:
Bài sáng nay suy nghĩ chứng minh toán học tá lả hoài cả tiếng không ra, vào discuss xem tụi nó làm thế nào thì chả thấy đứa nào chứng minh phương pháp đó là hợp lý. Chán hẳn, chả buồn làm tiếp.

  • Gọi f() là hàm trả về giá trị X sao cho tổng khoảng cách từ X đến các item trong mảng nums sẽ là nhỏ nhất.
  • Giả sử các item trong mảng nums sẽ tăng dần.
  • Nếu nums có 1 item => f(1) = nums[1]
  • Nếu nums có 2 items => f(2) = (nums[1] + nums[2])/2
  • Nếu nums có 3 items => chứng minh quy nạp các kiểu để tìm ra quy luật, mà tìm hoài chưa ra :cry:
Click to expand...
Như bạn tính là trung bình cộng đó. Mình cũng nghĩ như vậy nhưng mà submit lần đầu bị sai. Nên nghĩ lại lỡ như số trung bình cộng đó không nằm trong mảng thì tốn thêm mấy bước để chỉnh. Thế là mình chuyển sang Sort rồi lấy số nằm giữa mảng làm số trung bình.
https://leetcode.com/submissions/detail/734678707/
 
tu_tay_bop_dai said:
Như bạn tính là trung bình cộng đó. Mình cũng nghĩ như vậy nhưng mà submit lần đầu bị sai. Nên nghĩ lại lỡ như số trung bình cộng đó không nằm trong mảng thì tốn thêm mấy bước để chỉnh. Thế là mình chuyển sang Sort rồi lấy số nằm giữa mảng làm số trung bình.
https://leetcode.com/submissions/detail/734678707/
Click to expand...
Không phải trung bình cộng, mà còn phải nhân hệ số này nọ nữa. Ví dụ nums = [1,2,3,4,9999] thì phải tìm số X ở giữa sao cho |X-1| + |X-2| + |X-3| + |X-4| + |9999-X| là min. Cái này dùng vòng lặp cũng được nhưng tôi thấy nó hơi chuối nên chán chả muốn làm.

Tôi đọc discuss thấy tụi nó toàn chọn số median làm target, nhưng tôi chưa thấy ai chứng minh được vì sao phải chọn median, vì sao chọn median thì output sẽ là nhỏ nhất?
 
30/6/2022:
  • 1 câu medium hay
  • do hôm qua thức khuyêa nên sáng nay đầu loạn vl
  • Nghĩ 30p ms ra cái solution dùng prefix sum mạc dù time vẫn là O(nlogn) nhưng khá ngáo, nên cách này khỏi nói luôn
  • Code solution 1: https://leetcode.com/submissions/detail/734675197/
  • Đọc discuss thì thấy cách này ms chuẩn:
  • Ví dụ ta có 2 số 6 và 9 để chuyển 2 số này theo yêu cầu thành 2 số giống nhau thì chọn bất kì số giống nhau đó từ 6->9 thì tổng số lần chuyển đều nhỏ nhất
  • [6, 9] -> [7, 7] thì số lần chuyển sẽ là (7 - 6) + (9 - 7) = 3
  • [6, 9] - [9, 9] thì số lần chuyển là (9 - 6) + (9 - 9) = 3
  • ...
  • Để chứng minh thì tưởng tưởng 6 là điểm A, 9 là điểm B;
1656553744510.png

  • Chọn 1 điểm C bất kì trên AB giống như việc chọn 1 số trong khoảng [6, 9]
  • tổng số lần chuyển sẽ là d1 + d2 = AB sẽ ko đổi và sẽ nhỏ nhất
  • nếu chọn điểm C ngoài khoảng AB thì tổng AC + CB > AB giống như việc chọn 1 số ngoài khoảng [6, 9]
1656554297315-png.1238426

 

Attachments

  • 1656554297315.png
    1656554297315.png
    5.8 KB · Views: 202
Last edited:

Similar threads

buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
970
weed_bông
weed_bông
IM LANG
thắc mắc Cần cao nhân giúp đỡ về WordPress (có sử dụng custom theme bằng HTML, CSS)
Replies
3
Views
289
zaizai_vjp
zaizai_vjp
quangpt12345
kiến thức Join Anchor Consortium trading crypto sàn Odyssey kiếm lợi nhuận 2-3% mỗi ngày
Replies
2
Views
121
quangpt12345
quangpt12345
J
kiến thức Mod Mộng Liêu Trai mới nhất
Replies
0
Views
81
jivrus
J

Share this page

Back
Top