ចម្ងាយរវាងដំណោះស្រាយឡានក្រុង Leetcode


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

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

ចម្ងាយរវាងដំណោះស្រាយឡានក្រុង Leetcode

distance = [1,2,3,4], start = 0, destination = 1
1

ការពន្យល់ៈទីក្រុងដែលបានរៀបចំតាមលំដាប់រាងជារង្វង់ត្រូវបានបង្ហាញក្នុងរូបភាពខាងលើ។ នៅទីនេះឧទាហរណ៍យើងត្រូវបានផ្តល់ទីក្រុង 0 ជាទីក្រុងចាប់ផ្តើមនិងទីក្រុង 1 ជាទិសដៅ។ ដូច្នេះមានវិធីពីរយ៉ាងដែលអាចចាប់ផ្តើមពីទីក្រុង ០ និងទៅដល់ city១ ។ យើងអាចធ្វើដំណើរពីទីក្រុង ០ ទៅទី ១ រឺក៏យើងអាចដើរតាមផ្លូវពី ០ ទៅ ៣, ៣ ទៅ ២, ២ ទៅ ១. ឥឡូវនេះយើងនឹងគណនាចម្ងាយដែលត្រូវធ្វើពីមធ្យោបាយទាំងពីរហើយត្រឡប់ចម្ងាយអប្បបរមា។ ផ្លូវទីមួយ ០ ដល់ ១ ទាមទារឱ្យយើងធ្វើដំណើរចម្ងាយ = ១ ចំណែកផ្លូវផ្សេងទៀតតម្រូវឱ្យយើងធ្វើដំណើរចម្ងាយ = ៩។ ដូច្នេះចម្ងាយអប្បបរមាគឺ ១ ឯកតា។

distance = [1,2,3,4], start = 0, destination = 2
3

ការពន្យល់ៈដូចដែលយើងបានធ្វើនៅក្នុងឧទាហរណ៍ខាងលើយើងគណនាចម្ងាយទាំងទិសដៅហើយត្រឡប់អប្បបរមា។ ដោយសារផ្លូវទាំងពីរមានប្រវែង ៣ និង ៧ យើងជ្រើសរើសអប្បបរមាដែលពីរគឺ ៣ ។

វិធីសាស្រ្តសម្រាប់ចម្ងាយរវាងចំណតឡានក្រុងដំណោះស្រាយឡេឡេកូដ

បញ្ហាចម្ងាយរវាងចំណតឡានក្រុង Leetcode ដំណោះស្រាយបានស្នើសុំឱ្យរកចម្ងាយអប្បបរមាដែលត្រូវការដើម្បីធ្វើដំណើរប្រសិនបើចាប់ផ្តើមទីក្រុងនិងទីក្រុងគោលដៅត្រូវបានផ្តល់ឱ្យយើង។ បញ្ហាគឺសាមញ្ញពីព្រោះវាអាចមានវិធីតែពីរប៉ុណ្ណោះដើម្បីទៅដល់គោលដៅ។ មួយគឺប្រសិនបើយើងចាប់ផ្តើមក្នុងទិសដៅឆ្ពោះទៅមុខហើយមួយទៀតរំកិលទៅក្រោយហើយទៅដល់គោលដៅ។ យើងអាចរកចម្ងាយសម្រាប់ការធ្វើដំណើរមួយហើយមួយទៀតអាចត្រូវបានគណនាយ៉ាងងាយស្រួលដោយដកចម្ងាយនេះពីចំនួនសរុប។

ពិចារណាយើងត្រូវធ្វើដំណើរពីទីក្រុង ២ ទៅ ៥ ដែលមានចំនួនទីក្រុងសរុប ១០ ។ បន្ទាប់មកយើងក៏អាចទៅពី ២ ទៅ ៥ ឬពី ៥ ទៅ ១០ បន្ទាប់មក ១០ ទៅ ១ ហើយបន្ទាប់មក ១ ទៅ ២ ។ លទ្ធផល នៃសហជីពនៃផ្លូវទាំងពីរគឺជាសៀគ្វីទាំងមូល។ ដូច្នេះយើងអាចដកចម្ងាយដើម្បីទទួលបានចំងាយសម្រាប់ការធ្វើដំណើរផ្សេងទៀត។

លេខកូដ

លេខកូដ C ++ សម្រាប់ចម្ងាយរវាងចំណតឡានក្រុង Leetcode ដំណោះស្រាយ

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

int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    if(start>destination)swap(start, destination);
    int total = 0, first_path = 0;
    for(int i=0;i<distance.size();i++){
        if(i>=start && i<destination)
        first_path += distance[i];
        total += distance[i];
    }
    return min(total - first_path, first_path);
}

int main(){
    vector<int> distance = {1, 2, 3, 4};
    cout<<distanceBetweenBusStops(distance, 0, 1);
}
1

លេខកូដចាវ៉ាសំរាប់ចំងាយរវាងស្តុបឡានក្រុងឡេឡេលេខកូដ

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

class Main
{
  public static int distanceBetweenBusStops(int[] distance, int start, int destination) {
        if(start>destination){
            int t = start;
            start = destination;
            destination = t;
        }
        int total = 0, first_path = 0;
        for(int i=0;i<distance.length;i++){
            if(i>=start && i<destination)
            first_path += distance[i];
            total += distance[i];
        }
        return Math.min(total - first_path, first_path);
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] distance = {1, 2, 3, 4};
    System.out.println(distanceBetweenBusStops(distance, 0, 1));
  }
}
1

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

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

O (N), ដែល N ជាចំនួនទីក្រុង។ ចាប់តាំងពីយើងត្រូវធ្វើដំណើរឆ្លងកាត់ទីក្រុងទាំងអស់។ ភាពស្មុគស្មាញនៃពេលវេលាគឺលីនេអ៊ែរ។

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

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