Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

लक्ष्य योग वाले सबमैट्रिक्स की संख्या C++ में

मान लीजिए हमारे पास एक मैट्रिक्स है और एक लक्ष्य मान है, हमें उन गैर-खाली सबमैट्रिक्स की संख्या ढूंढनी है जिनका योग लक्ष्य के बराबर है। यहां एक सबमैट्रिक्स [(x1, y1), (x2, y2)] उन सभी सेल्स matrix[x][y] का समुच्चय है जहां x, x1 और x2 की रेंज में है और y, y1 और y2 की रेंज में है। दो सबमैट्रिक्स [(x1, y1), (x2, y2)] और [(x1', y1'), (x2', y2')] अलग हैं यदि उनका कोई निर्देशांक अलग है: जैसे, यदि x1, x1' के समान नहीं है।

उदाहरण के लिए, यदि इनपुट इस प्रकार है:

010
111
010

और लक्ष्य = 0, तो आउटपुट 4 होगा, क्योंकि चार 1x1 सबमैट्रिक्स हैं जिनमें केवल 0 है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • ans := 0

  • col := कॉलम की संख्या

  • row := पंक्तियों की संख्या

  • प्रत्येक पंक्ति के लिए प्रीफिक्स योग की गणना करें

  • दो कॉलम सीमाओं (i, j) के बीच सभी संभावित जोड़ों के लिए पुनरावृति करें

  • प्रत्येक जोड़ी के लिए, पंक्तियों के साथ 1D सरणी के रूप में उपसमस्या को हल करने के लिए हैश मैप का उपयोग करें

  • वर्तमान योग और लक्ष्य के बीच अंतर की आवृत्ति को ट्रैक करें

  • मान्य सबमैट्रिक्स की संख्या संचित करें

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) { 
        int ans = 0; 
        int col = matrix[0].size(); 
        int row = matrix.size(); 
        
        // पंक्ति-वार प्रीफिक्स योग की गणना करें
        for(int i = 0; i < row; i++){
            for(int j = 1; j < col; j++){
                matrix[i][j] += matrix[i][j - 1]; 
            } 
        } 
        
        unordered_map<int, int> m; 
        
        // सभी कॉलम जोड़ों के लिए पुनरावृति करें
        for(int i = 0; i < col; i++){
            for(int j = i; j < col; j++){
                m.clear(); 
                m[0] = 1; 
                int sum = 0; 
                
                // पंक्तियों को 1D सरणी के रूप में संसाधित करें
                for(int k = 0; k < row; k++){ 
                    int current = matrix[k][j]; 
                    if(i - 1 >= 0) current -= matrix[k][i - 1]; 
                    sum += current; 
                    ans += m[target - sum]; 
                    m[-sum]++; 
                } 
            } 
        } 
        return ans; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}}; 
    cout << (ob.numSubmatrixSumTarget(v, 0)); 
    return 0;
}

इनपुट

{{0,1,0},{1,1,1},{0,1,0}}, 0

आउटपुट

4
  1. - C++ में फाइबोनैचि संख्याओं के वर्गों का योग

    समस्या विवरण फाइबोनैचि श्रृंखला: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... जहां प्रत्येक संख्या पिछली दो का योग होती है। पहले n फाइबोनैचि संख्याओं के वर्गों का योग ज्ञात करें। उदाहरण: n = 4 F0=0, F1=1, F2=1, F3=2, F4=3 वर्ग: 0²+1²+1²+2²+3² = 0+1+1+4+9 = 15 उदाहरण कोड #include <iostream> using

  1. - C++ में एलिक्वोट अनुक्रम

    एलिक्वोट अनुक्रम संख्याओं का एक विशेष अनुक्रम है। अनुक्रम संख्या से ही शुरू होता है और अनुक्रम की अगली संख्या पिछले पदों के उचित भाजकों का योग होती है। आइए अनुक्रम का एक उदाहरण लेते हैं अवधारणा को बेहतर ढंग से सीखने के लिए: इनपुट: 8 आउटपुट: 8 7 1 0 व्याख्या:    8 के उचित भाजक 4, 2, 1 हैं।

  1. - C++ में ऐरे में न्यूनतम संख्या जोड़कर योग को सम बनाना

    मान लीजिए एक ऐरे है जिसमें कुछ संख्याएं हैं। हमें बताना है कि न्यूनतम कितनी संख्याएं जोड़ने से तत्वों का योग सम हो जाएगा। संख्या 0 से बड़ी होनी चाहिए। इसलिए यदि तत्वों का योग विषम है, तो हम 1 जोड़ेंगे, लेकिन यदि योग पहले से सम है, तो हम 2 जोड़कर इसे सम बनाएंगे। एल्गोरिदम addMinNumber(arr) begin