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

  • Người tạo chủ đề Người tạo chủ đề unknowpc90
  • Ngày bắt đầu Ngày bắt đầu
Tuấn Mỏ đã nói:
Bài word-ladder mình dùng graph với BFS mà sao nó chỉ nhanh hơn 20% thôi nhỉ, Bác xem giúp có thể tối ưu thêm đoạn nào ko nhỉ?
C++: 
#include <queue>
#include <list>

class Solution {
public:
    struct Node
    {
        std::string str;
        int value = -1;
       
        bool visited = false;
       
        std::list<Node*> adj;
    };
   
    bool match(const string& str1, const string& str2)
    {
        int count = 0;
       
        for(int i = 0; i < str1.size(); ++i)
        {
            if(str1[i] != str2[i])
                count++;
        }
       
        return count <= 1;
    }
   
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        std::list<Node*> list;
       
        Node* begin = new Node;
        begin->str = beginWord;
        begin->value = -1;
        begin->visited = false;
       
        list.push_back(begin);
       
        for(const auto& iter : wordList)
        {
            if(iter == beginWord)
                continue;
           
            Node* node = new Node;
            node->str = iter;
            node->value = -1;
            node->visited = false;
           
            list.push_back(node);
        }
       
        for(const auto& iter : list)
        {
            for(const auto& iterInner : list)
            {
                if(iter != iterInner && match(iter->str, iterInner->str))
                {
                    iter->adj.push_back(iterInner);
                }
            }
        }
       
        std::queue<Node*> queue;
        begin->value = 1;
        queue.push(begin);
       
        while(!queue.empty())
        {
            Node* node = queue.front();
            queue.pop();
           
            if(node->visited)
                continue;
           
            node->visited = true;
           
            for(auto& iter : node->adj)
            {
                if(iter->visited)
                    continue;
               
                if(iter->value == -1)
                {
                    iter->value = node->value + 1;
                }
                else
                {
                    iter->value = std::min(iter->value, node->value + 1);
                }
               
                queue.push(iter);
            }
           
        }
       
        int nRet = 0;
       
        for(auto& iter : list)
        {
            if(iter->str == endWord)
            {
                nRet = iter->value;
                break;
            }
        }
       
        for(auto& iter : list)
        {
            if(iter)
            {
                delete iter;
                iter = nullptr;
            }
        }
       
        list.clear();      
       
        return nRet < 0 ? 0 : nRet;
    }
};
Nhấp để mở rộng...
Theo t thì bài này nó quan trọng lúc xử lý để build lên cái graph thôi. Cách build graph của bạn hiện tại chưa tối ưu. Độ phức tạp hiện tại của bạn là O(n*n*len(beginWord))

Ý tưởng để build graph của t là sẽ dùng một bảng hash, để lưu các từ trong wordList có thể transfom qua lại. Bằng cách lần lượt replace các chữ cái trong từng word xuất hiện trong wordList bằng một chữ Z (do chữ Z k nằm trong wordList). Cụ thể như sau.
vd:
hot => ["Zot" : ["hot"], "hZt" : ["hot"], "hoZ" : ["hot"], ]
dot => ["Zot" : ["hot", "dot"], "hZt" : ["hot"], "hoZ" : ["hot"], "dZt" : ["dot"], "doZ" : ["dot"]]

đến đây => hot, dot có thể transform qua lại bằng cách thay đổi 1 chữ cái.

Ngoài ra graph thì mình sẽ lưu index của word nằm trong wordList. Điều này giúp giảm memory cũng như thời gian chạy. Do khi dùng bfs thì điều kiện để kết thúc thay vì phải so sánh 2 chuỗi thì chỉ còn là so sánh 2 số.

C++: 
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int beginIdx = -1, endIdx = -1;
        for (int i = 0; i < wordList.size(); i++){
            if (wordList[i] == beginWord){
                beginIdx = i;
            } else if (wordList[i] == endWord){
                endIdx = i;
            }
        }
        if (endIdx < 0) return 0;
        if (beginIdx < 0){
            wordList.push_back(beginWord);
            beginIdx = wordList.size()-1;
        }
        
        unordered_map<int,vector<int>> table(wordList.size());
        buildGraph(wordList, table);
        vector<int> myQueue;
        myQueue.push_back(beginIdx);
        int numTrans = 1;
        while(!myQueue.empty()) {
            numTrans++;
            vector<int> tmpQueue;
            for (auto fromIdx : myQueue) {
                vector<int>& vec = table[fromIdx];
                for (auto toIdx : vec){
                    if (toIdx == endIdx) return numTrans;
                    tmpQueue.push_back(toIdx);
                }
                vec.clear(); //invalid the visted node
            }
            tmpQueue.swap(myQueue);
        }
        return 0;
    }
    
    void buildGraph(const vector<string>& wordList,
                             unordered_map<int,vector<int>> &table){
        unordered_map<string,vector<int>> tmpTable(wordList.size()*wordList.front().size());
        int len = wordList.front().size();
        for (int i = 0; i < wordList.size(); ++i){
            for (int j = 0; j < len; ++j){
                auto tmp = wordList[i];
                tmp[j] = 'Z';
                tmpTable[tmp].push_back(i);
            }
        }
        
        for (auto x : tmpTable){
            for (int i = 0; i < x.second.size(); ++i) {
                for (int j = 0; j < x.second.size(); ++j) {
                    if (i == j) continue;
                    table[x.second[i]].push_back(x.second[j]);
                }   
            }
        }
    }
};

