Ən qısa söz məsafəsi Leetcode həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Goldman Sachs google LinkedIn microsoft Salesforce Über
Geyim SimBaxılıb 76

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Ən qısa söz məsafəsi LeetCode Həlli - deyir ki, sizə bir sıra simlər və iki fərqli söz verilir. Giriş sətirində görünən bu iki söz arasındakı ən qısa məsafəni qaytarmalıyıq.Ən qısa söz məsafəsi Leetcode həlliPin

Misal:

Input:  wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Explanation:

  • "Kodlaşdırma" sözü 4-cü mövqedə olur.
  • "Təcrübə" sözü 1-ci mövqedə olur.
  • Ən qısa məsafə 3-dür.
Input:  wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Explanation:

  • "Kodlaşdırma" sözü 4-cü mövqedə olur.
  • 2-ci və 5-ci mövqelərdə “yaradır” sözü olur.
  • Ən qısa məsafə 5-4 = 1-dir.

Yanaşma

Bu, birbaşa kodlaşdırma problemidir. İstənilən iki mövqe arasındakı məsafə i_1 və i_2 massivdədir |i_1 – i_2|. Aralarındakı ən qısa məsafəni tapmaq üçün word1 və word2, biz giriş massivini keçməli və bütün hadisələri tapmalıyıq i_1 və i_2 iki sözdən və olub olmadığını yoxlayın |i_1 – i_2| indiyə qədər hesablanmış minimum məsafədən azdır.

Idea:

  1. Hər söz üçün iki mövqe dəyişənini qoruyun.
  2. Sətir massivində təkrarlayın və müvafiq olaraq iki mövqe dəyişənini yeniləyin.
  3. Cavabımız budur minimum mütləq bu mövqe dəyişənləri arasındakı fərq.

Kodu

C++ Həlli:

class Solution {
public:
    int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
        int ans = INT_MAX,pos1 = -1,pos2 = -1;
        for(int i=0;i<wordsDict.size();i++){
            if(wordsDict[i]==word1){
                pos1 = i;
            }
            if(wordsDict[i]==word2){
                pos2 = i;
            }
            if(pos1!=-1 and pos2!=-1){
                ans = min(ans,abs(pos1-pos2));
            }
        }
        return ans;
    }
};

Java Həlli:

class Solution {
    public int shortestDistance(String[] wordsDict, String word1, String word2) {
        int ans = Integer.MAX_VALUE,pos1 = -1,pos2 = -1;
        for(int i=0;i<wordsDict.length;i++){
            if(wordsDict[i].equals(word1)){
                pos1 = i;
            }
            if(wordsDict[i].equals(word2)){
                pos2 = i;
            }
            if(pos1!=-1 && pos2!=-1){
                ans = Math.min(ans,Math.abs(pos1-pos2));
            }
        }
        return ans;
    }
}

Ən Qısa Söz Məsafəsi Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) çünki biz bütövlükdə təkrar edirik giriş sətri tam bir dəfə.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz yalnız daimi boşluqdan istifadə edirik.

Referans: https://en.wikipedia.org/wiki/One-pass_algorithm

Crack Sistemi Dizayn Müsahibələri
Translate »