सी++ में पथ योग IV

मान लीजिए कि हमारे पास पूर्णांकों की एक सूची है जो 5 से कम गहराई वाले बाइनरी ट्री का प्रतिनिधित्व कर रहा है। यदि किसी पेड़ की गहराई 5 से कम है, तो इस पेड़ को तीन-अंकीय पूर्णांकों की सूची द्वारा दर्शाया जा सकता है। इस सूची में प्रत्येक पूर्णांक के लिए -

• सैकड़ा अंक इस नोड की गहराई D को दर्शाता है, 1 <=D <=4.

• दहाई का अंक इस नोड की स्थिति P को 1 से 8 के बीच के स्तर में दर्शाता है। स्थिति एक पूर्ण बाइनरी ट्री के समान है।

• इकाई अंक का उपयोग इस नोड के मान V को दर्शाने के लिए किया जाता है, 0 <=V <=9.

हमें जड़ से पत्तियों तक सभी पथों का योग ज्ञात करना है।

इसलिए, यदि इनपुट [113, 215, 221] जैसा है, तो आउटपुट 12 होगा, सूची का प्रतिनिधित्व करने वाला पेड़ है

पथ योग है (3 + 5) + (3 + 1) =12.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक मानचित्र ग्राफ़ परिभाषित करें

• एक फ़ंक्शन को परिभाषित करें dfs(), यह नोड, स्तर, स्थिति लेगा, योग इसे 0 से प्रारंभ करेगा,

• isLeaf :=true

• प्रारंभ करने के लिए i:=0, जब i <ग्राफ का आकार [स्तर + 1], अद्यतन (i से 1 तक बढ़ाएं), करें -

  • एक जोड़ी अस्थायी परिभाषित करें:=ग्राफ[स्तर + 1, i]

  • अगर temp.first/2 pos के समान है, तो -

    • isLeaf :=false

    • dfs(temp.second, level + 1, temp.first, sum + node)

• यदि isLeaf गैर-शून्य है, तो -

  • रिट:=रिट + (योग + नोड)

• मुख्य विधि से निम्न कार्य करें,

• रिट:=0

• इनिशियलाइज़ i :=0 के लिए, जब i <अंकों का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -

  • एक्स:=अंक [i]

  • वैल:=एक्स मॉड 10

  • एक्स:=एक्स / 10

  • स्थिति :=x मॉड 10

  • एक्स:=एक्स / 10

  • स्तर :=x

  • ग्राफ के अंत में {(शिफ्ट 1 लेफ्ट साइड (लेवल -1) बार), वैल} डालें [लेवल]

• dfs(ग्राफ[1, 0].सेकंड, 1, ग्राफ[1, 0].प्रथम)

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int ret;
   map <int, vector < pair <int, int> > > graph;
   void dfs(int node, int level, int pos, int sum = 0){
      bool isLeaf = true;
      for (int i = 0; i < graph[level + 1].size(); i++) {
         pair<int, int> temp = graph[level + 1][i];
         if (temp.first / 2 == pos) {
            isLeaf = false;
            dfs(temp.second, level + 1, temp.first, sum + node);
         }
      }
      if (isLeaf) {
         ret += (sum + node);
      }
   }
   int pathSum(vector<int>& nums) {
      ret = 0;
      for (int i = 0; i < nums.size(); i++) {
         int x = nums[i];
         int val = x % 10;
         x /= 10;
         int pos = x % 10;
         x /= 10;
         int level = x;
         graph[level].push_back({ (1 << (level - 1)) + pos - 1, val });
      }
      dfs(graph[1][0].second, 1, graph[1][0].first);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {113,215,221};
   cout<<(ob.pathSum(v));
}

इनपुट

{113,215,221}

आउटपुट

12