ໄລຍະຫ່າງລະຫວ່າງທາງລົດເມຢຸດວິທີແກ້ໄຂ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ກູໂກ
Array

ບັນຫາໄລຍະຫ່າງລະຫວ່າງຢຸດລົດເມ Leetcode Solution ໃຫ້ພວກເຮົາ array ຂອງ ຈຳ ນວນອະທິບາຍໄລຍະທາງລະຫວ່າງຕົວເມືອງທີ່ຢູ່ຕິດກັນ. ບັນດາເມືອງແມ່ນມອບໃຫ້ເປັນລະບຽບຮຽບຮ້ອຍ. ສະນັ້ນ, ເມືອງສຸດທ້າຍແມ່ນຕິດຕາມດ້ວຍເມືອງ ທຳ ອິດ. ດຽວນີ້, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາໄລຍະຫ່າງຂັ້ນຕ່ ຳ ສຸດລະຫວ່າງສອງເມືອງທີ່ໃຫ້. ສະນັ້ນ, ກ່ອນທີ່ຈະກ້າວໄປສູ່ການແກ້ໄຂບັນຫາ. ຂໍໃຫ້ເບິ່ງບາງຕົວຢ່າງ.

ໄລຍະຫ່າງລະຫວ່າງທາງລົດເມຢຸດວິທີແກ້ໄຂ Leetcode

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

ຄຳ ອະທິບາຍ: ບັນດາເມືອງທີ່ຈັດລຽງເປັນວົງກົມແມ່ນສະແດງໃນຮູບຂ້າງເທິງ. ນີ້, ໃນຕົວຢ່າງ, ພວກເຮົາໄດ້ຮັບເມືອງ 0 ເປັນເມືອງເລີ່ມຕົ້ນແລະເມືອງ 1 ເປັນຈຸດ ໝາຍ ປາຍທາງ. ສະນັ້ນ, ມັນມີສອງວິທີທາງທີ່ເປັນໄປໄດ້ທີ່ຈະເລີ່ມຈາກເມືອງ 0 ແລະເຂົ້າຫາ city1. ພວກເຮົາພຽງແຕ່ສາມາດໄປຈາກເມືອງ 0 ເຖິງ 1. ຫຼືພວກເຮົາສາມາດເດີນຕາມເສັ້ນທາງຈາກ 0 ຫາ 3, 3, 2, 2 ເຖິງ 1. ດຽວນີ້, ພວກເຮົາຈະຄິດໄລ່ໄລຍະທາງທີ່ຈະເດີນທາງຈາກທັງສອງທາງແລະກັບຄືນໄລຍະທາງຕ່ ຳ ສຸດ. ເສັ້ນທາງ ທຳ ອິດ 0 ຫາ 1, ຮຽກຮ້ອງໃຫ້ພວກເຮົາເດີນທາງໄລຍະທາງ = 1, ໃນຂະນະທີ່ເສັ້ນທາງອື່ນຮຽກຮ້ອງໃຫ້ພວກເຮົາເດີນທາງໄລຍະທາງ = 9 ດັ່ງນັ້ນໄລຍະທາງຕ່ ຳ ສຸດແມ່ນ 1 ໜ່ວຍ.

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

ຄໍາອະທິບາຍ: ຄືກັບທີ່ພວກເຮົາໄດ້ເຮັດໃນຕົວຢ່າງຂ້າງເທິງ, ພວກເຮົາຄິດໄລ່ໄລຍະທາງທັງສອງທິດທາງ, ແລະສົ່ງຄືນຄ່າຕໍາ່ສຸດທີ່. ເນື່ອງຈາກສອງເສັ້ນທາງມີຄວາມຍາວ 3 ແລະ 7. ພວກເຮົາເລືອກເອົາ ຕຳ ່ສຸດທີ່ສອງນັ້ນແມ່ນ 3.

ວິທີການ ສຳ ລັບໄລຍະຫ່າງລະຫວ່າງບ່ອນຈອດລົດເມ Leetcode Solution

ບັນຫາໄລຍະຫ່າງລະຫວ່າງການຢຸດລົດເມ Leetcode Solution ໄດ້ຂໍໃຫ້ຊອກຫາໄລຍະທາງທີ່ຕ່ ຳ ສຸດທີ່ ຈຳ ເປັນໃນການເດີນທາງຖ້າເລີ່ມຕົ້ນເມືອງແລະເມືອງປາຍທາງໃຫ້ພວກເຮົາ. ບັນຫາແມ່ນງ່າຍດາຍເພາະວ່າມັນສາມາດມີພຽງສອງທາງທີ່ຈະໄປຮອດຈຸດ ໝາຍ. ໜຶ່ງ ແມ່ນຖ້າພວກເຮົາເລີ່ມຕົ້ນໃນທິດທາງທີ່ຈະກ້າວໄປຂ້າງ ໜ້າ ແລະອີກເບື້ອງ ໜຶ່ງ ກ້າວໄປຂ້າງຫລັງແລະໄປເຖິງຈຸດ ໝາຍ. ພວກເຮົາສາມາດຊອກຫາໄລຍະທາງ ສຳ ລັບ ໜຶ່ງ ໃນການເດີນທາງ, ແລະອີກອັນ ໜຶ່ງ ສາມາດຄິດໄລ່ໄດ້ງ່າຍໂດຍການຫັກໄລຍະທາງນີ້ຈາກ ຈຳ ນວນທັງ ໝົດ.

ພິຈາລະນາ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງໄປຈາກເມືອງ 2 ຫາ 5, ເຊິ່ງ ຈຳ ນວນຕົວເມືອງທັງ ໝົດ ແມ່ນ 10. ຫຼັງຈາກນັ້ນພວກເຮົາກໍ່ຈະໄປຈາກ 2 ເຖິງ 5 ຫຼືໄປຈາກ 5 ຫາ 10, ຫຼັງຈາກນັ້ນ 10 ຫາ 1, ແລະຫຼັງຈາກນັ້ນ 1 ຫາ 2. ຂອງສະຫະພາບຂອງທັງສອງເສັ້ນທາງແມ່ນວົງຈອນທັງ ໝົດ. ດັ່ງນັ້ນ, ພວກເຮົາສາມາດຫັກໄລຍະທາງເພື່ອໃຫ້ໄລຍະທາງ ສຳ ລັບການເດີນທາງອື່ນ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບໄລຍະທາງລະຫວ່າງຢຸດລົດເມ Leetcode Solution

#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

ລະຫັດ Java ສຳ ລັບໄລຍະທາງລະຫວ່າງຢຸດລົດເມ Leetcode Solution

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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ບ່ອນທີ່ N ແມ່ນ ຈຳ ນວນຕົວເມືອງ. ເນື່ອງຈາກວ່າພວກເຮົາຕ້ອງໄດ້ເດີນທາງຜ່ານທຸກເມືອງ. ຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ຕົວແປດຽວ. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນຄົງທີ່.