Độ phức tạp bài này nằm ở chỗ build graph: O(n*len(beginWord)*len(beginWord)).
Mà bài này lúc làm bài test t cũng không làm kịp. :beat_brick:
 
https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
bài này tại sao kadane's algo lại không áp dụng được vậy các thím? Hồi trước e làm bài hình chữ nhật có tổng lớn nhất lớn nhất thì lại chạy đúng. E đọc disscus thì họ dùng binary search, dùng kadane pass được 2/3 testcase thôi. Và hình như tất cả các bài dạng 'no larger than K' thì đều không dùng Kadane được đúng k ạ?
code của e:
C++: 
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int u) {
        int n=matrix.size();
        int m=matrix[0].size();
        int res=INT_MIN;
        for(int i=0;i<m;i++){
            vector<int>sum(n,0);
            for(int j=i;j<m;j++){
                for(int k=0;k<n;k++){
                    sum[k]+=matrix[k][j];
                }
                int m=sum[0];
                for(int k=0;k<n;k++){
                    m=max(sum[k],sum[k]+m);
                    if(m<=u) res=max(res,m);
                }
            }
        }
        return res;
    }
};
 
Katsura janai đã nói:
https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
bài này tại sao kadane's algo lại không áp dụng được vậy các thím? Hồi trước e làm bài hình chữ nhật có tổng lớn nhất lớn nhất thì lại chạy đúng. E đọc disscus thì họ dùng binary search, dùng kadane pass được 2/3 testcase thôi. Và hình như tất cả các bài dạng 'no larger than K' thì đều không dùng Kadane được đúng k ạ?
code của e:
C++: 
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int u) {
        int n=matrix.size();
        int m=matrix[0].size();
        int res=INT_MIN;
        for(int i=0;i<m;i++){
            vector<int>sum(n,0);
            for(int j=i;j<m;j++){
                for(int k=0;k<n;k++){
                    sum[k]+=matrix[k][j];
                }
                int m=sum[0];
                for(int k=0;k<n;k++){
                    m=max(sum[k],sum[k]+m);
                    if(m<=u) res=max(res,m);
                }
            }
        }
        return res;
    }
};
Nhấp để mở rộng...

Bản chất hai bài khác nhau mà thím. Lấy ví dụ đơn giản cho dãy số toàn số dương thì lúc nào Kadane cũng lấy toàn bộ dãy là thấy đã sai rồi.
 
Katsura janai đã nói:
em hiểu rồi, nhưng em đã kèm điều kiện cái res<=target thì mới đổi kết quả, nhưng cũng chỉ pass 2/3
Nhấp để mở rộng...
Nhầm rồi, ví dụ dãy 1 2 2, target là 4 thì đáng nhẽ phải return 4 (2+2). Nhưng nếu xài LIS thuần sẽ trả về 5 (1+2+2) + điều kiện nó sẽ chỉ trả về 3 (1+2) thôi, vì nó lấy hẳn 1+2+2 chứ làm gì lấy 2+2 làm gì. :doubt:
 
Tập Làm Coder đã nói:
https://leetcode.com/problems/jump-game-ii/

ai giải thích bài này quy hoạch động với
Nhấp để mở rộng...

Buonnguqua6 đã nói:
Thề là tao đọc đề bài cũng éo hiểu
Nhấp để mở rộng...
Bài này dễ hiểu mà. Làm theo kiểu quy hoạch động như dưới đây là đơn giản, dễ hiểu nhất.

C++: 
class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size(), INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < nums.size(); ++i){
            for (int j = 1; j <= nums[i] && i + j < nums.size(); ++j){
                dp[i+j] = min(dp[i+j], dp[i] + 1);
            }
        }
        return dp.back();
    }
};
 
