Kira bilangan cara untuk membelah rentetan kepada subrentetan K bermula dengan nombor genap dan mempunyai panjang minimum M

Dalam masalah ini, kita akan mengira cara untuk membahagikan rentetan yang diberikan kepada substring K supaya ia memenuhi syarat yang diberikan dalam pernyataan masalah.

Kami akan menggunakan rekursi untuk menyelesaikan masalah ini. Selain itu, kami akan menggunakan kaedah pengaturcaraan dinamik jadual untuk menyelesaikan masalah ini dengan cekap.

Pernyataan Masalah − Kami mempunyai rentetan panjang tertentu yang dipanggil bin_Str. Rentetan mengandungi hanya aksara angka dari '0' hingga '9'. Kita perlu mengira bilangan cara untuk membahagikan rentetan kepada subrentetan K supaya ia memenuhi syarat berikut.

• Subrentetan hendaklah mengandungi sekurang-kurangnya 2 aksara.

• Watak pertama setiap subrentetan hendaklah genap dan aksara terakhir hendaklah ganjil.

Contoh Contoh

Masuk

M = 2, K = 2; bin_str = "255687"

Output

1

Penjelasan − Berdasarkan syarat penyataan masalah, kita boleh membahagikan 255 | 687 kepada bahagian rentetan yang diberikan.

Masuk

M = 2, K = 2; bin_str = "26862";

Output

0

Penjelasan − Memandangkan rentetan mengandungi nombor genap sahaja, kita tidak boleh membahagikannya kepada dua subrentetan supaya setiap subrentetan berakhir dengan nombor ganjil.

Masuk

M = 2, K = 3; bin_str = "856549867";

Output

3

Penjelasan − Kaedah pembahagian yang mungkin ialah 85|65|49867, 8565|49|867 dan 85|6549|867.

Kaedah 1

Kami akan menggunakan fungsi rekursif untuk menyelesaikan masalah ini. Jika kami menemui subrentetan yang sah pada indeks semasa, kami membuat panggilan rekursif mengira bilangan cara untuk memisahkan subrentetan yang tinggal kepada subrentetan K - 1.

Algoritma

Langkah 1 − Dapatkan aksara pertama dan terakhir rentetan yang diberikan.

Langkah 2 − Jika aksara pertama tidak genap dan aksara terakhir tidak ganjil, kembalikan 0.

Langkah 3 − Jika indeks permulaan sama dengan panjang rentetan, kembalikan 0 kerana kita telah sampai ke penghujung rentetan yang diberikan.

Langkah 4− Jika K == 1, ambil perbezaan antara panjang rentetan dan indeks permulaan. Jika ia sama dengan atau lebih besar daripada M, maka 1 dikembalikan. Jika tidak, mengembalikan 0. Di sini, jika K ialah 1, kita perlu mendapatkan subrentetan yang tinggal.

Langkah 5 - Mulakan 'ops' kepada '0' untuk menyimpan kiraan belahan, dan 'len' kepada '0' untuk menyimpan panjang subrentetan semasa.

Langkah 6 − Lintas rentetan bermula dari indeks "mula" sehingga penghujung rentetan.

Langkah 7− Tingkatkan ‘len’ sebanyak 1. Pada masa yang sama, dapatkan watak semasa dan watak seterusnya.

Langkah 8− Jika 'len' lebih besar daripada M, dan nombor semasa adalah ganjil dan nombor seterusnya adalah genap, kita boleh menamatkan partition pada indeks semasa. Jadi, buat panggilan rekursif ke fungsi countWays() dengan menghantar indeks seterusnya dan K - 1 sebagai parameter fungsi.

Langkah 9− Akhir sekali, kembalikan nilai ‘ops’.

Contoh

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

int countWays(int start, int str_len, int K, int M, string bin_str) {
    // Geeting first and last character of the substring
    int f_char = bin_str[0] - '0';
    int l_char = bin_str[str_len - 1] - '0';
    if (f_char % 2 != 0 || l_char % 2 != 1) {
        return 0;
    }
    // When we reach at the end
    if (start == str_len)
        return 0;
    // Base case
    if (K == 1) {
        int chars = str_len - start;
        // Validate minimum length of substring
        if (chars >= M)
            return 1;
        return 0;
    }    
    int ops = 0;
    int len = 0;
    // Traverse all partions
    for (int p = start; p < str_len - 1; p++) {
        len++;
        int first = bin_str[p] - '0';
        int second = bin_str[p + 1] - '0';
        // If we can end the partition at p and start a new partition at p+1
        if (len >= M && first % 2 == 1) {
            if (second % 2 == 0) {
                ops += countWays(p + 1, str_len, K - 1, M, bin_str);
            }
        }
    }
    return ops;
}
int main() {
    int M = 2, K = 2;
    string bin_str = "255687";
    int str_len = bin_str.length();
    cout << "The number of ways to split the string is " << countWays(0, str_len, K, M, bin_str) << endl;
    return 0;
}

