ភាពខុសគ្នាដាច់ខាតអប្បបរមានៅក្នុងដំណោះស្រាយឡេអឹមអេសអេសប៊ី


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន google
មែកធាង

បញ្ហាភាពខុសគ្នាដាច់ខាតអប្បបរមានៅក្នុងដំណោះស្រាយប៊ី។ អេស។ ធី។ ឡេសកូដបញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យ មែកធាងស្វែងរកគោលពីរ។ ហើយអ្នកត្រូវបានគេតម្រូវឱ្យរកភាពខុសគ្នាដាច់ខាតអប្បបរមានៅក្នុងប។ ស។ សទាំងមូល។ ម។ ស។ ស។ ឬមែកធាងការស្វែងរកគោលពីរគ្មានអ្វីក្រៅពីដើមឈើដែលមានថ្នាំងមួយចំនួនដែលធ្វើតាមក្បួន។ ច្បាប់គឺថាអនុក្រឹត្យខាងឆ្វេងនៃថ្នាំងត្រូវតែមានតែថ្នាំងដែលមានតម្លៃតិចជាងថ្នាំងបច្ចុប្បន្ន។ ស្រដៀងគ្នានេះដែរសម្រាប់អនុក្រឹត្យត្រឹមត្រូវថ្នាំងត្រូវតែមានតម្លៃធំជាងថ្នាំងបច្ចុប្បន្ន។ ដូច្នេះដូចធម្មតាដំបូងយើងត្រូវមើលឧទាហរណ៍មួយចំនួនមុនពេលលោតចូលដំណោះស្រាយ។

ភាពខុសគ្នាដាច់ខាតអប្បបរមានៅក្នុងដំណោះស្រាយឡេអឹមអេសអេសប៊ី

1

ការពន្យល់ៈភាពខុសគ្នារវាងថ្នាំង [១, ២], [២, ៣], [៣, ៤], [៤, ៥] ទាំងអស់មានភាពខុសគ្នានៃ ១. ហើយគូផ្សេងទៀតសុទ្ធតែមានភាពខុសគ្នាកាន់តែច្រើន។ ដូច្នេះចម្លើយគឺ ១ ។

តារាង​មាតិកា

វិធីសាស្រ្តកម្លាំង Brute សម្រាប់ភាពខុសគ្នាដាច់ខាតអប្បបរមាក្នុងដំណោះស្រាយឡេអឹមអេសអេសអេស

បញ្ហាភាពខុសគ្នាដាច់ខាតអប្បបរមាក្នុងសូលុយស្យុងឡេអរលេខកូដបានស្នើសុំឱ្យយើងស្វែងរកភាពខុសគ្នាអប្បបរមារវាងថ្នាំងពីរនៅក្នុងមែកធាងស្វែងរកគោលពីរដែលបានផ្តល់ឱ្យ។ ដូច្នេះវិធីមួយដើម្បីរកចម្លើយគឺជ្រើសរើសយកកំពូលពីរឬថ្នាំងណាមួយនៃអេសអេសអេសនិងគណនាភាពខុសគ្នា។ យើងនឹងធ្វើបច្ចុប្បន្នភាពចម្លើយនៅពេលដែលយើងរកឃើញគូដែលមានភាពខុសគ្នាដាច់ខាតជាងគូមុន។ ដំបូងយើងអាចប្រើថ្នាំងពីរណាមួយហើយនៅចុងបញ្ចប់នៃដំណើរការ។ ចម្លើយនឹងត្រូវបានរក្សាទុកតាមអថេររៀងៗខ្លួន។ ដូច្នេះដើម្បីធ្វើឱ្យដំណើរការនេះមានលក្ខណៈធម្មតាយើងនឹងឆ្លង BST តាមលក្ខណៈអក្សរកាត់ហើយរក្សាទុកវាជាវ៉ិចទ័រ។ ដោយប្រើរង្វិលជុំដែលមានសំបុកពីរយើងនឹងបន្តគណនាភាពខុសគ្នាដាច់ខាតរវាងកំពូលទាំងពីរនៅលើដើមឈើ។