Tập Làm Coder đã nói:
Giải thích mình vs sao lại code như vậy lại chạy đc
@thuyduong2007
via theNEXTvoz for iPhone
Nhấp để mở rộng...
Cái dp là để tính số bước nhảy ít nhất cần để nhảy từ 0 đến i bất kỳ.
Giả sử từ i nhảy được trực tiếp đến n =>dp[n] = dp+1. Tuy nhiên sẽ có nhiều vị trí mà từ đó có thể nhảy được trực tiếp đến n => phải lấy min.
Cách này khá dễ tiếp cận, nhưng chưa tối ưu.
 
Sửa lần cuối:
Katsura janai đã nói:
https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
bài này tại sao kadane's algo lại không áp dụng được vậy các thím? Hồi trước e làm bài hình chữ nhật có tổng lớn nhất lớn nhất thì lại chạy đúng. E đọc disscus thì họ dùng binary search, dùng kadane pass được 2/3 testcase thôi. Và hình như tất cả các bài dạng 'no larger than K' thì đều không dùng Kadane được đúng k ạ?
code của e:
C++: 
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int u) {
        int n=matrix.size();
        int m=matrix[0].size();
        int res=INT_MIN;
        for(int i=0;i<m;i++){
            vector<int>sum(n,0);
            for(int j=i;j<m;j++){
                for(int k=0;k<n;k++){
                    sum[k]+=matrix[k][j];
                }
                int m=sum[0];
                for(int k=0;k<n;k++){
                    m=max(sum[k],sum[k]+m);
                    if(m<=u) res=max(res,m);
                }
            }
        }
        return res;
    }
};
Nhấp để mở rộng...

Pass 100%
C++: 
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        std::vector<std::vector<int>> dp(m + 1);
        for (int y = 0; y <= m; ++y)
        {
            dp[y].resize(n + 1, 0);
        }

        for (int y = 1; y <= m; ++y)
        {
            for (int x = 1; x <= n; ++x)
            {
                dp[y][x] = matrix[y - 1][x - 1] + dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1];
            }
        }

        int nMax = std::numeric_limits<int>::min();


        for (int x = 0; x < n; ++x)
        {
            for (int j = x; j < n; ++j)
            {
                std::vector<int> sum_row(m, 0);

                for (int y = 0; y < m; ++y)
                {
                    // col x -> j, row y
                    int sum = dp[y + 1][j + 1] + dp[y][x] - dp[y][j + 1] - dp[y + 1][x];
                    sum_row[y] = sum;
                }

                std::vector<int> int_col(m + 1, 0);

                for (int i = 1; i <= m; ++i)
                {
                    int_col[i] = sum_row[i - 1] + int_col[i - 1];
                }

                for (int p = 0; p < m; ++p)
                {
                    for (int q = p; q < m; ++q)
                    {
                        int sum = int_col[q + 1] - int_col[p];

                        if (sum <= k)
                            nMax = std::max(nMax, sum);
                    }
                }

            }
        }


        return nMax;
    }
};
 
