מרחק בין תחנות אוטובוס פתרון Leetcode


רמת קושי קַל
נשאל לעתים קרובות Google
מערך

הבעיה מרחק בין תחנות אוטובוס פתרון Leetcode מספק לנו מערך מספרים שלמים המתארים את המרחק בין הערים הסמוכות. הערים ניתנות בסדר מעגלי. אז, העיר האחרונה ואחריה העיר הראשונה. כעת אנו נדרשים לברר את המרחק המינימלי בין שתי הערים הנתונות. אז לפני שעוברים לפיתרון. בואו נראה כמה דוגמאות.

מרחק בין תחנות אוטובוס פתרון Leetcode

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

הסבר: הערים המסודרות בסדר מעגלי מוצגות בתמונה למעלה. הנה, בדוגמה, אנו מספקים את העיר 0 כעיר ההתחלתית ואת העיר 1 כיעד. לכן, ישנן שתי דרכים אפשריות להתחיל מעיר 0 ולהגיע לסיטי 1. או שאנחנו יכולים פשוט לעבור מעיר 0 עד 1. או שאנחנו יכולים ללכת בדרך בין 0 ל -3, 3 ל -2, 2 ל 1. כעת נחשב את המרחק שיש לעבור משני הכיוונים ונחזיר את המרחק המינימלי. הנתיב הראשון 0 עד 1, דורש מאיתנו מרחק מרחק = 1, ואילו הנתיב השני מחייב אותנו מרחק נסיעה = 9. לפיכך המרחק המינימלי הוא יחידה אחת.

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

הסבר: בדיוק כמו שעשינו בדוגמה שלעיל, אנו מחשבים את המרחק בשני הכיוונים ומחזירים את המינימום. מכיוון ששני הנתיבים הם באורך 3 ו- 7. אנו בוחרים את המינימום של השניים שהוא 3.

גישה למרחק בין תחנות אוטובוס לפתרון Leetcode

הבעיה מרחק בין תחנות אוטובוס פתרון Leetcode התבקש למצוא את המרחק המינימלי הדרוש לנסיעה אם ניתנים לנו עיר מתחילה ועיר יעד. הבעיה פשוטה מכיוון שיכולות להיות רק שתי דרכים להגיע ליעד. האחת היא אם נתחיל בכיוון להתקדם והשני לנוע אחורה ולהגיע ליעד. אנו יכולים למצוא את המרחק לאחד הנסיעות, ואת השני ניתן לחשב בקלות על ידי הפחתת מרחק זה מהסך הכל.

קחו בחשבון, עלינו לעבור מעיר 2 ל -5, שם המספר הכולל של ערים הוא 10. ואז נעבור בין 2 ל 5. או שנלך מ 5 ל 10, ואז 10 ל 1, ואז 1 ל 2. התוצאה של איחוד שני הנתיבים הוא המעגל כולו. לפיכך, אנו יכולים לחסר את המרחק כדי לקבל את המרחק למסע האחר.

קופונים

קוד 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

קוד Java לפתרון מרחק בין תחנות אוטובוס

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 הוא מספר הערים. מכיוון שהיינו צריכים לנסוע בכל הערים. מורכבות הזמן היא לינארית.

מורכבות בחלל

O (1), מכיוון שהשתמשנו במשתנה יחיד בלבד. מורכבות החלל קבועה.