Jadual Kandungan
Kaedah 1
Algoritma
Contoh
Output
Rumah pembangunan bahagian belakang C++ Susunan terpanjang yang aksaranya sama dengan subrentetan dan perbezaan frekuensinya paling banyak K

Susunan terpanjang yang aksaranya sama dengan subrentetan dan perbezaan frekuensinya paling banyak K

Sep 09, 2023 am 09:09 AM
watak kekerapan pesanan anak

Susunan terpanjang yang aksaranya sama dengan subrentetan dan perbezaan frekuensinya paling banyak K

Dalam masalah ini, kita akan mendapati panjang maksimum bagi urutan yang mengandungi aksara berturut-turut dan perbezaan kekerapan semua aksara tidak melebihi K.

Kita perlu mencari semua kemungkinan urutan rentetan yang diberikan dan menyemak sama ada ia mengandungi setiap aksara secara berturutan dan dengan perbezaan frekuensi maksimum untuk mendapatkan output.

Pernyataan Masalah- Kami diberi rentetan alfa yang mengandungi aksara abjad huruf kecil. Selain itu, kami telah diberi integer positif K. Kita perlu mencari panjang maksimum bagi urutan rentetan tertentu supaya ia mengikut peraturan berikut.

  • Semua kejadian watak tertentu hendaklah berturut-turut.

  • Perbezaan kekerapan aksara tidak boleh lebih besar daripada K.

Contoh

Masuk

alpha = "ppppqrs", K = 2
Salin selepas log masuk

Output

6
Salin selepas log masuk

Penjelasan - Kita boleh ambil "pppqrs" seterusnya. Kekerapan aksara maksimum ialah 3 dan kekerapan aksara minimum ialah 1. Oleh itu, perbezaannya ialah 2. Dan ia mengandungi semua aksara berturut-turut.

Masuk

alpha = "abbbbc", K = 2
Salin selepas log masuk

Output

5
Salin selepas log masuk

Penjelasan - Kita boleh ambil urutan "abbbc".

Masuk

alpha = "mnnnnnnno", k = 3;
Salin selepas log masuk

Output

7
Salin selepas log masuk

Penjelasan - Kita boleh ambil "nnnnnnn" seterusnya.

Kaedah 1

Dalam kaedah ini, kita akan menggunakan fungsi rekursif untuk mencari semua urutan panjang tertentu. Selain itu, kami akan mentakrifkan fungsi untuk menyemak sama ada urutan mengandungi semua aksara secara berturut-turut. Kami akan menggunakan struktur data peta untuk mengira perbezaan frekuensi maksimum dan minimum.

Algoritma

Langkah 1 - Tentukan peta "f" untuk menyimpan kekerapan aksara.

Langkah 2 - Jika permulaan adalah sama dengan panjang rentetan sementara, dan panjang rentetan lebih besar daripada 0, ikut langkah ini.

Langkah 3 - Mulakan pembolehubah "minf" dan "maxf" untuk menyimpan frekuensi minimum dan maksimum.

Langkah 4- Kosongkan peta dan simpan kekerapan setiap aksara dalam peta.

Langkah 5 - Gelung nilai peta dan cari nilai kekerapan maksimum dan minimum.

Langkah 6 - Jika perbezaan frekuensi maksimum dan minimum adalah kurang daripada atau sama dengan K, semak sama ada rentetan mengandungi aksara berturut-turut.

Langkah 6.1 - Dalam fungsi checkForContinously(), tentukan peta "pos" untuk menyimpan kedudukan terakhir aksara tertentu.

Langkah 6.2 - Gelung melalui rentetan. Jika aksara semasa wujud dalam peta dan perbezaan antara kedudukan semasa watak dan kedudukan terakhir adalah kurang daripada 1, kemas kini kedudukan terakhir. Jika tidak, pulangan palsu.

Langkah 6.3 - Tambahkan aksara pada peta jika ia tidak wujud.

Langkah 6.4 - Akhirnya kembali benar.

Langkah 7 - Jika rentetan mengandungi aksara berturutan dan perbezaan frekuensi kurang daripada K, kemas kini nilai 'maxi' jika nilai 'maxi' kurang daripada panjang jujukan semasa.

Langkah 8 - Buat panggilan rekursif selepas mengecualikan aksara semasa.

Langkah 9 - Tambahkan aksara semasa pada penghujung rentetan sementara. Juga, buat panggilan rekursif dengan rentetan "tmp" yang dikemas kini.

Contoh

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