Python
Các bác cho em hỏi để hiển thị dấu "." ở các con số thì làm như nào ạ
VD:
a=123456798
print(a)
>>123.456.789
Nhấp để mở rộng...
("Dấu . để ngăn cách các chữ số cho dễ nhìn, phải là dấu ''.'' chứ k được là dấu '','')
Đề bài nó bắt dấu "." chứ dấu "," em tra google được rồi ạ =((.
 
Python:
Số hoàn hảo là số có tổng các ước (không bao gồm nó) của nó bằng chính nó

Ví dụ: số 6 là số hoàn hảo vì số 6 có các ước 1, 2, 3. Các ước này cộng lại ra 6.

Nhập vào số nguyên dương a, kiểm tra xem a có phải là số hoàn hảo hay không.

a=int(input())
print('----------------------------')
dem=1
for i in range(a):
dem=dem+1
b=a//dem
if a%dem==0:
print(b)
VD: a=20
20
----------------------------
10
5
4
2
1

Cho em hỏi làm sao để mình tính tổng các số (''10 , 5 , 4 , 2 , 1") ạ. Các bác có cách nào làm bài trên không ạ cho em tham khảo với =((.Ít dùng hàm khó nhất có thể ạ
 
Sửa lần cuối:
N.Khanh đã nói:
Python:
Số hoàn hảo là số có tổng các ước (không bao gồm nó) của nó bằng chính nó

Ví dụ: số 6 là số hoàn hảo vì số 6 có các ước 1, 2, 3. Các ước này cộng lại ra 6.

Nhập vào số nguyên dương a, kiểm tra xem a có phải là số hoàn hảo hay không.

a=int(input())
print('----------------------------')
dem=1
for i in range(a):
dem=dem+1
b=a//dem
if a%dem==0:
print(b)
VD: a=20

20
----------------------------
10
5
4
2
1

Cho em hỏi làm sao để mình tính tổng các số (''10 , 5 , 4 , 2 , 1") ạ. Các bác có cách nào làm bài trên không ạ cho em tham khảo với =((.Ít dùng hàm khó nhất có thể ạ
Nhấp để mở rộng...
Python: 
a=int(input())
print('----------------------------')
dem=1
tong=0
for i in range(a):
    dem=dem+1
    b=a//dem
    if a%dem==0:
        print(b)
        tong += b
print(tong)
 
Tập Làm Coder đã nói:
https://leetcode.com/problems/jump-game-ii/

ai giải thích bài này quy hoạch động với
Nhấp để mở rộng...
Giải thích bằng cái ví dụ của nó nhé
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Nhấp để mở rộng...
  • Bạn bắt đầu nhảy ở vị trí đầu tiên trong array, có giá trị là 2, nghĩa là bạn được chọn 2 ô tiếp theo để nhảy tới, bạn có quyền nhảy vào một trong hai ô phía trước, không bắt buộc là ô nào cả.
  • Hai ô tiếp theo có giá trị lần lượt là 3, và 1. Bạn chỉ được chọn một giá trị để làm bước nhảy tiếp theo.
    • Nếu chọn 3: bạn được phép nhảy tới một trong ba ô kế tiếp có giá trị là 1, 1, 4
    • Nếu chọn 1: bạn được quyền nhảy tới một ô kế tiếp là có giá trị là 1
  • Dễ thấy nếu chọn giá trị 3, bạn nhảy được tới 3 ô kế tiếp, tới hết array luôn => giá trị cần chọn là 3, còn nếu chọn 1, bạn phải nhảy thêm một vài lần nữa mới tới hết array. => bạn chỉ nhảy 2 lần, từ vị trí số 0 (chứa 2), tới vị trí số 1 (chứa 3) => output = 2

Code của mình đây
C#: 
public class Solution {
    public int Jump(int[] nums) {
     
      var count = 0;
      var farthest = 0;
      var jumpEnd = 0;
       
      for(var i = 0; i < nums.Length - 1; i++){
        farthest = Math.Max(farthest,  i + nums[i]);
        if(i == jumpEnd){
          jumpEnd = farthest;
          count++;
        }
      }
     
      return count;
    }
}
 
Mới sáng mở mắt ra đớp được bài hard dễ vl, phần palindrome đúng kiểu cứ ốp qhđ là ra, được mấy bài hard phần này rồi, dạng cứ na ná nhau
UO1H3Fn.gif

https://leetcode.com/problems/palindrome-partitioning-iv/

C++: 
class Solution {
public:
    bool checkPartitioning(string s) {
        if(s.length()<3) return false;
        vector<vector<bool>>dp(s.length(),vector<bool>(s.length(),false));
        for(int i=0;i<s.length();i++) dp[i][i]=true;
        for(int i=s.length()-2;i>=0;i--){
            for(int j=i+1;j<s.length();j++){
                if((s[i]==s[j])&&(j-i<2||dp[i+1][j-1])) dp[i][j]=true;
            }
        }
        for(int i=1;i<s.length();i++){
            for(int j=i;j<s.length()-1;j++){
                if(dp[0][i-1]&&dp[i][j]&&dp[j+1][s.length()-1]) return true;
            }
        }
        return false;
    }
};
 
Bạn phải đăng nhập hoặc đăng ký để trả lời tại đây.

Chủ đề tương tự

atomwaffen
7 lý do khiến TPHCM ngày càng ngập nặng
2
Trả lời
30
Lượt xem
2K
SpaceXAI
SpaceXAI
Địa Ngục
Mưa lớn là đường Tô Ngọc Vân, chợ Thủ Đức thành sông: Ngóng dự án hơn 5.000 tỉ
Trả lời
15
Lượt xem
617
betappt
betappt
ChatGPT AI
(Trung Quốc) Singapore và Trung Quốc dẫn đầu thế giới về kết quả học tập
Trả lời
0
Lượt xem
166
ChatGPT AI
ChatGPT AI
Ma trận
[Dịch] Kết quả PISA 2025: Điểm đọc và toán giảm mạnh trên toàn thế giới
2 3 4
Trả lời
65
Lượt xem
5K
chenyouxing
chenyouxing
manoao
Khi sự không hoàn hảo làm nên bản sắc của phin cà phê Việt
Trả lời
1
Lượt xem
149
chocoboxx
chocoboxx

Thống kê chủ đề

Ngày tạo
unknowpc90,
Người trả lời cuối
Spaghetti Code,
Trả lời
1.460
Lượt xem
154.035

Chia sẻ trang này

Quay lại
Lên đầu trang