Tối giản việc đọc tin nổi bật, comment chất lượng nhiều reaction trên voz cho các fen bận rộn.

VozFen.com: [kiến thức] [Học Tập] Topic thuật toán

@Ngày Được Tự Do
#1

[kiến thức] [Học Tập] Topic thuật toán

Ha…
HaLinhNHP

04/2016

@HaLinhNHP 04/2016
#2
Ưng 4
Dốt thuật toán, chỉ biết dùng mấy cái map array linh tinh

Se…
Setoid

11/2020

@Setoid 11/2020
#25
Ưng 5
Bài 2: mỗi phần tử của nums có 2 cách đặt dấu + và -
Thuật toán
  • sinh ra tất cả các trạng thái dùng đệ quy: 1 trạng thái gồm index của phần tử đang xét và tổng hiện tại; từ 1 trạng thái sinh ra con trái bằng phép +, sinh ra con phải bằng phép -
  • không gian trạng thái là 1 cây nhị phân hoàn hảo
  • nút lá là nút có index = số phần tử của nums, tại đây kiểm tra nếu tổng hiện tại = target thì số cách tăng lên 1.

Tối ưu hoá:
  • ghi nhớ các nút đã sinh để tránh lặp
  • nếu nút hiện tại có tổng bé hơn target thì không phải sinh nhánh con bên phải

Độ phức tạp: trường hợp xấu nhất là không có trạng thái nào lặp lại
=> O(2^n) cho cả time và space.

tr…
trungpham90

07/2012

@trungpham90 07/2012
#33
Ưng 8
Vàng quan điểm
Hóng cách giải ạ
Bài 2 cách trâu bò O(n*2^n), dùng bit manipulation,
Java:
public int numberOfWays(int[]data, int sum){
    int n = data.length;
    int result = 0;
    for(int z = 0; z < (1 << n); z++){
        int total = 0;
        for(int i = 0; i < n; i++){
            if(((1 << i) & z) != 0){
                total += data[i];
            }else{
                total -= data[i];
            }
        }
        result += total == sum ? 1 : 0;
    }
    return result;
}
Dùng qui hoạch động, top-down, O(n*m)
Java:
int[][][]dp;
public int numberOfWays(int []data, int sum){
    int max = 1000;
    dp = new int[2][data.length][max + 1];
    for(int[][]a : dp){
        for(int[]b : a){
            Arrays.fill(b, -1);
        }
    }
    return cal(0, 0, 0, sum, data);

}

public int cal(int index, int negative, int currentSum, int sum, int[]data){
    int current = negative == 1 ? -currentSum : currentSum;
    if(index == data.length){
        return current== sum ? 1 : 0;
    }
    if(dp[negative][index][currentSum] != -1){
        return dp[negative][index][currentSum];
    }
    int add = current + data[index];
    int sub = current - data[index];
    int result = cal(index + 1, add < 0 ? 1 : 0, abs(add), sum, data);
    result += cal(index + 1, sub < 0 ? 1 : 0, abs(sub), sum, data);
    return dp[negative][index][currentSum] = result;
}

Ng…
Ngày Được Tự Do

@Ngày Được Tự Do
#112
Ưng 12
Vàng quan điểm
Chào mọi người, nay mình lập thread này để học tập về thuật toán, mình sẽ post các bài tập về thuật toán từ các nguồn trên mạng thường xuyên lên để mọi người cùng thảo luận. Thank you!

Bài 1:

ni…
nipevt

11/2013

@nipevt 11/2013
#168
Ưng 6
Vàng quan điểm
Chắc các thím trong đây cũng có một số thím chơi bộ môn này nhỉ.
Các thím cứu em ca này với. Em tạch một testcase mà số nó lớn quá thành ra em không biết nó sai đâu.
Bài thứ 301 trong 300 bài code thiếu nhi nên em chịu
View attachment 576336
tính a <- a % n.

rồi tính a^b % n bằng cách:

a^b = (a^(b / 10))^10 * (a^(b % 10))

vậy từ công thức có thể thấy chỉ cần duyệt qua và tính (a^(b đến chữ số thứ i-1))^10 * (a^(chữ số thứ i của b)).

C++:
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll expt(ll a, ll b, ll m) {
    ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            ans = ans * a % m;
        a = a * a % m;
    }
    return ans;
}

