ការឆ្លងកាត់អង្កត់ទ្រូងនៃមែកធាងគោលពីរ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon រោងចក្រ និយមជ្រុល Fourkites ក្រុមហ៊ុន Oracle PayU Quora
មែកធាងគោលពីរ មែកធាង ការឆ្លងកាត់ដើមឈើ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ ដ្យាក្រាមអង្កត់ទ្រូងនៃមែកធាងគោលពីរ” បញ្ជាក់ថាអ្នកត្រូវបានគេផ្តល់ឱ្យនូវមែកធាងគោលពីរហើយឥឡូវអ្នកត្រូវរកមើលអង្កត់ទ្រូងសម្រាប់ដើមដែលបានផ្តល់ឱ្យ។ នៅពេលដែលយើងឃើញដើមឈើមួយពីទិសដៅខាងលើស្តាំ។ ថ្នាំងដែលអាចមើលឃើញសម្រាប់យើងគឺជាទិដ្ឋភាពអង្កត់ទ្រូងនៃមែកធាងគោលពីរ។

ឧទាហរណ៍

ការឆ្លងកាត់អង្កត់ទ្រូងនៃមែកធាងគោលពីរ

2 7
3 4
5 6

ការពន្យល់

អង្កត់ទ្រូងដំបូងមានថ្នាំង 2, 7 នៅក្នុងនោះ។ បន្ទាប់មកអង្កត់ទ្រូងទីពីរមាន ៣, ៤ ប្រហាក់ប្រហែលនឹងអង្កត់ទ្រូងទីបី ៥, ៦ ។ ដូច្នេះលទ្ធផលបានបោះពុម្ពតាមរបៀបមួយដែលធាតុពីអង្កត់ទ្រូងដូចគ្នាមាននៅក្នុងបន្ទាត់តែមួយ។

វិធីសាស្រ្ត

ការឆ្លងកាត់អង្កត់ទ្រូងនៃមែកធាងគោលពីរ

បញ្ហាស្នើឱ្យយើងបោះពុម្ពថ្នាំងដែលអាចមើលឃើញពីទិសដៅពីលើទៅស្តាំ។ ដូច្នេះតើយើងត្រូវដោះស្រាយបញ្ហាយ៉ាងដូចម្តេច?

យើងនឹងធ្វើការផ្លាស់ប្តូរនៃដើមគោលពីរ។ នៅពេលធ្វើដូចនេះយើងនឹងតាមដានចម្ងាយក្នុងទិសដៅអង្កត់ទ្រូង។ រាល់ពេលដែលយើងរំកិលទៅទិសខាងឆ្វេងយើងបន្ថែម ១ ទៅចំងាយអង្កត់ទ្រូងហើយបើយើងផ្លាស់ទៅទិសដៅត្រឹមត្រូវយើងមិនបន្ថែមតំលៃចំងាយទេ។ ដូច្នេះពេលកំពុងធ្វើនេះយើងនឹងតាមដានថ្នាំងដែលបានចូលមើលក្នុងក ផែនទី។ យើងនឹងបង្កើតផែនទីដែលមានចម្ងាយអង្កត់ទ្រូងជាគន្លឹះនិងវ៉ិចទ័រដែលជាតម្លៃ។ ពីព្រោះយើងនឹងបន្ថែមថ្នាំងដែលមានចម្ងាយអង្កត់ទ្រូងជាវ៉ិចទ័រ។ ហើយដូចដែលយើងនឹងឆ្លងកាត់ទាំងមូល ដើមឈើ។ បន្ទាប់ពីការឆ្លងកាត់យើងនឹងរក្សាថ្នាំងក្នុងវ៉ិចទ័រតាមចម្ងាយអង្កត់ទ្រូងរបស់វា។

បន្ទាប់ពីការគណនាទាំងអស់នេះគ្រាន់តែបោះពុម្ពធាតុនៅក្នុងផែនទីនៅពេលបំបែកថ្នាំងពីវ៉ិចទ័រនីមួយៗ។

កូដ C ++ ដើម្បីបោះពុម្ពអង្កត់ទ្រូងអង្កត់ទ្រូងនៃមែកធាងគោលពីរ

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

struct node{
    int data;
    node *left, *right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

int main(){
    node *root = create(2);
    root->left = create(3);
    root->right = create(7);
    root->left->left = create(5);
    root->left->right = create(4);
    root->left->right->left = create(6);

    map<int, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

កូដចាវ៉ាដើម្បីបោះពុម្ពអង្កត់ទ្រូងនៃមែកធាងគោលពីរ

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = tmp.right = null;
      return tmp;
  }

  static void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  public static void main(String[] args){
    node root = create(2);
      root.left = create(3);
      root.right = create(7);
      root.left.left = create(5);
      root.left.right = create(4);
      root.left.right.left = create(6);

      Map<Integer, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (NlogN), ដោយសារតែយើងបានឆ្លងកាត់ដើមឈើហើយបានធ្វើបច្ចុប្បន្នភាពតម្លៃ។ ដោយសារតែយើងបានប្រើផែនទីការបញ្ចូលការលុបនិងការស្វែងរកត្រូវបានធ្វើឡើងនៅក្នុងពេលវេលា O (logN) ។

ភាពស្មុគស្មាញនៃលំហ

O (N), ពីព្រោះយើងកំពុងទុកថ្នាំងទាំងអស់នៅក្នុងផែនទី។ ភាពស្មុគស្មាញនៃលំហគឺលីនេអ៊ែរ។