កូដកម្លាំង Brute

លេខកូដ C ++ សម្រាប់ភាពខុសគ្នាដាច់ខាតអប្បបរមាក្នុងដំណោះស្រាយឡេធីកូដអ៊ឹមអេស

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

struct TreeNode{
    int val;
    TreeNode *left, *right;
};

vector<int> inorder_traversal;
int ans = INT_MAX;

void inorder(TreeNode* root){
    if(root){
        inorder(root->left);
        inorder_traversal.push_back(root->val);
        inorder(root->right);
    }
}

int getMinimumDifference(TreeNode* root) {
    inorder(root);
    for(int i=1;i<inorder_traversal.size();i++)
        ans = min(ans, inorder_traversal[i]-inorder_traversal[i-1]);
    return ans;
}

int main(){
    TreeNode* root = new TreeNode();
    root->val = 1;
    root->right = new TreeNode();
    root->right->val = 5;
    root->right->left = new TreeNode();
    root->right->left->val = 3;
    root->right->left->left = new TreeNode();
    root->right->left->left->val = 2;
    root->right->left->right = new TreeNode();
    root->right->left->right->val = 4;
    cout<<getMinimumDifference(root);
}
1

លេខកូដចាវ៉ាសម្រាប់ភាពខុសគ្នាដាច់ខាតអប្បបរមាក្នុងដំណោះស្រាយឡេអឹមអេសអេជ

import java.util.*;
import java.lang.*;
import java.io.*;

class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
}

class Main {
    static ArrayList<Integer> inorder_traversal = new ArrayList<Integer>();
    static int ans = Integer.MAX_VALUE;
    
    public static void inorder(TreeNode root){
        if(root != null){
            inorder(root.left);
            inorder_traversal.add(root.val);
            inorder(root.right);
        }
    }
    
    public static int getMinimumDifference(TreeNode root) {
        inorder(root);
        for(int i=1;i<inorder_traversal.size();i++)
        	ans = Math.min(ans, inorder_traversal.get(i)-inorder_traversal.get(i-1));
        return ans;
    }
    
    public static void main (String[] args) throws java.lang.Exception
  {
    TreeNode root = new TreeNode();
      root.val = 1;
      root.right = new TreeNode();
      root.right.val = 5;
      root.right.left = new TreeNode();
      root.right.left.val = 3;
      root.right.left.left = new TreeNode();
      root.right.left.left.val = 2;
      root.right.left.right = new TreeNode();
      root.right.left.right.val = 4;
      System.out.print(getMinimumDifference(root));
  }
}
1

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

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

O (N ^ ២), ដោយសារយើងបានប្រើរង្វិលជុំចំនួន ២ ដើម្បីស្វែងរកភាពខុសគ្នាដាច់ខាតអប្បបរមាភាពស្មុគស្មាញនៃពេលវេលាសម្រាប់វិធីសាស្រ្តនេះក្លាយជាពហុគុណ។

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

O (N), ពីព្រោះយើងត្រូវរក្សាទុកការផ្លាស់ប្តូរខាងក្នុងវ៉ិចទ័រឬអារេមួយ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺមានលីនេអ៊ែរ។

វិធីសាស្រ្តល្អប្រសើរបំផុតសម្រាប់ភាពខុសគ្នាដាច់ខាតអប្បបរមាក្នុងដំណោះស្រាយឡេធីកូដអេសធីអេស

វិធីសាស្រ្តខាងលើសម្រាប់បញ្ហាភាពខុសគ្នាដាច់ខាតអប្បបរមាក្នុងសូលុយស្យុងឡេអឹមអេសហ្សិចសឺរត្រូវបានគេប្រើឆ្លងកាត់ការផ្លាស់ប្តូរ។ វាមិនត្រឹមតែត្រូវបានគេប្រើការឆ្លងកាត់តាមអាកាសប៉ុណ្ណោះទេប៉ុន្តែវាក៏ផ្ទុកវាផងដែរដែលធ្វើឱ្យវិធីសាស្រ្ត O (N) ទាក់ទងនឹងភាពស្មុគស្មាញនៃលំហ។ យើងក៏មិនបានប្រើការពិតដែលថាយើងមានអេសធីអេសហើយភាពខុសគ្នាដាច់ខាតអប្បបរមាអាចទទួលបានរវាងបញ្ឈរជាប់គ្នាពីរ។ ដោយសារការពិតមិនបានគិតពិចារណាយើងមានពេលវេលាស្មុគស្មាញ។