int main() {
    string a, b; int n;
    cin >> a >> b >> n;
    ll as = 0;
    for (char c : a) {
        as = (as * 10 + (c - '0')) % n;
    }
    ll ans = expt(as, b[0] - '0', n);
    for (int i = 1; i < b.size(); ++i) {
        ans = expt(ans, 10, n) * expt(as, b[i] - '0', n) % n;
    }
    cout << ans;
    return 0;
}

vi…
vietdt89

07/2011

@vietdt89 07/2011
#237
Ưng 4
Em ưng ý kiến của bác này, tiếc là không thể thả tim, em chuẩn bị sang năm 3 rồi, mà thuật toán còn yếu quá, mấy bài từ mức dễ còn giải được lên mức trung bình là phân tích không nổi nữa không biết cải thiện được trình độ giải thuật không nữa chứ cứ mấy bài ngang mức trung bình nhiều lúc loay hoay gần 1 tiếng mà chưa giải được
đời còn dài. Hồi xưa mình cũng ngu thuật toán lắm, giờ phải lọ mọ đi học lại. Trên reddit nó liệt kê ra 14 pattern của thuật toán, bạn ôn theo pattern, mỗi pattern luyện đến khi nào chạy ra accepted mà k cần xem đáp án là ok. Khi đi PV đôi khi về ngôn ngữ có thể k quá thành thạo, nhưng nếu thuật toán tốt vẫn có thể pass. Nhất là mấy ông mới ra trường, ngoài thuật toán thì biết hỏi gì.Đồ án các bố trên trời dưới biển chán bỏ mẹ
Có thể nói giỏi thuật toán con đường sự nghiệp sẽ mở rộng hơn rất nhiều, k chỉ ở trong nước mà còn có cơ hội làm việc ở nước ngoài. Tây nó toàn hỏi thuật toán thôi, còn lại là SOLID, rồi domain liên quan

bu…
buihuynhson

@buihuynhson
#275
Ưng 4
Gạch 1
Mấy cái này toán cơ bản cấp 1, cấp 2 thôi (cùng lắm chút ít cấp 3).
Toán trong lập trình đa số học hiểu bản chất công thức ấy, chứ k phải kiểu đi giải loằng ngoằng như hồi học phổ thông đâu, áp dụng đc là đc
Trừ khi học machine learning, phải dùng đại số tuyến tính toán cao cấp A2, hoặc lúc tính big-O của mấy giải thuật phải tính toán phức tạp xíu, chứ ngoài ra cộng trừ nhân chia cơ bản là được

cu…
cuc gach

02/2012

@cuc gach 02/2012
#392
Ưng 4
Lâu không ai post gì mình share 1 bài medium leetcode, đề bài khá đơn giản: cho 1 string, tìm palindromic substring lớn nhất (palindromic string là string mà viết xuôi viết ngược như nhau).
Các thím thử sức xem làm trong bao lâu, mình để gợi ý và lời giải ở dưới.
Thím nào có lời giải hay hơn thì đóng góp luôn.
https://leetcode.com/problems/longest-palindromic-substring/
View attachment 685718

Dùng quy hoạch động, cải tiến từ bài toán longest common substring.
Lời giải của mình:
- Để tìm longest palindromic substring của s, ta có thể dựa vào ý tưởng tìm longest common substring của s và chuỗi đảo của chính nó (rs), vì khi đảo lại s thì longest palindromic substring không đổi
VD: s là xxxabcdcba và chuỗi đảo rsabcdcbaxxx, khi cho vào thuật toán lc substr sẽ tìm được abcdcba.

- Tuy nhiên longest common substring chưa chắc đã là palindromic string
VD: s là xxxabcdxxxdcba thì rs là abcdxxxdcbaxxx, khi tìm lcsubstr của 2 chuỗi sẽ ra dcba hoặc abcd, sai so với yêu cầu.
Vì thế khi tìm được 1 chuỗi con chung dài nhất, sẽ check xem chuỗi có phải là palindromic string không.

Thuật toán:

