Langsung ke konten
Brute force dulu

Pelajaran 3.4

Temukan kerja yang diulang

7 menit · 7 langkah

  1. Langkah 1 dari 7 · Penjelasan

    Soal: "Return array di mana out[i] adalah jumlah nums[0] sampai nums[i]."

    Brute force-nya menjumlahkan ulang dari awal untuk setiap i, dengan loop dalam j dari 0 sampai i. Untuk [3, 1, 4, 2], out[2] menghitung 3 + 1 + 4 dari nol, padahal 3 + 1 sudah dihitung untuk out[1]. Setiap putaran mengulang penjumlahan yang sudah dilakukan putaran sebelumnya.

  2. Langkah 2 dari 7 · Tebak hasilnya

    Berapa kali penjumlahan terjadi untuk 4 item?

    function solution(nums) {  let adds = 0  for (let i = 0; i < nums.length; i++) {    for (let j = 0; j <= i; j++) {      adds++    }  }  return adds}
    1. 10
    2. 4
    3. 16

  3. Langkah 3 dari 7 · Pilih pendekatan

    Brute force untuk running sum: loop luar i jalan di setiap item. Di dalamnya, sum mulai dari 0, loop j menjumlahkan nums[0] sampai nums[i], lalu out.push(sum).
    Kerja apa yang diulang-ulang?

    1. Menjumlahkan ulang nums[0] sampai nums[i - 1], padahal hasilnya sudah ada di putaran sebelumnya
    2. out.push(sum) di setiap putaran
    3. Loop luar i
    4. Membaca nums.length

  4. Langkah 4 dari 7 · Susun kodenya

    Susun versi O(n) untuk running sum, di mana out[i] adalah jumlah nums[0] sampai nums[i]. Simpan jumlah sejauh ini. Dua baris tidak termasuk.

    return outsum += nums[i]out.push(sum)}const out = []}for (let i = 0; i < nums.length; i++) {let sum = 0function solution(nums) {sum = nums[i]for (let i = 1; i < nums.length; i++) {

  5. Langkah 5 dari 7 · Pilih pendekatan

    Brute force lain: "Untuk setiap i, cek dengan loop dalam apakah nums[i] sudah muncul sebelumnya." Itu O(n²).
    Apa yang bisa menjawab "sudah pernah lihat?" dalam satu langkah?

    1. Set atau Map yang menyimpan setiap angka yang sudah lewat
    2. Sort ulang array di setiap putaran
    3. Loop dalam dengan j = i + 1
    4. Satu variable yang menyimpan angka sebelumnya

  6. Langkah 6 dari 7 · Tebak hasilnya

    Apa yang di-return untuk [5, 3, 5, 3]?

    function solution(nums) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    if (seen.has(nums[i])) {      return [seen.get(nums[i]), i]    }    seen.set(nums[i], i)  }  return []}
    1. [0, 2]
    2. [1, 3]
    3. [2, 0]
    4. []

  7. Langkah 7 dari 7 · Ringkasan

    • Setelah brute force jalan, cari loop dalam yang menghitung ulang sesuatu.
    • Simpan hasil sejauh ini, seperti running total, supaya tidak dihitung ulang.
    • "Sudah pernah lihat?" bisa dijawab dalam satu langkah dengan Set atau Map.

    Kartu pola

    Kerja yang diulang
    Kapan dipakai: Saat brute force kamu benar tapi terlalu lambat. Tanya: apa yang dihitung loop dalam yang sebenarnya sudah diketahui?
    let sum = 0for (const x of nums) {  sum += x      // simpan / keep it  out.push(sum)}