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

[nashwade]

int solve(vector<int> a) {
    int n = size(a);
    // f[i] = length of longest subsequence of form [j, j + 1, j + 2, ..., i]
    vector<int> f(n + 1);
    for (int x : a)
        f[x] = f[x - 1] + 1;
    return n - *max_element(begin(f), end(f));
}

 

[thaygiao3]

Không liên quan nhưng em thấy toàn pro nên cho em hỏi xíu, em năm nay ms vào đại học nên ms tập tành học đc c++ cơ bản, bây h muốn học thuật toán thì có trang web nào hay sách nào dạy dễ hiểu và đầy đủ ko ạ, cho em xin vs,

 

[Lập Trình Viên Số Khổ]

Không liên quan nhưng em thấy toàn pro nên cho em hỏi xíu, em năm nay ms vào đại học nên ms tập tành học đc c++ cơ bản, bây h muốn học thuật toán thì có trang web nào hay sách nào dạy dễ hiểu và đầy đủ ko ạ, cho em xin vs,

Có youtube, geeksforgeeks nhiều kiến thức, còn luyện tập thì có leetcode

via theNEXTvoz for iPhone

 

[Kân team]

theo mình thấy code theo cách j thì cũng phải 2 vòng lặp, như bác kia dùng stl std::adjacent_find(it, end(p), std::greater<int>{} thực ra cũng là 1 vòng lặp ở trong.

gán jt = find từ it rồi gán it = jt thì tuy 2 vòng lặp lồng nhau nhưng chỉ mất có O(n) thoy

ví dụ mảng index là 2 3 1 0 4 muốn tách thành 2 3, 1, 0 4 là các mảng con liên tục tăng dần thì thực tế là đi tìm 2 cặp số a b liên tục nhau mà a > b nên xài adjacent_find. jt = adjacent_find(greater) kia sẽ tìm tới vị trí số 3 vì 3>1, ++jt để tới số 1 cho distance(it, jt) ra 2 là mảng con 2 3 tăng dần. Tiếp theo gán it = jt thì mảng 2 3 1 0 4 coi như chỉ còn 1 0 4 thoy. Mỗi cặp adjacent chỉ xét 1 lần nên tổng cộng là O(n) chứ ko phải kiếm từ đầu mà O(n^2)

tôi code điêu để gà mờ đọc vô ko hiểu, đáng lẽ ko nên viết bài giải thích

 

[nashwade]

tôi code điêu để gà mờ đọc vô ko hiểu, đáng lẽ ko nên viết bài giải thích

Bác code gán biến trong if thì đúng là đọc đau mắt thật, lại còn lạm dụng STD nữa. Thay vì dùng distance thì chỉ cần (jt - it) thôi

 

[Kân team]

distance cho nó có mùi iterator hơn là con chỏ

cái này cười ỉa thặc: https://stackoverflow.com/questions...-get-the-index-of-an-iterator-of-an-stdvector

I would prefer std::distance(vec.begin(), it) as it will allow me to change the container without any code changes. For example, if you decide to use std::list instead of std::vector

thằng thì bảo thích xài distance để dễ bề đổi kiểu container

I would prefer it - vec.begin() precisely for the opposite reason given by Naveen: so it wouldn't compile if you change the vector into a list. If you do this during every iteration, you could easily end up turning an O(n) algorithm into an O(n^2) algorithm.

thằng thì bảo ngược lại

bài này có đổi làm list cũng O(n) thoy

 

[Yêu em Thu Nga CN12 ptit]

Dễ vl mà e không nghĩ ra, code có 3 dòng mà nghĩ phức tạp quá. Cảm ơn mấy bác pass rồi

 

[Yêu em Thu Nga CN12 ptit]

int solve(vector<int> a) {
    int n = size(a);
    // f[i] = length of longest subsequence of form [j, j + 1, j + 2, ..., i]
    vector<int> f(n + 1);
    for (int x : a)
        f[x] = f[x - 1] + 1;
    return n - *max_element(begin(f), end(f));
}

Ốp nguyên code của bác vào nhanh nhất lớp luôn

 

[tuanhpg]

muốn cầy chút algorithm mà k có thời gian. Thôi để khi nào interview cầy 1 thể

Sent from Samsung SM-G960F using vozFApp

 

[Thạch Sanh_4.0]

Đây là đoạn code dùng để nhập giá trị của n bằng cách gọi Read(n). nó tương tự với câu lệnh cin >> n. Cho mình hỏi khi nào thì lên dùng cách viết này để nhập giá trị cho n ?? Mình thấy người ta dùng nó trong 1 khóa học

 

[Tuấn Mỏ]

View attachment 839111
Đây là đoạn code dùng để nhập giá trị của n bằng cách gọi Read(n). nó tương tự với câu lệnh cin >> n. Cho mình hỏi khi nào thì lên dùng cách viết này để nhập giá trị cho n ?? Mình thấy người ta dùng nó trong 1 khóa học

code này để nhập vào dạng số mà nằm lẫn với ký tự khác, ví dụ absdfs12345dfd thì nó vẫn nhập vào đc n=12345

 

[Dev Tập Sự]

Mình tạo top pic không nhằm mục đích gì khác tạo động lực làm giải thuật hằng ngày. Dù bận thế nào cũng sẽ cố làm giải thuật mỗi ngày.

Có công mài code có ngày 300

Link github của mình: Hằng ngày mình sẽ post các bài giải thuật (problem + solution) các thím có thể vào tham khảo.
https://github.com/jeanJacquesRousseauVietnam

 

[cs_50i]

Những thuật toán cơ bản như
Numerical, String, Counting,Matrix,Geometry,Sequence,Graph,Sorting,Searching. Đúng nghĩa đi làm chỉ cần nắm được cơ bản. Còn lại thì vào ngành nào luyện kỹ thuật toán của ngành đấy thôi. Kinh nghiệm của tôi là vậy chứ mỗi ngày luyện những thuật toán chẳng áp dụng gì cho công việc. Nay luyện mai mốt quên ngay ấy mà. Tôi là một điển hình . Cuối cùng ngộ ra chân lý thế rồi chuyên tâm luyện thuật toán + toán cơ bản ngành của mình hay dùng như sin cos tính hệ số góc, phương trình tiếp tuyến,đồ thị sin cos...Tích phân thì dùng cho tính toán tối ưu không gian.

 

[minh_la_boy]

Mình mới đọc blog họ bảo nắm vứng 10 thuật toán này, các tiền bối có tài liệu gì ko chia sẻ cho em với
10 thuật toán: đệ quy, Sắp xếp, tìm kiếm nhị phân, tìm kiếm, thuật toán băm, thuật toán tham lam, thuật toán chia và chinh phục, thuật toán quay lui, lập trình động, thuật toán so khớp chuỗi.

 

[Drinkfood1905]

Mình mới đọc blog họ bảo nắm vứng 10 thuật toán này, các tiền bối có tài liệu gì ko chia sẻ cho em với
10 thuật toán: đệ quy, Sắp xếp, tìm kiếm nhị phân, tìm kiếm, thuật toán băm, thuật toán tham lam, thuật toán chia và chinh phục, thuật toán quay lui, lập trình động, thuật toán so khớp chuỗi.

Mình nghĩ ôn chắc data structure đã r học thuật toán sau

 

[Dev Tập Sự 2]

Để tạo động lực code giải thuật hằng ngày mình quyết định lập topic này, anh em nào thích có thể vào trao đổi và làm cùng cho vui rất welcome anh em.

Day 1:
bài 1: Source: https://leetcode.com/problems/two-sum/
solution: TwoSum
bài 2: tham khảo trên leetcode và tự chế thêm vì trên leetcode bài gốc dễ quá
solution: MergeSortArray
/**
* You are given two integer arrays nums1 and nums2
* Merge nums1 and nums2 into a single array sorted in non-decreasing order and eliminate the zeros of the two arrays.
*/

/**
* Example 1:
*
* Input: nums1 = [3,1,2,0,4,0], nums2 = [5,5,6],
* Output: [1,2,3,4,5,5,6]
*/

/**
* Example 2:
*
* Input: nums1 = [0,1,0,0,4,0], nums2 = [5,7,6,0,2],
* Output: [1,2,4,5,6,7]
*/

Source code trên github của mình: https://github.com/jeanJacquesRousseauVietnam/Algorithm-with-Java

 

[monster_hunter]

Mình nghĩ ôn chắc data structure đã r học thuật toán sau

bác này nói chuẩn nè. mún apply thuật toán thì phải biết về data structure trước. thế nên câu Cấu Trúc Dữ Liệu và Giải Thuật lun đi với nhau

 

[Yêu em Thu Nga CN12 ptit]

Cái bit manipulation em có đọc qua rồi, mà không biết nó có quan trọng lắm không vậy các thím? Phỏng vấn các kiểu chẳng hạn

 

[emanonn]

Các bác cho em hỏi, đối với bài toán tháp hà nội (trường hợp 3 cọc, n đĩa) trong trí tuệ nhân tạo thì dùng thuật toán nào là tốt nhất ạ?

 

[mrteeq]

Mấy bác cho em hỏi, làm sao để xử lý chuyển số thành chuỗi theo như logic:
1-26:a-z
27:aa và đến zz là 703, 704 lại quay lại aaa.
Tks các bác!