1. Áp dụng lcsubstr, tìm 1 chuỗi con chung của 2 s và rs.
2. Khi được 1 chuỗi con chung:
2.1 Nếu độ dài chuỗi <= độ dài longest palindromic substring hiện tại, quay lại bước 1.
2.2 Check xem chuỗi có phải palindromic string không, nếu không quay lại bước 1.
2.3 Update độ dài lớn nhất và vị trí của chuỗi trong s hoặc rs.
3. Sử dụng vị trí và độ dài tìm được để trả về chuỗi kết quả.

Code hơi messy chút vì viết cho chạy luôn, tối ưu thì sẽ chạy nhanh hơn và đỡ tốn memory hơn.
C++:
class Solution {
public:
    string longestPalindrome(string s) {
        string rs = std::string(s);
        std::reverse(rs.begin(),rs.end());
  
        int n = s.size();
  
        //if (n <= 1) return s;
  
        int arr[n+2][n+2];
        memset(arr, 0, sizeof arr);
        int maxVal = 0, maxX = 0, maxY = 0;
  
        for (int i = 1; i <= n+1; ++i) {
            for (int j = 1; j <= n+1; ++j) {
                if (i < n+1 && j < n+1 && s[i-1] == rs[j-1]) {
                    arr[i][j] = arr[i-1][j-1] + 1;
                }
                else {
                    if (arr[i-1][j-1] > maxVal) {
                        int size = arr[i-1][j-1];
                        bool check = true;
                        for (int pl = 0; pl <= size/2; ++pl) {
                            if (s[i-2-pl] != s[i-1-size+pl]) {
                                check = false;
                                break;
                            }
                        }
                  
                        if (check) {
                            maxX = i-2;
                            maxY = j-2;
                            maxVal = arr[i-1][j-1];
                        }
                    }
                }
            }
        }
  
        string ans = s.substr(maxX - maxVal + 1,maxVal);
  
        return ans;
    }
};

Bài này hồi lâu mình cũng có làm rồi tìm hiểu thì có thể giải bằng Manacher's Algorithm trong O(n). Nhưng sau này biết thêm nhiều thuật giải quyết string thì mình thấy Manacher không nên học làm gì. Bởi cái này là một dạng thuật Ad-hoc chỉ có thể dùng được trong một bài toán cụ thể. Thay vào đó thì nên học những dạng thuật toán học 1 làm 10.

Giờ quay lại làm lại mình cũng cố thử giải bài này bằng hash string + binary search.
Mọi người có thể tìm hiểu thêm về hash string ở 2 trang sau:
https://cp-algorithms.com/string/string-hashing.html
https://vnoi.info/wiki/algo/string/hash.md

Đầu tiên để cho đơn giản ta chèn thêm kí tự vào giữa string (ở đây mình dùng '#'). Mục đích của việc này là để khỏi cần phải chia ra 2 trường hợp tâm đối xứng lẻ và chẵn.
Để tiện gọi tên mình sẽ gọi string mới này là ss. Khi đó độ dài của một Palindromic Substring của ss có độ dài n sẽ bằng (n - 1) / 2 hay chính là bán kính đối xứng.

Ví dụ: (Tâm đối xứng gạch chân dưới)
aba => #a#b#a# => (7 - 1) / 2 = 3
abba => #a#b#b#a# => (9 - 1) / 2 = 4

Để sử dụng BS ta có nhận xét sau:
  • Nếu tồn tại một Palindromic Substring có bán kính đối xứng là l. Khi đó sẽ tồn tại các Palindromic Substring có bán kính [1 .. l - 1] trùng tâm.
  • Nếu không tồn tại một Palindromic Substring có bán kính đối xứng là l. Khi đó sẽ không tồn tại các Palindromic Substring có bán kính [l .. N].
Đến đây ta có thể sử dùng BS để tìm một Palindromic Substring có bán kính lớn nhất. Và dùng 2 lần hash xuôi và ngược để so sánh.

Time complexity O(nlogn).

Code:

C++:
class Solution {
public:
    #define ll long long
    const ll MOD = 1e9 + 9;
    static const int MAXN = 2003;
    const int p = 31;
    ll power[MAXN], hashT[MAXN], rhashT[MAXN];
   
    string ss = " #";
    string ans;
   
