ເວລາ ຕຳ ່ສຸດທີ່ມາຢ້ຽມຢາມທຸກໆຈຸດ Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Bloomberg ເຟສບຸກ Medianet
Array Geometry

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

ເວລາ ຕຳ ່ສຸດທີ່ມາຢ້ຽມຢາມທຸກໆຈຸດ Leetcode Solution

[[1,1],[3,4],[-1,0]]
7

ຄຳ ອະທິບາຍ: ດັ່ງທີ່ສະແດງໃນຮູບພາບ, ພວກເຮົາຕ້ອງການເວລາ 3 ໜ່ວຍ ເພື່ອຍ້າຍຈາກຈຸດ ທຳ ອິດໄປຫາທີສອງ. ຫຼັງຈາກນັ້ນ, ໃຊ້ເວລາ 4 ໜ່ວຍ ເພື່ອຍ້າຍຈາກຈຸດທີສອງຫາຈຸດສຸດທ້າຍ. ດັ່ງນັ້ນ, ຈຳ ເປັນຕ້ອງໃຊ້ເວລາທັງ ໝົດ 7 ໜ່ວຍ.

ວິທີການ ສຳ ລັບການໄປຢ້ຽມຢາມທີ່ໃຊ້ເວລາຕ່ ຳ ສຸດທຸກຈຸດ Leetcode Solution

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

ແນວຄິດເບິ່ງຄືວ່າເຄັ່ງຄັດແຕ່ວ່າການຈັດຕັ້ງປະຕິບັດບັນຫາມັນຈະງ່າຍດາຍຫຼາຍ. ໃນທີ່ນີ້, ແທນທີ່ຈະເຮັດຂັ້ນຕອນແຍກຕ່າງຫາກບ່ອນທີ່ພວກເຮົາຍ້າຍເສັ້ນຂວາງແລະຫຼັງຈາກນັ້ນໄປໃນທິດທາງດຽວ. ພວກເຮົາພຽງແຕ່ພົບຄວາມແຕກຕ່າງສູງສຸດຂອງຄ່າ x ແລະ y ຂອງຈຸດປະຈຸບັນແລະຕໍ່ໄປ. ນີ້ເຮັດໃຫ້ພວກເຮົາມີສູດງ່າຍໆ ສຳ ລັບການເຄື່ອນໄຫວແຕ່ລະຄັ້ງ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບເວລາ ໜ້ອຍ ທີ່ສຸດທີ່ມາຢ້ຽມຢາມທຸກຈຸດ Leetcode Solution

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

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int ans = 0;
    int n = points.size();
    for(int i=1;i<n;i++){
        vector<int> cur = points[i], prev = points[i-1];
        int curVal = max(abs(cur[0] - prev[0]), abs(cur[1] - prev[1]));
        ans += curVal;
    }
    return ans;
}

int main(){
    vector<vector<int>> points({{1,1},{3,4},{-1,0}});
    cout<<minTimeToVisitAllPoints(points);
}
7

ລະຫັດ Java ສຳ ລັບເວລາ ໜ້ອຍ ທີ່ສຸດທີ່ມາຢ້ຽມຢາມທຸກຈຸດ Leetcode Solution

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

class Main
{
  public static int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        int n = points.length;
        for(int i=1;i<n;i++){
            int[] cur = points[i];
            int[] prev = points[i-1];
            int curVal = Math.max(Math.abs(cur[0] - prev[0]), Math.abs(cur[1] - prev[1]));
            ans += curVal;
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] points = {{1,1},{3,4},{-1,0}};
    System.out.println(minTimeToVisitAllPoints(points));
  }
}
7

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

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

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

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

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