Daş Oyunu LeetCode

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.

Stone Game problemi nədir?

Stone Game LeetCode - İki oyunçu A və B daş oyunu oynayır. Hər bir yığının içində bəzi daşlar olan çox sayda yığın var və bütün yığınlardakı ümumi daşlar təkdir. A və B-nin sıranın başlanğıcından və ya ucundan bir-bir qalaq qalmayana qədər bir-bir yığın götürməsi nəzərdə tutulur. Oyunçu A həmişə əvvəlcə bir yığın götürərək oyuna başlayacaq. Sonda daha çox daş olan oyunçu oyunu qazanır. Yalnız A oyunçusu oyunda qalib gəldiyi təqdirdə doğru yazdırın, əks halda səhv yazdırın. Bu sual LeetCode-da çox yaygındır.

Pin

 

Bu səbəbdən çıxış doğru olacaq, çünki A oyuna başladığını düşünərək qalib gəlir. Aşağıda daş oyun leetcoduna bir nümunə verilmişdir.

misal

Giriş: yığınlar = {5, 3, 4, 5}

Çıxış: Doğru

Giriş: yığınlar = {5, 3, 4, 5, 3, 7}

Çıxış: Doğru

Dinamik Proqramlaşdırma Metodu

LeetCode-un Daş Oyunu problemini istifadə edərək həll etmək olar Dinamik proqramlaşdırma

Alqoritm

1. Yığın daşları ehtiva edən bir siyahı başlayın.
2. 2D-DP yaradın array və bütün dəyərləri 0 olaraq təyin edin.
3. Qalan yığınlar yığın [i], qalaq [i + 1],… olduqda hər bir oyunçunun iki seçimi olur. yığınlar [j], buna görə ji ilə n modulo 2 müqayisə edilərək oyunçu şansı tapıla bilər.
4. Oyunçu A daşlarını maksimum dərəcədə artırmaq üçün ya yığınları [i] ya da yığınları [j] seçir.
5. Oyunçu B daşlarını minimuma endirmək üçün ya yığınları [i] ya da yığınları [j] seçir.
6. A-da daha çox daş varsa, doğru qayıdın

Zamanın mürəkkəbliyi: O(n²)

Kosmik Mürəkkəblik: O(n²)

C ++ Proqramı

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

class Stone{
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();

        int dp[n+2][n+2];
        memset(dp, 0, sizeof(dp));

        for(int size = 1; size <= n; ++size)
            for(int i = 0, j = size - 1; j < n; ++i, ++j){
                int parity = (j + i + n) % 2; 
                if(parity == 1)
                    dp[i+1][j+1] = max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]);
                else
                    dp[i+1][j+1] = min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]);
            }
        return dp[1][n] > 0;
    }
};
int main(){
    Stone s;
    vector<int> piles = {5, 3, 4, 5};
    if(s.stoneGame(piles)){
        cout<<"True";
    }
    else{
        cout<<"False";
    }
}

True

Java Proqramı

import java.util.*;

class Stone{
    
    static boolean stoneGame(int[] piles){
        int n = piles.length;

        int[][] dp = new int[n+2][n+2];
        
        for(int size = 1; size <= n; ++size)
            for(int i = 0; i + size <= n; ++i){
                int j = i + size - 1;
                int parity = (j + i + n) % 2;
                if(parity == 1)
                    dp[i+1][j+1] = Math.max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]);
                else
                    dp[i+1][j+1] = Math.min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]);
            }

        return dp[1][n] > 0;
    }
    
  public static void main (String[] args){
      
    int piles[] = {5, 3, 4, 5};
    
    if(stoneGame(piles)){
        System.out.println("True");
    }
    else{
        System.out.println("False");
    }
  }
}

Output :
True

Riyazi və ya müşahidə olunan metod

Stone Game LeetCode haqqında maraqlı faktlar. A oyunçu ilk olaraq daş yığını seçdiyindən yığın sayı bərabər olduğundan bu maraqlı bir həqiqətə səbəb olur:
A oyunçu hər zaman tək yığınlar seçə bilər və ya hər zaman cüt yığınlar seçə bilər.

Deyək :

A oyunçu cüt mövqelərdə yığın yığmaq istəyirsə və indeks 0-da yığın olan ilk yığını götürürsə, oyunçu B ya yığınları [1], ya da yığınları [n-1] seçə bilər.
Hər döngədə, A oyunçu hər zaman cüt mövqedə yığın seçə bilər və B oyunçu yalnız tək mövqedə yığma seçə bilər.

Bildiyimiz kimi yığınlarda olan daşların cəmi təkdir.
Yığınların [cüt] cəmləri [qəpiklərin] cəmindən çoxdursa, A Oyuncu yalnız bütün cütləri seçir və qazanır.
Yığınların cəmi [cüt] yığınların cəmindən [tək] azdırsa, B oyunçu bütün əmsalları seçir və qazanır.

Beləliklə, A oyunçu bu oyunda həmişə qalib gəlir.

Alqoritm

1. Yığın daşları ehtiva edən bir siyahı başlayın.
2. Doğru qayıt.

Zamanın mürəkkəbliyi: O (1)

Kosmik Mürəkkəblik: O (1)

C ++ Proqramı

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

class Stone{
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

int main(){
    Stone s;
    vector<int> piles = {5, 3, 4, 5};
    if(s.stoneGame(piles)){
        cout<<"True";
    }
    else{
        cout<<"False";
    }
}

True

Java Proqramı

import java.util.*;

class Stone{
    
    static boolean stoneGame(int[] piles){
        return true;
    }
    
  public static void main (String[] args){
      
    int piles[] = {5, 3, 4, 5};
    
    if(stoneGame(piles)){
        System.out.println("True");
    }
    else{
        System.out.println("False");
    }
  }
}

True

Bu daş oyun leetcodeun məşhur həllidir. Stone Game LeetCode sualına əsaslanan müxtəlif reportajlarda soruşulur dinamik proqramlaşdırma.

References