    void precompute() {
        power[0] = 1;
        hashT[0] = rhashT[ss.size()] = 0;
   
        for (int i = 1; i < ss.size(); ++i)
            power[i] = power[i - 1] * p % MOD;
   
        for (int i = 1; i < ss.size(); ++i)
            hashT[i] = (hashT[i - 1] * p + ss[i] - '#' + 1) % MOD;
   
        for (int i = ss.size() - 1; i >= 1; --i)
            rhashT[i] = (rhashT[i + 1] * p + ss[i] - '#' + 1) % MOD;
    }
   
    bool check(int len) {
        for (int i = 1 + len; i <= ss.size() - len - 1; ++i) {
            ll h = (hashT[i] - hashT[i - len - 1] * power[len + 1] + MOD * MOD) % MOD;
            ll rh = (rhashT[i] - rhashT[i + len + 1] * power[len + 1] + MOD * MOD) % MOD;
            if (h == rh) {
                ans = ss.substr(i - len, 2 * len + 1);
                return true;
            }
        }
   
        return false;
    }
   
    string longestPalindrome(string s) {
        ans = s[0];
        for (auto& x : s) ss = ss + x + "#";
        int l = 1, r = s.size();
        precompute();
   
        while (l < r) {
            int m = (l + r + 1) / 2;
   
            if (check(m)) l = m;
            else r = m - 1;
        }
   
        ans.erase(remove(ans.begin(), ans.end(), '#'), ans.end());
        return ans;
    }
};

Ki…
KimSoHyunGoddness

03/2021

@KimSoHyunGoddness 03/2021
#570
Ưng 5
Thím nắm thông tin của thím kia ở đâu vậy? Cho em nghe ké với
Nắm gì đâu bác. Cứ lâu lâu bác để ý là thấy liền à. NHiều khi ông đó sẽ xuất thần và nói những thứ cực kì cao siêu, chỉ có những người có trình độ cao mới hiểu ổng nói cái gì thôi, và sau khi xuất thần xong thì ổng lại nói mấy cái vớ vấn tới mức đần độn vcl, chỉ muốn chửi vào mặt.
Nên chỉ có thể là giả ngu giả khờ thôi.

th…
thuyduong2007

03/2013

@thuyduong2007 03/2013
#690
Ưng 4
Nay cuối tuần ngồi làm mấy bài hard chơi. Thấy bài này khá hay nên share lại cho ae cách giải quyết của mình.
https://leetcode.com/problems/trapping-rain-water-ii/
Input là một matrix chiều cao của các khối. Yêu cầu ouput ra lượng nước mà khối này có thể chứa đc. Ae coi hình bên dưới để hiểu rõ.

Ý tưởng ban đầu của mình là dùng cách xử lý giống như morphology trong image processing. Đó là dùng 1 cái kernel để chọn những khối cạnh bên. rồi scan toàn bộ khối này cho đến khi khi không có sự thay đổi về lượng nước chứa được nữa thì dừng lại. Cách này độ phức tạp là O(m*m*n*n). Mặc dù có độ phức tạp cao nhưng cách tiếp cận này mình thấy có thể code nhanh được.

C++:
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        vector<vector<int>> waterMap(heightMap.size(), vector<int>(heightMap[0].size(), 0));
        for (int i = 1; i < heightMap.size() - 1; i++) {
            for (int j = 1; j < heightMap[0].size() - 1; j++) {
                array<int, 3> neighbours = {heightMap[i][j-1] + waterMap[i][j-1],
                                            heightMap[i][j],
                                            heightMap[i-1][j] + waterMap[i-1][j]};
                waterMap[i][j] = *max_element(neighbours.begin(), neighbours.end()) - heightMap[i][j];
            }   
        }
        bool run = true;
        while(run) {
            run = false;
            for (int i = 1; i < heightMap.size() - 1; i++) {
                for (int j = 1; j < heightMap[0].size() - 1; j++) {
                    array<int, 4> neighbourHeight = {heightMap[i][j+1] + waterMap[i][j+1],
                                                   heightMap[i][j-1] + waterMap[i][j-1],
                                                   heightMap[i+1][j] + waterMap[i+1][j],
                                                   heightMap[i-1][j] + waterMap[i-1][j]};
                    int minHeight = *min_element(neighbourHeight.begin(),
                                                 neighbourHeight.end());
                    int newWater = minHeight > heightMap[i][j] ?
                        minHeight - heightMap[i][j] : 0;
                    run = newWater != waterMap[i][j] ? true : run;
                    waterMap[i][j] = newWater;
                }   
            }
        }
        int result = 0;
        for (auto row : waterMap) {
            for (auto cell : row) {
                result += cell;
            }
        }
        return result;
    }
};