int maxi = 0;
// Check for continuous characters in the substring
bool CheckForContinuous(string &tmp) {
    // map to store the last index of the character
    unordered_map<char, int> pos;
    for (int p = 0; p < tmp.length(); p++) {
        // When the last index exists in the map
        if (pos[tmp[p]]) {
            // If the last index is adjacent to the current index
            if (p - pos[tmp[p]] + 1 <= 1)
                pos[tmp[p]] = p + 1;
            else
                return false;
        } else {
            // When the map doesn't have a character as a key
            pos[tmp[p]] = p + 1;
        }
    }
    return true;
}
void getLongestSubSeq(string &alpha, string tmp, int start, int &k) {
    // To store the character's frequency
    unordered_map<char, int> f;
    if (start == alpha.length()) {
        if (tmp.length() > 0) {
            // To store minimum and maximum frequency of characters
            int minf = INT_MAX, maxf = INT_MIN;
            // Make map empty
            f.clear();
            // Store frequency of characters in the map
            for (int p = 0; p < tmp.length(); p++)
                f[tmp[p]]++;

            // Get minimum and maximum value from the map
            for (auto &key : f) {
                minf = min(minf, key.second);
                maxf = max(maxf, key.second);
            }
            // Validate substring for frequency difference and continuous characters
            if (maxf - minf <= k && CheckForContinuous(tmp))
                maxi = max(maxi, (int)tmp.length());
        }
        return;
    }
    // Exclude current character
    getLongestSubSeq(alpha, tmp, start + 1, k);
    // Include current character
    tmp.push_back(alpha[start]);
    getLongestSubSeq(alpha, tmp, start + 1, k);
}
int main() {
    string alpha = "ppppqrs", tmp;
    int k = 2;
    getLongestSubSeq(alpha, tmp, 0, k);
    cout <<"The maximum length of the substring according to the given conditions is " << maxi;
    return 0;
}
Salin selepas log masuk

Output

The maximum length of the substring according to the given conditions is 6
Salin selepas log masuk

Kerumitan masa - O(N*2N), di mana O(N) untuk menyemak aksara berturut-turut dan O(2N) untuk mencari semua urutan.

Kerumitan ruang - O(N) untuk menyimpan urutan sementara.

Kami menggunakan kaedah mudah untuk mencari semua urutan rentetan yang diberikan. Walau bagaimanapun, ini sangat memakan masa. Ia tidak disyorkan untuk menggunakan kaedah ini untuk menyelesaikan masalah dengan rentetan besar.

Atas ialah kandungan terperinci Susunan terpanjang yang aksaranya sama dengan subrentetan dan perbezaan frekuensinya paling banyak K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Tag artikel panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Yang manakah mempunyai kesan yang lebih besar pada prestasi, kekerapan memori atau pemasaan? Yang manakah mempunyai kesan yang lebih besar pada prestasi, kekerapan memori atau pemasaan? Feb 19, 2024 am 08:58 AM

Yang manakah mempunyai kesan yang lebih besar pada prestasi, kekerapan memori atau pemasaan?

Cara menaip anak panah dalam Word Cara menaip anak panah dalam Word Apr 16, 2023 pm 11:37 PM

Cara menaip anak panah dalam Word

Cara menggunakan pilihan pemformatan superskrip dan subskrip dalam Microsoft Excel Cara menggunakan pilihan pemformatan superskrip dan subskrip dalam Microsoft Excel Apr 14, 2023 pm 12:07 PM

Cara menggunakan pilihan pemformatan superskrip dan subskrip dalam Microsoft Excel

Bagaimanakah anda memasukkan aksara lanjutan, seperti simbol darjah, pada iPhone dan Mac? Bagaimanakah anda memasukkan aksara lanjutan, seperti simbol darjah, pada iPhone dan Mac? Apr 22, 2023 pm 02:01 PM

Bagaimanakah anda memasukkan aksara lanjutan, seperti simbol darjah, pada iPhone dan Mac?

Gunakan fungsi Character.isDigit() java untuk menentukan sama ada aksara ialah nombor Gunakan fungsi Character.isDigit() java untuk menentukan sama ada aksara ialah nombor Jul 27, 2023 am 09:32 AM

Gunakan fungsi Character.isDigit() java untuk menentukan sama ada aksara ialah nombor

ASUS TUF Z790 Plus serasi dengan frekuensi memori ASUS MCP79 ASUS TUF Z790 Plus serasi dengan frekuensi memori ASUS MCP79 Jan 03, 2024 pm 04:18 PM

ASUS TUF Z790 Plus serasi dengan frekuensi memori ASUS MCP79

Cara yang betul untuk memaparkan aksara Cina dalam matplotlib Cara yang betul untuk memaparkan aksara Cina dalam matplotlib Jan 13, 2024 am 11:03 AM

Cara yang betul untuk memaparkan aksara Cina dalam matplotlib

Bagaimana untuk menyemak kekerapan ddr4 Bagaimana untuk menyemak kekerapan ddr4 Feb 01, 2024 am 09:42 AM

Bagaimana untuk menyemak kekerapan ddr4

See all articles