เส้นทางรวม IV ใน C++

สมมติว่าเรามีรายการของจำนวนเต็มที่เป็นตัวแทนของต้นไม้ไบนารีที่มีความลึกน้อยกว่า 5 หากความลึกของต้นไม้น้อยกว่า 5 ต้นไม้นี้สามารถแทนได้ด้วยรายการจำนวนเต็มสามหลัก สำหรับแต่ละจำนวนเต็มในรายการนี้ -

• หลักร้อยแสดงถึงความลึก D ของโหนดนี้ 1 <=D <=4

• ตัวเลขหลักสิบแสดงถึงตำแหน่ง P ของโหนดนี้ในระดับที่เป็นอยู่ในช่วง 1 ถึง 8 ตำแหน่งจะเหมือนกับตำแหน่งในแผนผังไบนารีแบบเต็ม

• หลักหน่วยใช้แทนค่า V ของโหนดนี้ 0 <=V <=9

เราต้องหาผลรวมของเส้นทางทั้งหมดตั้งแต่โคนจรดใบ

ดังนั้น หากอินพุตเป็น [113, 215, 221] ผลลัพธ์จะเป็น 12 ต้นไม้ที่แสดงรายการคือ

ผลรวมของเส้นทางคือ (3 + 5) + (3 + 1) =12.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งกราฟแผนที่

• กำหนดฟังก์ชัน dfs() ซึ่งจะรับ node, level, pos, sum เริ่มต้นด้วย 0

• isLeaf :=จริง

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[ระดับ + 1] อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • กำหนดหนึ่งคู่ temp :=กราฟ[ระดับ + 1, i]

  • ถ้า temp.first / 2 เหมือนกับ pos แล้ว −

    • isLeaf :=เท็จ

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

• ถ้า isLeaf ไม่ใช่ศูนย์ ดังนั้น −

  • ret :=ret + (ผลรวม + โหนด)

• จากวิธีหลักให้ทำดังนี้

• ยกเลิก :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • x :=nums[i]

  • val :=x mod 10

  • x :=x / 10

  • ตำแหน่ง :=x mod 10

  • x :=x / 10

  • ระดับ :=x

  • แทรก { (เลื่อน 1 ด้านซ้าย (ระดับ - 1) ครั้ง), val } ที่ส่วนท้ายของกราฟ[ระดับ]

• 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