LeetCode Grinding
Algorithms2 menit baca

Pengenalan Knowing What to Track

Pilih state yang dibutuhkan sebuah algoritma, misalnya jumlah kemunculan, value yang udah dikunjungi, atau hasil terbaik sejauh ini.

Di artikel ini 3 bagian

Pengecekan duplikat perlu tahu apakah sebuah value udah muncul. Pengecekan permutasi perlu tahu berapa kali setiap value muncul. Perbedaan ini menentukan apa yang aku simpan saat menelusuri input.

Hitung dulu, lalu pakai hasil hitungannya

Frequency counting punya dua fase. Pertama, aku men-scan input dan mencatat seberapa sering tiap value muncul. Lalu aku pakai catatan itu untuk menjawab pertanyaan yang sebenarnya, misalnya mencari duplikat atau membandingkan dua input.

Hitungan berguna untuk membandingkan dua input atau mencari value yang paling sering muncul. Kalau yang penting cuma ada atau nggaknya sebuah value, penanda keanggotaan bisa cukup.

Contoh dan pilihan penyimpanan

Pengecekan duplikat ini menghitung kemunculan setiap value, lalu mencari hitungan di atas satu:

javascript
function hasDuplicate(nums) {
  const counts = {};

  // Counting phase
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }

  // Utilization phase
  for (let num in counts) {
    if (counts[num] > 1) {
      return true; // Found a duplicate!
    }
  }
  return false;
}

Untuk permutasi, hitung karakter di string pertama lalu kurangi hitungannya memakai karakter dari string kedua:

javascript
function arePermutations(str1, str2) {
  if (str1.length !== str2.length) return false;

  const counts = {};

  // Count characters in first string
  for (let char of str1) {
    counts[char] = (counts[char] || 0) + 1;
  }

  // Decrement for second string
  for (let char of str2) {
    if (!counts[char]) return false;
    counts[char]--;
  }

  // All should be zero if they're permutations
  return Object.values(counts).every((count) => count === 0);
}

Hash map adalah pilihan yang umum. Aku pakai tiap elemen sebagai key dan frekuensinya sebagai value:

javascript
const frequency = {};
for (let item of data) {
  frequency[item] = (frequency[item] || 0) + 1;
}

Kalau value-nya integer kecil, sebuah array bisa memakai value itu sebagai index:

javascript
const frequency = new Array(26).fill(0); // For lowercase letters
for (let char of str) {
  frequency[char.charCodeAt(0) - "a".charCodeAt(0)]++;
}

Kompleksitas dan checklist

Pass penghitungan butuh O(n) waktu, lalu dilanjutkan dengan menelusuri value yang berbeda. Hash map memakai O(k) space untuk k value berbeda. Array berukuran tetap menyediakan tempat untuk seluruh rentang yang dipilih.

Aku memilih state dari pertanyaan yang harus dijawab langkah berikutnya. Menyimpan hitungan saat yang dibutuhkan cuma keanggotaan tetap bisa jalan, tapi menyimpan informasi lebih banyak dari yang diperlukan.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan