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

thuyduong2007 · 30/8/21

_Gia_Cat_Luong_ đã nói:
để thử đk làm xem sao, lập team chơi k fen ?

thích thì nhích thôi fen,

Aristides · 30/8/21

Cho một dãy số không được sắp theo thứ tự. Hãy trả về một dãy số gồm những phần tử là bình phương của các số từ dãy số ban đầu, được sắp theo thứ tự tăng dần, độ phức tạp thuật toán là O(n)
VD:

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Các bác cho tôi hỏi đoạn code này sai chỗ nào nhỉ?

C++:

  vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result;
        while(nums.empty() == false){
            int min = *min_element(nums.begin(), nums.end()); //Tìm phần tử nhỏ nhất
            min = min * min; // Bình phương
            result.push_back(min);
            auto iterator = find(nums.begin(), nums.end(), min);
            nums.erase(iterator); // Xóa phần tử nhỏ nhất
    }
        return result;
    }

thuyduong2007 · 30/8/21

Aristides đã nói:
Cho một dãy số không được sắp theo thứ tự. Hãy trả về một dãy số gồm những phần tử là bình phương của các số từ dãy số ban đầu, được sắp theo thứ tự tăng dần, độ phức tạp thuật toán là O(n)
VD:

Các bác cho tôi hỏi đoạn code này sai chỗ nào nhỉ?

C++:

