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

Yêu em Thu Nga CN12 ptit · 29/9/21

nashwade đã nói:
Nay vừa vào làm thử 1 bài LeetCode, đề cũng đơn giản nhưng có giới hạn bộ nhớ nên cũng khá khoai. Các bác hứng thú có thể vào thảo luận cho vui

bài này hôm kia e vừa thực hành xong :sweat:

Lập Trình Viên Số Khổ · 29/9/21

Yêu em Thu Nga CN12 ptit đã nói:

n.logn thì dễ mà o(n) thì sao nhỉ

C++:

class Solution {
public:
    int firstMissingPositive(vector<int>& a) {
        sort(a.begin(),a.end());
        int n=a.size();
        int min=1;
        for(int i=0;i<n;i++){
             if(a[i]<0) a[i]=0;
             if(a[i]==min) min++;
        }
        return min;
    }
};

đây là nlogn mà cái dòng if đầu tiên cho vào làm gì vậy fen

Lập Trình Viên Số Khổ · 29/9/21

caubeongungo đã nói:
có việc chưa anh

, chắc năm sau mới đi tìm việc được, mà fen phải post 1 bài tập vào nó mới tránh thành comment spam hâha

nashwade · 29/9/21

Nghĩ cách giải khi được dùng thêm O(N) bộ nhớ sau đó cải tiến bằng cách dùng trực tiếp trên input thay vì phải tạo thêm bộ nhớ

_Gia_Cat_Luong_ · 29/9/21

nashwade đã nói:
Nay vừa vào làm thử 1 bài LeetCode, đề cũng đơn giản nhưng có giới hạn bộ nhớ nên cũng khá khoai. Các bác hứng thú có thể vào thảo luận cho vui

Vì cái đề đòi O(1) space nên có 2 khả năng:

Hoặc là dùng lượng bộ nhớ fixed. Vd: constraint là 5*10^5 thì cấp phát luôn vector<int> 500k phần tử.
Hoặc là sử dụng lại cái mảng input

Nhận thấy giả sử cái mảng có n phần tử, thì:
1. Hoặc là nó thiếu một số nào đó trong khoảng từ 1 - n
2. Nếu không thì nghĩa là mảng đó là một hoán vị của mảng 1...n => số bị thiếu là số n + 1

Nhưng theo constraint thì n <= 500000, nên có thể làm ý tưởng đơn giản (nhưng k tối ưu). Là dùng luôn 1 cái bitset<500000>. Lặp qua từng phần tử, nếu nó nằm trong khoảng 1 => 500000 thì bật bit tương ứng lên, k thì bỏ qua.

Sau đó duyệt lại i từ 1 => 500000. Xem số nào thiếu thì return. Nếu k có số nào thiếu thì return về 500001.

p/s: Ý tưởng trên cũng có thể dùng cho pp2 là dùng lại luôn cái mảng hiện tại, thay vì bitset. Nhưng lười suy diễn thêm quá

thuyduong2007 · 29/9/21

Bài này t từng làm rồi. Có một nhận xét là kết quả cần tìm sẽ luôn nằm trong khoảng từ [1,nums.size()]. :big_smile:

vexliva · 29/9/21

thuyduong2007 đã nói:
Bài này t từng làm rồi. Có một nhận xét là kết quả cần tìm sẽ luôn nằm trong khoảng từ [1,nums.size()].

nhận xét có ích ghê thím :misdoubt:

thuyduong2007 · 29/9/21

vexliva đã nói:
nhận xét có ích ghê thím

Nói thật hay nói đểu vậy? :beat_brick:

thuyduong2007 · 29/9/21

Do kết quả sẽ chỉ nằm trong khoảng từ [1,nums.size()+1] nên ý tưởng là sẽ dùng lại luôn cái nums để check.

C++:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            while (nums[i] != i+1 && nums[i] <= nums.size() && nums[i] > 0 && nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
        }
     
        int i;
        for (i = 0; i < nums.size() && nums[i] == i+1; ++i);
        return i+1;
    }
};

Việc swap nhằm đưa các số về đúng vị trí, do đó chỉ có n lần swap. Nên độ phức tạp chỉ là O(n).

nashwade · 30/9/21

