[Algoritma] . Permata dan Batu

Penerangan Masalah

Berikan dua rentetan:

mewakili jenis permata,

mewakili batu yang anda miliki. jewels Setiap watak mewakili beberapa jenis batu yang anda miliki. Anda perlu mengira berapa banyak permata di dalam batu yang anda miliki. stones stones huruf huruf, jadi "a" dan "a" mewakili pelbagai jenis batu.

Kunci masalah

Cari watak dalam rentetan dalam rentetan

, dan kembalikan jumlah aksara ini.

jewels Contoh 1 stones

Contoh 2

<code>输入：jewels = "aA", stones = "aAAbbbb"
输出：3</code>

Keadaan Kekangan

<code>输入：jewels = "z", stones = "ZZ"
输出：0</code>

1 ≤ ,

≤ 50 dan

hanya termasuk huruf bahasa Inggeris.

• Semua watak adalah unik. jewels.length stones.length
Pelan 1: Gunakan kaedah termasuk ()
• jewels stones
Langkah:
• jewels Inisialisasi kaunter
digunakan untuk menyimpan jumlah permata.

traversed rentetan, dan gunakan kaedah untuk memeriksa sama ada setiap aksara berada dalam rentetan .

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewels.includes(stones[i])) {
            count++;
        }
    }
    return count;
};

Jika ia mengandungi, ia akan meningkat

.

kembali terakhir <最后>.
1. count
kerumitan masa kaedah ini adalah O (m*n), di mana m ialah panjang rentetan
2. , dan n ialah panjang rentetan stones. Kerana <对> kaedah melintasi setiap aksara pada rentetan includes(). Apabila skala input meningkat, kaedah ini tidak cekap. Kita perlu mengoptimumkan rancangan untuk mengurangkan kerumitan masa. jewels
<案> Rancangan 2: Gunakan kaedah set () (Jadual Hash)
3. count
4. Langkah: <<> count
Inisialisasi kaunter

digunakan untuk menyimpan jumlah permata.

stones Gunakan <符> rentetan untuk membuat jewels. includes() Gunakan jadual hash untuk mencari carian yang lebih cepat. jewels

traversed <字> String, dan gunakan kaedah

untuk memeriksa sama ada setiap watak berada dalam .

Jika ia wujud, ia akan meningkat

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    const jewelsSet = new Set(jewels);
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewelsSet.has(stones[i])) {
            count++;
        }
    }
    return count;
};

.

kembali terakhir .

1. count Mengapa ditetapkan lebih cepat daripada termasuk ()?
2. kaedah untuk memeriksa nilai dengan melintasi jewels rentetan melalui aksara satu demi satu. Set Set dan jadual hach ​​di dalam struktur data, yang membolehkan penggunaan
kaedah untuk masa malar o (1) carian. Walaupun perlu membuat
3. masa awal O (n), ikut carian -up jauh lebih cepat daripada kaedah stones. has()

   Jika saya mempunyai sebarang kesilapan atau anda mempunyai pandangan yang berbeza, sila tinggalkan mesej pada bila -bila masa. Saya sentiasa gembira untuk belajar dari perspektif yang berbeza! ? Jika anda suka artikel ini, sila hubungi saya di LinkedIn pada bila -bila masa.

Atas ialah kandungan terperinci [Algoritma] . Permata dan Batu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!