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

#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;
    }
};

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]);
                }   
            }
        }
    }
};

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;
    }
};

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();
    }
};

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;
    }
};

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)

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;
    }
}