Semak sama ada rentetan binari boleh diisih dalam tertib menurun dengan mengalih keluar aksara bukan bersebelahan

Dalam masalah ini, kita perlu mengisih rentetan binari yang diberikan dalam tertib menurun dengan mengalih keluar elemen bukan bersebelahan sahaja.

Untuk menyelesaikan masalah ini, kita perlu mengeluarkan semua 0 yang datang sebelum 1 dalam rentetan binari. Jika kita menemui dua sifar berturut-turut diikuti oleh dua 1 berturut-turut di mana-mana dalam rentetan, ini bermakna kita tidak boleh mengisih rentetan dalam tertib menurun. Jika tidak, kita boleh mengklasifikasikan setiap situasi.

Pernyataan Masalah - Kami diberi rentetan binari str panjang sama dengan N. Kita perlu menyemak sama ada rentetan yang diberikan boleh diisih dalam tertib menurun dengan mengalih keluar berbilang aksara bukan bersebelahan daripada rentetan. rentetan yang diberikan. Jika rentetan boleh diisih dalam susunan menurun, cetak "ya" jika tidak, cetak "tidak".

Contoh

Input –  str = "10101100"

Output – “YES”

Arahan

Kita boleh mengisih rentetan dalam tertib menurun dengan mengalih keluar "0" daripada kedudukan kedua dan keempat.

Input –  str = "11000"

Output – “YES”

Arahan

String disusun.

Input –  str = “010001100”

Output – “NO”

Arahan

Di sini, kita perlu mengalih keluar 0s pada kedudukan 1, 3, 4 dan 5 untuk mengisih rentetan, tetapi kita tidak boleh mengalih keluar 0 yang bersebelahan. Sebagai alternatif, kita boleh mengisih rentetan dengan mengalih keluar semua "1", tetapi ini juga mustahil kerana dua "1" bersebelahan.

Kaedah 1

Dalam kaedah ini kita akan berulang melalui rentetan bermula dari akhir. Jika kita mendapati dua "1" berturut-turut, kita memecahkan gelung. Selepas itu, kami menyemak sama ada rentetan mengandungi dua "0" berturut-turut. Jika ya, kami kembali palsu. Jika tidak, kami kembali benar.

Algoritma

• Langkah 1 - Mulakan lelaran melalui rentetan daripada 'len – 2' kepada 0 menggunakan gelung for. Di sini, 'len' ialah panjang rentetan binari yang diberikan.

• Langkah 2 - Jika kedua-dua str[i] dan str[i+1] adalah sama dengan "1", tamatkan gelung menggunakan kata kunci "break".

• Langkah 3 - Sekarang, mula melintasi rentetan bermula dari indeks ke-i.

• Langkah 4 - Jika kedua-dua str[j] dan str[j+1] adalah sama dengan '0', kembalikan 0. Mengembalikan 1 jika gelung berjaya ditamatkan.

• Langkah 5 - Cetak "YA" atau "TIDAK" dalam kod pemacu berdasarkan nilai pulangan fungsi isSortPossible().

Contoh

#include <bits/stdc++.h>
using namespace std;
// removing the non-adjacent characters from the given string to make it sorted in descending order
bool isSortPossible(string str, int len){
   int i, j;
   
   // Traverse the string str from the end
   for (i = len - 2; i >= 0; i--){
   
      // if str[i] and str[i + 1] is equal to 1 then break the loop.
      if (str[i] == '1' && str[i + 1] == '1'){
         break;
      }
   }
   
   // start traversing the string from i
   for (int j = i; j >= 0; j--){
      // If str[j] and str[j + 1] is equal to 0 then return false
      if (str[j] == '0' && str[j + 1] == '0'){
         return 0;
      }
   }
   return 1;
}
int main(){
   string str = "10101100";
   int len = str.length();
   cout << "The sorting of the given binary string is possible by removing non-adjacent characters - " << endl;
   if (isSortPossible(str, len))
      cout << "YES" << endl;
   else
      cout << "NO" << endl;

   return 0;
}

Output

The sorting of the given binary string is possible by removing non-adjacent characters −
YES

Kerumitan masa - O(N), apabila kita mengulangi rentetan.

Kerumitan ruang - O(1)

Kaedah 2

Dalam kaedah ini kami akan menggunakan logik yang sama seperti kaedah pertama, tetapi kami telah mengoptimumkan kod untuk menjadikannya lebih mudah dibaca. Di sini, daripada menggunakan dua gelung berasingan, kami hanya akan menggunakan gelung tunggal untuk mengesan dua "1" berturut-turut selepas dua "0" berturut-turut.

Algoritma

• Langkah 1 - Tentukan pembolehubah "isTwoZeros" dan mulakan dengan nilai "false".

• Langkah 2 - Mulakan lelaran rentetan daripada indeks ke-0 kepada “len – 1”.

• Langkah 3 - Jika str[i] dan str[I + 1] ialah "0" dan "isTwoZeros" sama dengan palsu, kemudian tukar nilai "isTwoZeros" kepada benar . Ini bermakna kita mendapat dua sifar berturut-turut dalam rentetan yang diberikan.

• Langkah 4 - Di bahagian lain, jika str[i] dan str[I + 1] ialah '1' dan 'isTwoZeros' sama dengan benar, maka dari fungsi. Ini bermakna kita mendapat dua "1" berturut-turut selepas dua sifar berturut-turut.

• Langkah 5 - Kembalikan benar apabila semua lelaran gelung for ditamatkan.

Contoh

#include <bits/stdc++.h>
using namespace std;
// removing the non-adjacent characters from the given string to make it sorted in descending order
bool isSortPossible(string str, int len){
   // to track if there are two adjacent zeros in the string
   bool isTwoZeros = false;
   
   // traverse the string
   for (int i = 0; i < len - 1; i++){
   
      // if two zeros are adjacent, then change the value of isTwoZeros to true
      if (str[i] == '0' && str[i + 1] == '0' && !isTwoZeros){
         isTwoZeros = true;
      }
      else{
      
         // if we find two adjacent ones after finding two adjacent zeros, then return false
         if (str[i] == '1' && str[i + 1] == '1' && isTwoZeros){
            return false;
         }
      }
   }
   
   // return true if we don't find two adjacent ones after finding two adjacent zeros
   return true;
}
int main(){
   string str = "101001100";
   int len = str.length();
   cout << "The sorting of the given binary string is possible by removing non-adjacent characters - " << endl;
   if (isSortPossible(str, len))
      cout << "YES" << endl;
   else
      cout << "NO" << endl;

   return 0;
}

Output

The sorting of the given binary string is possible by removing non-adjacent characters - 
NO

Kerumitan masa - O(N)

Kerumitan ruang - O(1)

Kesimpulan

Kami mempelajari dua cara untuk mengisih rentetan binari dalam tertib menurun dengan mengalih keluar aksara bukan bersebelahan sahaja. Kedua-dua kaedah menggunakan logik yang sama dengan perubahan minimum pada kod. Kod untuk pendekatan kedua lebih mudah dibaca daripada kod untuk pendekatan pertama.

Atas ialah kandungan terperinci Semak sama ada rentetan binari boleh diisih dalam tertib menurun dengan mengalih keluar aksara bukan bersebelahan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!