vector<int> sortedSquares(vector<int>& nums) { vector<int> result; while(nums.empty() == false){ int min = *min_element(nums.begin(), nums.end()); //Tìm phần tử nhỏ nhất min = min * min; // Bình phương result.push_back(min); auto iterator = find(nums.begin(), nums.end(), min); nums.erase(it); // Xóa phần tử nhỏ nhất } return result; }

input là dãy có cả số âm và dương mà. Nên lấy ra min rồi bình phương thì đâu chắc chắn nó là nhỏ nhất nữa? btw, cách của thím hiện tại không thỏa mãn được yêu cầu O(n) nha. Sort mà O(n) thì chắc dùng counting sort.

Aristides · 30/8/21

thuyduong2007 đã nói:
input là dãy có cả số âm và dương mà. Nên lấy ra min rồi bình phương thì đâu chắc chắn nó là nhỏ nhất nữa? btw, cách của thím hiện tại không thỏa mãn được yêu cầu O(n) nha. Sort mà O(n) thì chắc dùng counting sort.

Bảo sao...
Nhân tiện, bác cho tôi hỏi độ phức tạp thuật toán của cái này là bao nhiêu:

C++:

 vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result;
       for( size_t i = 0; i < nums.size(); i++){
           int square = nums[i] * nums[i];
           result.push_back(square);
       }
        sort(result.begin(), result.end());
        return result;
    }

bmskyline · 30/8/21

Aristides đã nói:
Cho một dãy số không được sắp theo thứ tự. Hãy trả về một dãy số gồm những phần tử là bình phương của các số từ dãy số ban đầu, được sắp theo thứ tự tăng dần, độ phức tạp thuật toán là O(n)
VD:

Các bác cho tôi hỏi đoạn code này sai chỗ nào nhỉ?

C++:

vector<int> sortedSquares(vector<int>& nums) { vector<int> result; while(nums.empty() == false){ int min = *min_element(nums.begin(), nums.end()); //Tìm phần tử nhỏ nhất min = min * min; // Bình phương result.push_back(min); auto iterator = find(nums.begin(), nums.end(), min); nums.erase(it); // Xóa phần tử nhỏ nhất } return result; }

Bài này tìm vị trí giữa số âm với số dương rồi dùng 2 con trỏ có phải O(n) ko nhỉ

_Gia_Cat_Luong_ · 30/8/21

thuyduong2007 đã nói:
Có ai tham gia cái này k? đang bị kẹt ở 2 bài cuối. Ai làm rồi cho ý tưởng với.

Giải được bài C chapter 1 rồi, chapter 2 đúng khó hẳn. Có ý tưởng dùng QHĐ có thể giải được nhưng chắc k kịp nữa nên thôi.
Cơ mà cái này mình submit solution lên v thôi chứ k biết đúng sai à. Phải đợi end mới biết, chua dữ v.

thuyduong2007 · 30/8/21

Aristides đã nói:
Bảo sao...
Nhân tiện, bác cho tôi hỏi độ phức tạp thuật toán của cái này là bao nhiêu:

C++:

vector<int> sortedSquares(vector<int>& nums) { vector<int> result; for( size_t i = 0; i < nums.size(); i++){ int square = nums[i] * nums[i]; result.push_back(square); } sort(result.begin(), result.end()); return result; }

Dpt là O(nlogn) do cái sort

thuyduong2007 · 30/8/21

_Gia_Cat_Luong_ đã nói:
Giải được bài C chapter 1 rồi, chapter 2 đúng khó hẳn. Có ý tưởng dùng QHĐ có thể giải được nhưng chắc k kịp nữa nên thôi.
Cơ mà cái này mình submit solution lên v thôi chứ k biết đúng sai à. Phải đợi end mới biết, chua dữ v.

20k$ mà thím, phải chua chứ. T cũng làm đc 3 bài đầu thôi. Chưa biết đúng sai ntn.

_Gia_Cat_Luong_ · 30/8/21

thuyduong2007 đã nói:
20k$ mà thím, phải chua chứ. T cũng làm đc 3 bài đầu thôi. Chưa biết đúng sai ntn.

Nhân tiện cho hỏi thím dùng gì để dev C++ vậy ? Mình dùng windows, đang code chay rồi chạy bằng command line thấy bất tiện quá.

eraganxs · 31/8/21

_Gia_Cat_Luong_ đã nói:
Giải được bài C chapter 1 rồi, chapter 2 đúng khó hẳn. Có ý tưởng dùng QHĐ có thể giải được nhưng chắc k kịp nữa nên thôi.
Cơ mà cái này mình submit solution lên v thôi chứ k biết đúng sai à. Phải đợi end mới biết, chua dữ v.

Câu 2 đó dễ thôi mà có j đâu phải quy hoạch động fen. Cái input của nó nhỏ bằng cái lỗ mũi code đại cũng chạy đc mà, mới vòng giữ xe thôi.

eraganxs · 31/8/21

_Gia_Cat_Luong_ đã nói:
Nhân tiện cho hỏi thím dùng gì để dev C++ vậy ? Mình dùng windows, đang code chay rồi chạy bằng command line thấy bất tiện quá.

codeblock, ko thì vscode install gcc cũng code được.

Yêu em Thu Nga CN12 ptit · 31/8/21

https://www.spoj.com/PTIT/problems/CPPREA12/
bác nào xem thử hộ em bài này với, nó chính là bài maximum product subarray trên leetcode ấy, bài này cổ điển e code trên leetcode tẹo là xong. Không hiểu về đây mắc gì mà sub mấy chục lần vẫn chưa qua :canny:

C++:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        long long a[n];
        for(long long &x:a) cin>>x;
       long long maedh = a[0];
        long long  miedh= a[0];
        long long res = a[0];
        for(int i=1;i<n;i++){
            if(a[i]<0){
                swap(maedh, miedh);
            }
            maedh = max(a[i], a[i]*maedh);
            miedh = min(a[i], a[i]*miedh);
            res = max(maedh, res);
        }
        cout<<res<<endl;
    }
}

thuyduong2007 · 31/8/21

_Gia_Cat_Luong_ đã nói:
Nhân tiện cho hỏi thím dùng gì để dev C++ vậy ? Mình dùng windows, đang code chay rồi chạy bằng command line thấy bất tiện quá.

T code trên ubuntu, dùng vscode + gcc. mấy cái toolkit này quen cái nào thì xài cái đó thôi.

eraganxs đã nói:
Câu 2 đó dễ thôi mà có j đâu phải quy hoạch động fen. Cái input của nó nhỏ bằng cái lỗ mũi code đại cũng chạy đc mà, mới vòng giữ xe thôi.

Bài này t cũng dùng QHD. Thím quăng hết code lên đây cho ae tham khảo đc k?

eraganxs · 31/8/21

thuyduong2007 đã nói:
T code trên ubuntu, dùng vscode + gcc. mấy cái toolkit này quen cái nào thì xài cái đó thôi.

Bài này t cũng dùng QHD. Thím quăng hết code lên đây cho ae tham khảo đc k?

Brute force thôi anh, duyệt hết dòng và cột dòng(cột) nào chỉ có X với . Thì đếm số dấu chấm. Vứt kết quả vào cái một cái dictionary. Có kết quả đó rồi thì ++. Xử lý chút để loại bỏ trường hợp trùng. Tôi làm vậy thôi.

Sent from Xiaomi M2102J20SG using vozFApp

thuyduong2007 · 31/8/21

eraganxs đã nói:
Brute force thôi anh, duyệt hết dòng và cột dòng(cột) nào chỉ có X với . Thì đếm số dấu chấm. Vứt kết quả vào cái một cái dictionary. Có kết quả đó rồi thì ++. Xử lý chút để loại bỏ trường hợp trùng. Tôi làm vậy thôi.

Sent from Xiaomi M2102J20SG using vozFApp

này là câu 3 mà,

. có kq rồi đó ae. t bị sai bài 2. :beat_brick:

nashwade · 31/8/21

eraganxs đã nói:
Câu 2 đó dễ thôi mà có j đâu phải quy hoạch động fen. Cái input của nó nhỏ bằng cái lỗ mũi code đại cũng chạy đc mà, mới vòng giữ xe thôi.

Thế bác code đại có đúng không

_Gia_Cat_Luong_ · 31/8/21

eraganxs đã nói:
Brute force thôi anh, duyệt hết dòng và cột dòng(cột) nào chỉ có X với . Thì đếm số dấu chấm. Vứt kết quả vào cái một cái dictionary. Có kết quả đó rồi thì ++. Xử lý chút để loại bỏ trường hợp trùng. Tôi làm vậy thôi.

Sent from Xiaomi M2102J20SG using vozFApp

Đang nói bài C chapter 2 bác ơi

. Bài đào vàng ấy. Hồi tối ng ta công bố đáp án r mà đọc vẫn chưa hiểu mấy. Sáng nay mới đọc lại.

nashwade · 31/8/21

_Gia_Cat_Luong_ đã nói:
Nhân tiện cho hỏi thím dùng gì để dev C++ vậy ? Mình dùng windows, đang code chay rồi chạy bằng command line thấy bất tiện quá.

Mình code trên Mac cũng chỉ dùng Atom rồi chạy bằng Terminal thôi.

Buonnguqua6 · 31/8/21

_Gia_Cat_Luong_ đã nói:
Nhân tiện cho hỏi thím dùng gì để dev C++ vậy ? Mình dùng windows, đang code chay rồi chạy bằng command line thấy bất tiện quá.

GCC và Visual Studio Code nhé, config như video này

eraganxs · 31/8/21

nashwade đã nói:
Thế bác code đại có đúng không

Ko biết fen, thấy submit được với có tick xanh :sneaky:

Sent from Xiaomi M2102J20SG using vozFApp

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

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Member

Member

Senior Member

Member

Member

Senior Member

Member

Member

Member

Senior Member

Senior Member

Senior Member

Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này