Dekodlaşdırma yolları

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Cisco Verilənlər bazası Facebook Goldman Sachs google JP Morgan microsoft Morgan Stanley Kahin kvadrat
Dinamik proqramlaşdırma SimBaxılıb 98

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.

Decode Ways problemində bir boş deyil sim yalnız rəqəmlərdən ibarət olan aşağıdakı eşleme istifadə edərək kodun açılma yollarının ümumi sayını müəyyənləşdirin:

'A' -> 1

'B' -> 2

...

'Z' -> 26

misal

S = "123"

Bu simli deşifr etməyin yollarının sayı 3-dür

Dekodlaşdırma yolları

Problemə diqqətlə baxsaq, 0-dan başqa bütün birrəqəmli ədədin etibarlı olduğunu, ancaq iki rəqəmli nömrə olduqda yalnız 10-dan 26-dək rəqəmlərin etibarlı olduğunu müşahidə edə bilərik.

Buna görə əldə etdiyimiz hər indeksdə belə bir nəticəyə gələ bilərik iki addım:

1. Bir sətrin ith elementi '0' deyilsə, onda Xəritəçəkmə istifadə edərək ith indeksindən başlayaraq sazı deşifrə etməyin bir yolu var:

'A' -> 1

'B' -> 2

….

'I' -> 9

2. Aşağıdakı Xəritəçəkmə ilə etibarlı bir rəqəm yaratmaq üçün ith və (i + 1) indekslərini birləşdirə bilsək:

'J' -> 10

'K' -> 11

….

'Z' -> 26

Sonra ith indeksindən başlayaraq simli deşifrə etməyin bir yolu daha var.

Dekodlaşdırma yollarının alqoritmi

Step 1: N ölçüsündə 1D ölçülü sıfır ilə elan edin və başladın.

Step 2: Hər ikisini (n-1) indeksində başlayan və bitən simli deşifrə edə biləcəyimizi yoxlayın (Əsas hal).

Step 3: Bir döngü çalıştırın və hər bir addımda yoxlayın ki, ith indeks elementini bir rəqəmli etibarlı rəqəm kimi istifadə edə bilərik və ya (i + 1) -ci indeks elementi ilə birləşdirib iki rəqəmli etibarlı say yaradırıq.

  1. Əgər s [i]! = '0' olarsa, dp [i] + = dp [i + 1]
  2. S [i] == '1' olarsa, dp [i] + = dp [i + 2]
  3. Əgər s [i] == '2' və s [i + 1] <= '6' olarsa, onda dp [i] + = dp [i + 2]

Step 4: Dp [0] qayıdın.

Həyata keçirilməsi

Dekodlaşdırma yolları üçün C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
    int n=s.length();
    int dp[n+1];
    memset(dp,0,sizeof(dp));
    dp[n]=1;
    if(s[n-1]!='0'){       //if the last chararcter is not zero then we have one way to decode it
        dp[n-1]=1;
    }
    for(int i=n-2;i>=0;i--){
        if(s[i]!='0'){    
            dp[i]+=dp[i+1];
        }
        if(s[i]=='1'){
            dp[i]+=dp[i+2];
        }
        if(s[i]=='2'){
            if(s[i+1]<='6'){
                dp[i]+=dp[i+2];
            }
        }
    }
    return dp[0];
}
int main(){
    string s="452625";
    cout<<"The number of ways to decode the given string is: "<<numDecodings(s);
}
The number of ways to decode the given string is: 4

Dekodlaşdırma yolları üçün JAVA proqramı

public class Main
{
    public static int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n+1];
        dp[n]=1;
        if(s.charAt(n-1)!='0'){       //if the last chararcter is not zero then we have one way to decode it
            dp[n-1]=1;
        }
        for(int i=n-2;i>=0;i--){
            dp[i]=0;
            if(s.charAt(i)!='0'){    
                dp[i]+=dp[i+1];
            }
            if(s.charAt(i)=='1'){
                dp[i]+=dp[i+2];
            }
            if(s.charAt(i)=='2'){
                if(s.charAt(i+1)<='6'){
                    dp[i]+=dp[i+2];
                }
            }
        }
        return dp[0];
    }
  public static void main(String[] args) {
      String s="23572";
    System.out.println("The number of ways to decode the given string is: "+numDecodings(s));
  }
}
The number of ways to decode the given string is: 2

Dekodlaşdırma Yolları üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (n) burada n - verilən sətrin uzunluğu.

Verilən simli yalnız bir dəfə keçirik, bu səbəbdən mürəkkəblik O (n) -dir.

Kosmik mürəkkəblik: O (n) çünki biz hər addımda yol sayını dp massivində saxlayırıq ki, bu da bizi xətti kosmik mürəkkəbliyə aparır.

References

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