Menyemak sama ada penghujung rentetan binari yang diberikan boleh dicapai dengan memilih nilai lompatan dalam julat yang diberikan

Rentetan binari ialah rentetan yang mengandungi hanya dua jenis aksara yang berbeza, 0 dan 1. Diberi rentetan binari dan dua integer L dan R. Kita boleh membuat lompatan saiz antara 'L' dan 'R', termasuk, daripada indeks di mana nilai rentetan ialah '0'. Kita perlu bermula pada indeks sifar dan mengetahui sama ada kita boleh mencapai indeks terakhir.

Contoh Contoh

Input1:
string str = “01001110010”
int L = 2, R = 4
Output: Yes, we can reach the last index.

Penjelasan

diterjemahkan sebagai:

Penjelasan

Kita boleh melompat tiga kali daripada indeks sifar dan kemudian dua lagi lompat ke 4 supaya kita sampai ke indeks terakhir yang diingini.

Input2:
string str = “01001110010”
int L = 2, R = 3
Output: No, we cannot reach the last index. 

Penjelasan

diterjemahkan sebagai:

Penjelasan

Kita boleh membuat dua lompatan, setiap lompatan adalah 2 atau 3, jika lompat dari indeks ke-0, sama ada kita mencapai indeks ke-2 atau indeks ke-3, kemudian kita hanya boleh melompat ke indeks nilai '1', tiada lompatan lagi boleh dibuat.

Kaedah 1

Terjemahan bahasa Cina bagi

Idea

ialah:

Idea

Ideanya adalah untuk mengaplikasikan konsep pengaturcaraan dinamik. Kami boleh mengekalkan tatasusunan yang menunjukkan sama ada lokasi boleh dicapai.

Jika kita boleh mencapai satu kedudukan, maka kedudukan l hingga r seterusnya juga boleh dicapai.

Pelaksanaan

Kami akan mencipta fungsi yang akan mengambil rentetan, kedudukan kiri dan kedudukan kanan sebagai parameter dan mengembalikan nilai boolean.

Dalam fungsi ini, kami akan melelakan melalui tatasusunan dan menggunakan gelung bersarang untuk untuk lelaran melalui julat, semak sama ada kedudukan semasa tolak kedudukan julat semasa boleh dicapai, dan jika ia boleh dicapai, maka kedudukan boleh dicapai.

Akhirnya, kami akan mengembalikan status indeks terakhir tatasusunan DP, yang mewakili jawapan akhir.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to implement the DP concepts 
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results 
   
   // Initiating the first index 
   dp[0] = str[0] == '0'; 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      for(int j = l; j <= r ; j++){
         if(i-j < 0){
            break;
         }
         if(str[i-j] == '1' || dp[i-j] == 0){
            continue;
         }
         else{
            dp[i] = 1;
            break;
         }
      }
   }
   return dp[len-1];
}
int main(){
   string str = "01001110010";
   int l = 2, r = 4; 
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
   else{
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

Output

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

Kerumitan masa dan kerumitan ruang

Kerumitan masa kod di atas ialah O(N^2), dengan N ialah saiz rentetan yang diberikan. Kami menggunakan gelung bersarang, yang menghasilkan kerumitan masa N^2.

Kerumitan ruang kod di atas ialah O(N) kerana kami menggunakan tatasusunan panjang N untuk menyimpan keadaan DP.

Kaedah 2

Kaedah ini adalah versi yang lebih baik daripada yang sebelumnya, dalam kaedah ini kita akan mengekalkan integer untuk mendapatkan bilangan lompatan yang boleh kita lakukan. Pada setiap lompatan, kita boleh menambah kiraan jika lompatan boleh dilakukan, dan mengurangkan kiraan jika lompatan tidak boleh dilakukan di mana-mana lokasi.

Kami akan menyimpan data dalam setiap indeks tatasusunan DP dan menggunakannya kemudian.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <bits/stdc++.h>
using namespace std;
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results     
   // initiating the first index 
   dp[0] = str[0] == '0';    
   int count = 0; // variable to maintain the count of the jump 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      if (i >= l) {
         count += dp[i - l];
      }
      if (i > r) {
         count -= dp[i -r- 1];
      }
      dp[i] = (count > 0) and (str[i] == '0');
   }
   return dp[len-1];
}

// main function 
int main(){
   string str = "01001110010";
   int l = 2, r = 4;  
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   } else {
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

Output

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

Kerumitan masa dan kerumitan ruang

Kerumitan masa kod di atas ialah O(N), dengan N ialah saiz rentetan yang diberikan. Kami menggunakan gelung tunggal untuk mengulangi rentetan supaya kerumitan masa adalah linear.

Kerumitan ruang kod di atas ialah O(N) kerana kami menggunakan tatasusunan panjang N untuk menyimpan keadaan DP.

Kesimpulan

Dalam tutorial ini, kami melaksanakan kod yang menentukan sama ada kami boleh mencapai rentetan tertentu dengan bermula dari indeks pertama dan mengalihkan bilangan indeks tertentu daripada indeks yang mengandungi '0' dalam rentetan yang diberikan di penghujung. Kami menggunakan kaedah pengaturcaraan dinamik, kerumitan masa ialah O(N^2) dan O(N), dan kerumitan ruang ialah O(N).

Atas ialah kandungan terperinci Menyemak sama ada penghujung rentetan binari yang diberikan boleh dicapai dengan memilih nilai lompatan dalam julat yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!