Output

The number of ways to split the string is 1

Bilangan cara untuk membelah rentetan ialah 1

Kerumitan ruang - O(1) kerana kami tidak menggunakan ruang tambahan.

Kaedah 2

Dalam kaedah ini, kami akan menggunakan teknik pengaturcaraan dinamik jadual untuk mengira bilangan cara untuk membelah rentetan kepada bahagian K. Kami akan menggunakan matriks untuk menyimpan output keadaan sebelumnya.

Algoritma

Langkah 1 - Tentukan tatasusunan matriks matriks global[] bersaiz 1001 x 1001. Baris peta matriks kepada aksara rentetan, dan lajur peta matriks kepada K.

Langkah 2 − Dapatkan aksara pertama dan terakhir rentetan. Jika aksara pertama genap dan aksara terakhir ganjil, fungsi countWays() dilaksanakan. Jika tidak, cetak 0 dalam output.

Langkah 3 − Dalam fungsi countWays, mulakan tatasusunan matriks[].

Langkah 4 − Bilangan baris matriks yang dilalui adalah sama dengan panjang rentetan, dan bilangan lajur adalah sama dengan K. Jika bilangan baris sama dengan panjang rentetan, kemas kini keseluruhan baris kepada 0.

Langkah 5 − Jika tidak, jika q ialah 1 dan panjang rentetan tolak indeks semasa lebih besar daripada M, mulakan matriks tatasusunan[p][q] dengan 1. Jika tidak, mulakan matriks[p][q] dengan 0.

Langkah 6 − Dalam kes lain, mulakan matriks [p][q] kepada -1.

Langkah 7− Isikan matriks menggunakan dua gelung bersarang. Gunakan gelung luar untuk melintasi dari 2 ke K, dan gunakan gelung bersarang untuk melintasi dari 0 ke panjang rentetan.

Langkah 8 - Mulakan 'ops' dan 'len' kepada 0. Selain itu, lelaran pada rentetan bermula pada indeks p-th dan tambah 'len' sebanyak 1 pada setiap lelaran.

Langkah 9 − Keluarkan watak semasa dan watak seterusnya rentetan.

Langkah 10− Jika panjang lebih besar daripada M, aksara semasa adalah ganjil, dan aksara seterusnya adalah genap, tambahkan matriks[k + 1][q − 1] pada 'ops'.

Langkah 11− Gunakan 'ops' untuk mengemas kini matriks [p][q].

Langkah 12− Akhirnya kembalikan matriks[0][k].

Example

的中文翻译为：

示例

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

int matrix[1001][1001];
int countWays(int str_len, int K, int M, string bin_str) {
    // Base case
    for (int p = 0; p <= str_len; p++) {
        for (int q = 0; q <= K; q++) {
            // When index points to end index of string
            if (p == str_len)
                matrix[p][q] = 0;
            else if (q == 1) {
                // When only 1 split needs to be done
                int chars = str_len - p;
                // Validating substring's minimum len
                if (chars >= M)
                    matrix[p][q] = 1;
                else
                    matrix[p][q] = 0;
            } else {
                // For other cases
                matrix[p][q] = -1;
            }
        }
    }
    // Dynamic programming approach
    for (int q = 2; q <= K; q++) {
        for (int p = 0; p < str_len; p++) {
            int ops = 0;
            int len = 0; // length of current substring
            for (int k = p; k < str_len - 1; k++) {
                len++;
                int first = bin_str[k] - '0';
                int second = bin_str[k + 1] - '0';
                // Validate condition for split
                if (len >= M && first % 2 == 1 && second % 2 == 0) {
                    // Substring starting from k + 1 index needs to be splited in q-1 parts
                    ops += matrix[k + 1][q - 1];
                }
            }
            matrix[p][q] = ops;
        }
    }
    return matrix[0][K];
}
int main() {
    int M = 2, K = 2;
    string bin_str = "255687";
    int str_len = bin_str.length();
    int f_char = bin_str[0] - '0';
    int l_char = bin_str[str_len - 1] - '0';
    cout << "The number of ways to split the string is ";
    if (f_char % 2 != 0 || l_char % 2 != 1) {
        cout << 0 << endl;
    } else {
        cout << countWays(str_len, K, M, bin_str) << endl;
    }
    return 0;
}

输出

The number of ways to split the string is 1

时间复杂度 - O(N*N*K)，其中 O(N*N) 用于找到所有子字符串，O(K) 用于 K 个分区。

空间复杂度 - 使用matrix[]数组为O(N*K)。

Atas ialah kandungan terperinci Kira bilangan cara untuk membelah rentetan kepada subrentetan K bermula dengan nombor genap dan mempunyai panjang minimum M. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!