Terjemah yang berikut ke dalam bahasa Cina: Minimumkan penyingkiran 0 subrentetan untuk mengalih keluar semua kejadian 0 daripada rentetan binari bergelung

Dalam masalah ini, kita perlu mengeluarkan semua sifar daripada rentetan binari yang diberikan. Pada masa yang sama, kita perlu mengalih keluar pasangan sifar berturut-turut sekaligus dan mengira jumlah bilangan pasangan sifar yang dialih keluar.

Kita boleh menyelesaikan masalah dengan mengira bilangan pasangan sifar berturut-turut dalam rentetan yang diberikan Dalam tutorial ini, kita akan mempelajari dua penyelesaian yang berbeza untuk menyelesaikan masalah.

Pernyataan Masalah − Kami diberi rentetan binari bulat panjang N. Kita perlu mencari bilangan minimum sifar berturut-turut yang diperlukan untuk mengalih keluar semua sifar daripada rentetan.

Contoh Contoh

Input –  str = "0011001"

Output – 2

Penjelasan

Kita boleh memadam str[0] dan str[1] bersama-sama. Selepas itu, kita boleh memadam str[4] dan str[5]. Jadi, kita perlu mengeluarkan 2 pasang sifar berturut-turut.

Input –  str = ‘0000000’

Output – 1

Penjelasan

Kita boleh mengalih keluar semua sifar sekaligus.

Input –  str = ‘00110010’

Output – 2

Penjelasan

Kami mengalih keluar can str[0], str[1] dan str[7] bersama-sama kerana rentetan binari adalah bulat Seterusnya, kami boleh mengalih keluar str[5] dan str[6] bersama-sama.

Pendekatan 1

Dalam kaedah ini kita akan mencari jumlah pasangan sifar berturut-turut dalam rentetan yang diberikan, yang akan menjawab soalan yang diberikan.

Algoritma

• Langkah 1 - Mulakan pembolehubah 'cnt' kepada sifar.

• Langkah 2 - Mulakan pembolehubah 'isOne' kepada nilai palsu untuk menjejaki nombor 1 dalam rentetan yang diberikan.

• Langkah 3 - Ulangi rentetan menggunakan gelung. Dalam gelung, jika aksara semasa ialah '0', tingkatkan nilai 'cnt' sebanyak 1.

• Langkah 4 − Gunakan gelung sementara untuk mengulang sehingga kita terus mencari aksara seterusnya iaitu '0' dan meningkatkan nilai 'I' sebanyak 1.

• Langkah 5 - Jika aksara semasa ialah '1', tukar nilai pembolehubah 'isOne' kepada benar, menunjukkan bahawa rentetan mengandungi sekurang-kurangnya satu '1'.

• Langkah 6 − Setelah lelaran gelung selesai, Jika nilai 'isOne' adalah palsu, ini bermakna rentetan hanya mengandungi sifar 1 dalam kes sedemikian.

• Langkah 7 − Jika aksara pertama dan terakhir ialah '0', kurangkan nilai 'cnt' sebanyak 1 kerana rentetan adalah bulat.

• Langkah 8 − Kembalikan nilai 'cnt'.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   bool isOne = false;
   
   // Iterate over the string
   for (int i = 0; i < N; i++){
   
      // If the current character is 0, increment the count of 0s
      if (str[i] == '0'){
         cnt++;
         
         // traverse the string until a 1 is found
         while (str[i] == '0'){
            i++;
         }
      }
      else{
      
         // If the current character is 1, then set isOne as true
         isOne = true;
      }
   }
   
   // If string contains only 0s, then return 1.
   if (!isOne)
      return 1;
      
   // If the first and last character is 0, then decrement the count, as the string is circular.
   if (str[0] == '0' && str[N - 1] == '0'){
      cnt--;
   }
   
   // return cnt
   return cnt;
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

Output

The total number of minimum substrings of consecutive zeros required to remove is - 2<font face="sans-serif"><span style="font-size: 16px; background-color: rgb(255, 255, 255);">.</span></font></p><p>

Kerumitan ruang - O(1)

Kaedah 2

Dalam kaedah ini, kami akan mengira bilangan minimum subrentetan pengalih keluar sifar yang diperlukan untuk mengalih keluar semua sifar dengan mengira perbezaan elemen bersebelahan.

Algoritma

• Langkah 1 − Tentukan pembolehubah 'cnt' dan 'isOne', dan mulakan dengan 0 dan false, masing-masing.

• Langkah 2 − Gunakan untuk gelung untuk membuat lelaran N-1, dengan N ialah panjang rentetan.

• Langkah 3 − Dalam gelung, semak sama ada aksara semasa ialah '0,' dan aksara seterusnya ialah '1', naikkan nilai 'cnt' sebanyak 1. Jika tidak, tukar nilai 'isOne' berubah menjadi benar.

• Langkah 4 - Jika aksara terakhir ialah '0', dan aksara pertama ialah '1', maka naikkan nilai 'cnt' sebanyak 1.

• Langkah 5 - Jika nilai 'isOne' adalah palsu, kembalikan 1.

• Langkah 6 - Kembalikan nilai pembolehubah 'cnt'.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   
   // to check if there is at least one 1
   bool isOne = false;
   
   // traverse the string
   for (int i = 0; i < N - 1; i++) {
   
      // if the current character is 0, the next is 1, then increment count by 1
      if (str[i] == '0' && str[i + 1] == '1'){
         cnt++;
      }
      else{
      
         // if the current character is 1, then set isOne to true
         isOne = true;
      }
   }
   
   // for circular string, if the last character is 0 and the first is 1, then increment count by 1
   if (str[N - 1] == '0' && str[0] == '1'){
      cnt++;
   }
   
   // if there is no 1 in the string, then return 1
   if (!isOne){
      return 1;
   }
   return cnt; // return cnt
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

Output

The total number of minimum substrings of consecutive zeros required to remove is - 2

Kesimpulan

Kami telah melihat dua penyelesaian berbeza untuk menyelesaikan masalah yang diberikan. Dalam kaedah pertama kita mengira jumlah bilangan pasangan sifar berturut-turut, dalam kaedah kedua kita mengira jumlah bilangan aksara bersebelahan yang tidak sepadan.

Atas ialah kandungan terperinci Terjemah yang berikut ke dalam bahasa Cina: Minimumkan penyingkiran 0 subrentetan untuk mengalih keluar semua kejadian 0 daripada rentetan binari bergelung. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!