នៅក្នុងវិធីសាស្រ្តដែលបានធ្វើឱ្យប្រសើរយើងតាមដានថ្នាំងមុនទៅនឹងចំនុចកំពូលបច្ចុប្បន្ន។ ការធ្វើបែបនេះជួយឱ្យយើងរកឃើញភាពខុសគ្នាដាច់ខាតអប្បបរមាដោយអនុវត្តប្រតិបត្តិការវាយតម្លៃតែ N-1 ដង។ នេះក៏ជួយយើងឱ្យសម្រេចបាននូវភាពស្មុគស្មាញនៃលំហរថេរផងដែរពីព្រោះយើងមិនចាំបាច់រក្សាទុកការផ្លាស់ប្តូរខាងក្នុងទាំងមូលទេហើយទុកតែថ្នាំងមុនប៉ុណ្ណោះ។

លេខកូដប្រសើរសម្រាប់ភាពខុសគ្នាដាច់ខាតអប្បបរមាក្នុងដំណោះស្រាយឡេធីកូដអ៊ឹមអេសអេស

លេខកូដ C ++

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

struct TreeNode{
    int val;
    TreeNode *left, *right;
};

TreeNode* previous = NULL;
int ans = INT_MAX;

void inorder(TreeNode* root){
    if(root){
        inorder(root->left);
        if(previous != NULL){
            ans = min(ans, root->val - previous->val);
        }
        previous = root;
        inorder(root->right);
    }
}

int getMinimumDifference(TreeNode* root) {
    inorder(root);
    return ans;
}

int main(){
    TreeNode* root = new TreeNode();
    root->val = 1;
    root->right = new TreeNode();
    root->right->val = 5;
    root->right->left = new TreeNode();
    root->right->left->val = 3;
    root->right->left->left = new TreeNode();
    root->right->left->left->val = 2;
    root->right->left->right = new TreeNode();
    root->right->left->right->val = 4;
    cout<<getMinimumDifference(root);
}
1

ចាវ៉ាកូដ

import java.util.*;
import java.lang.*;
import java.io.*;

class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
}

class Main {
    static TreeNode prev = null;
    static int ans = Integer.MAX_VALUE;
    
    public static void inorder(TreeNode root){
        if(root != null){
            inorder(root.left);
            if(prev != null){
                ans = Math.min(ans, root.val - prev.val);
            }
            prev = root;
            inorder(root.right);
        }
    }
    
    public static int getMinimumDifference(TreeNode root) {
        inorder(root);
        return ans;
    }
    
    public static void main (String[] args) throws java.lang.Exception
  {
    TreeNode root = new TreeNode();
      root.val = 1;
      root.right = new TreeNode();
      root.right.val = 5;
      root.right.left = new TreeNode();
      root.right.left.val = 3;
      root.right.left.left = new TreeNode();
      root.right.left.left.val = 2;
      root.right.left.right = new TreeNode();
      root.right.left.right.val = 4;
      System.out.print(getMinimumDifference(root));
  }
}
1

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

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

O (N), ដោយសារតែយើងបានប្រើតែសកម្មភាពឆ្លងកាត់ដែលឆ្លងកាត់លើថ្នាំង N នៅលើដើមឈើ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

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

ឱ (១), ចាប់តាំងពីយើងបានប្រើតែចំនួនថេរនៃអថេរ។ ភាពស្មុគស្មាញនៃអវកាសក៏កាត់បន្ថយដល់ចន្លោះថេរដែរ។