Mặc dù pass được nhưng solution chạy rất chậm . Mình có tham khảo thì bài này nên dùng bfs kết hợp với minHeap thì độ phức tạp chỉ còn O(m*n). Anh em nào có hứng thú thì có thể coi visualization ở dưới và code lại.
Còn dưới đây là code của mình lấy ý tưởng từ video phía trên
C++:
struct cell{
    cell (int _x, int _y, int _val){
        x = _x;
        y = _y;
        val = _val;
    }
    int x;
    int y;
    int val;
};


bool operator < (const cell &o1, const cell &o2) {
        return o1.val > o2.val;
}

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) return 0;
        
        vector<vector<bool>> visited(heightMap.size(), vector<bool>(heightMap[0].size(), false));
        priority_queue<cell> minHeap;
        
        // add all cell in boundary into heap
        for (int j = 0; j < heightMap[0].size(); j++){
            minHeap.emplace(0,j,heightMap[0][j]);
            minHeap.emplace(heightMap.size() - 1,j,heightMap.back()[j]);
            visited[0][j] = true;
            visited[heightMap.size() - 1][j] = true;
        }
        for (int i = 1; i < heightMap.size() - 1; i++){
            minHeap.emplace(i,0,heightMap[i][0]);
            minHeap.emplace(i,heightMap[0].size() - 1,heightMap[i].back());
            visited[i][0] = true;
            visited[i][heightMap[0].size() - 1] = true;
        }
        
        
        array<pair<int, int>, 4> offsets = {make_pair(0,-1), make_pair(0,1),
                                            make_pair(-1,0), make_pair(1,0)};
        int curMax = -1;
        int result = 0;
        //bfs
        while (!minHeap.empty()) {
            auto top = minHeap.top();
            curMax = curMax > top.val ? curMax : top.val;
            minHeap.pop();
            for (auto off : offsets){
                int next_x = top.x + off.first;
                int next_y = top.y + off.second;
                if (next_x>=0 && next_x<heightMap.size()
                    && next_y>=0 && next_y<heightMap[0].size()
                    && !visited[next_x][next_y]) {
                    visited[next_x][next_y] = true;
                    if (heightMap[next_x][next_y] < curMax) {
                        result += curMax - heightMap[next_x][next_y];
                        minHeap.emplace(next_x, next_y, curMax);
                    } else{
                        minHeap.emplace(next_x, next_y, heightMap[next_x][next_y]);
                    }
                }
            }
        }
        return result;
    }
};

cl…
clonemasteruwu

05/2021

@clonemasteruwu 05/2021
#746
Ưng 4

bác nào rảnh cho em ý tưởng bài này với ạ @@
bài này ý tưởng khởi nguồn của nó là mobius inverse function.
Nhưng k cần biết cái trên, chỉ cần biết (tổng phi(d) với d chạy trên tập ước của n = n)
Kết quả = phi(d) * số tập con thực sự mà mỗi phần tử trong đó đều chia hết cho d (với d chạy từ 1 đến max(a_i), thường giới hạn khoảng 10^5-10^6)
Phi d có thể precompute, số tập hợp thì là 2^(số phần tử chia hết cho d) - 1, cũng precompute nốt
Độ phức tạp là khoảng n*sqrt(n)

Ki…
KimSoHyunGoddness

03/2021

@KimSoHyunGoddness 03/2021
#806
Ưng 4

Sau 3 ngày ngồi học linked list là cái quần què gì thì cuối cùng em cũng giải được bài toán này.
Mặc dù còn gà nhưng vẫn thấy cách làm của mình có vấn đề. Mong mấy bác chỉ giáo thêm

na…
nashwade

02/2012

@nashwade 02/2012
#1079
Ưng 4
ae thử bài này, đề bài đơn giản: "có bao nhiêu ước của N giai thừa mà chia hết cho D"

Phân tích N!, D thành tích thừa số nguyên tố. Lấy hiệu 2 mảng số mũ, nếu có số âm thì kết quả là 0. Không thì kết quả = tích(số mũ + 1).