Cách của bác @_Gia_Cat_Luong_ là O(N) bộ nhớ rồi mà nhỉ. Mình nghĩ cách của bác @thuyduong2007 mới là cách chuẩn. Cơ mà đoạn xử lý swap đấy cũng không phải đơn giản.

Mình thấy mấy bài interview hay có cái trò bắt phải sử dụng lại bộ nhớ trong input để làm những thứ khác. Mình khá anti với những bài thế này vì nó là một practice cực kì tệ khi code. Nguyên tắc vẫn nên là mỗi biến phải dùng cho một mục đích riêng chứ không nên dùng lẫn vào nhau như thế.

_Gia_Cat_Luong_ · 30/9/21

nashwade đã nói:
Cách của bác @_Gia_Cat_Luong_ là O(N) bộ nhớ rồi mà nhỉ. Mình nghĩ cách của bác @thuyduong2007 mới là cách chuẩn. Cơ mà đoạn xử lý swap đấy cũng không phải đơn giản.

Mình thấy mấy bài interview hay có cái trò bắt phải sử dụng lại bộ nhớ trong input để làm những thứ khác. Mình khá anti với những bài thế này vì nó là một practice cực kì tệ khi code. Nguyên tắc vẫn nên là mỗi biến phải dùng cho một mục đích riêng chứ không nên dùng lẫn vào nhau như thế.

fixed mem thì là O(1) chứ fen =))

. Cách của mình dĩ nhiên là cheaty, nhưng nếu đánh giá đúng lý thuyết thì vẫn là O(1) :v.

trungpham90 · 30/9/21

nashwade đã nói:
Cách của bác @_Gia_Cat_Luong_ là O(N) bộ nhớ rồi mà nhỉ. Mình nghĩ cách của bác @thuyduong2007 mới là cách chuẩn. Cơ mà đoạn xử lý swap đấy cũng không phải đơn giản.

Mình thấy mấy bài interview hay có cái trò bắt phải sử dụng lại bộ nhớ trong input để làm những thứ khác. Mình khá anti với những bài thế này vì nó là một practice cực kì tệ khi code. Nguyên tắc vẫn nên là mỗi biến phải dùng cho một mục đích riêng chứ không nên dùng lẫn vào nhau như thế.

Ko đồng ý nhé, ví dụ Arrays.sort(int[]), hoặc builder pattern.

Lập Trình Viên Số Khổ · 30/9/21

https://codeforces.com/contest/1581/problem/0

fen nào làm bài này đi

vexliva · 30/9/21

Lập Trình Viên Số Khổ đã nói:
https://codeforces.com/contest/1581/problem/0

fen nào làm bài này đi

ans = 2n! // 2 % ( 10^9 + 7 )
:adore:

Lập Trình Viên Số Khổ · 30/9/21

vexliva đã nói:
ans = 2n! // 2 % ( 10^9 + 7 )

code chứ công thức tui cũng bik

Lập Trình Viên Số Khổ · 1/10/21

https://codeforces.com/contest/63/problem/C

đang nghĩ bài này, cảm thấy khá hack não, mn làm thử

nashwade · 1/10/21

trungpham90 đã nói:
Ko đồng ý nhé, ví dụ Arrays.sort(int[]), hoặc builder pattern.

Bác có thể giải thích thêm về Arrays.sort được không? Bác sort lại mảng thì ý nghĩa của mảng vẫn là chứa các dữ liệu, chỉ thay đổi vị trí các phần tử. Còn trong bài kia thì dùng mảng input như mảng đánh dấu là thay đổi hoàn toàn ý nghĩa của mảng rồi.

nashwade · 1/10/21

Lập Trình Viên Số Khổ đã nói:
https://codeforces.com/contest/63/problem/C

đang nghĩ bài này, cảm thấy khá hack não, mn làm thử

Duyệt hết qua tất cả 10000 số rồi check xem có 0/1 hay nhiều hơn 1 số thỏa input?

dienbien_online · 1/10/21

Có bài toán nào về quy hoạch nguyên k ae, post lên giải chơi

Lập Trình Viên Số Khổ · 1/10/21

https://codeforces.com/contest/430/problem/C

một bài về đảo bít, mn làm xem

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Member

Member

Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này