Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediummath-number-theory

Pow(x, n)

Problem (yeniden ifade)

pow(x, n): kayan noktalı x’i tamsayı üs n’e yükselt (n negatif olabilir, INT_MIN dahil).

Sezgi

x’i n kez çarpmak doğrusal. İkili üs alma tabanı kareler, üssü yarılar: x^13 = x^8 · x^4 · x^1. Negatif n, 1 / x^|n|. INT_MIN’i 32-bit int olarak negatife çevirme.

Yaklaşımlar

İkili üs alma

Doğrulanmadı

Zaman O(log |n|)Alan O(1)

Fikir. n < 0 ise x’i ters çevir, |n|’i 64-bit üs yap. Üs canlıyken: düşük bit 1 ise cevaba çarp; x’i karele; üssü yarıla.

Yürüyüş. 2^10: 10’un bitleri (1010) 2 ve 8’i seçer → 1024. 2^-2 önce ters çevirir → 0.25.

Trade-off. Şablon. n = -2^31 taşmasın diye long üs. JS’te üs üzerinde >> kullanma (32-bit işaretli); böl.

Çözüm

export function myPow(x: number, n: number): number {
  let e = Math.abs(n);
  if (n < 0) x = 1 / x;
  let ans = 1;
  while (e > 0) {
    if (e % 2 === 1) ans *= x;
    x *= x;
    e = Math.floor(e / 2);
  }
  return ans;
}

export function myPow(x: number, n: number): number {
  let e = Math.abs(n);
  if (n < 0) x = 1 / x;
  let ans = 1;
  while (e > 0) {
    if (e % 2 === 1) ans *= x;
    x *= x;
    e = Math.floor(e / 2);
  }
  return ans;
}

Özyinelemeli kare-ve-çarp

Doğrulanmadı

Zaman O(log |n|)Alan O(log |n|) stack

Fikir. pow(x, 0) = 1. half = pow(x, ⌊e/2⌋); çift → half², tek → half² · x. Negatif n 1 / pow(x, |n|).

Yürüyüş. Aynı 2^10: beş yığın karesi, her biri kareler. Sonuç 1024.

Trade-off. Yineleme kanıtın kendisi. Yığın log derinlikte. Mülakatta genelde iteratif döngü istenir.

Çözüm

export function myPow(x: number, n: number): number {
  const pow = (base: number, e: number): number => {
    if (e === 0) return 1;
    const half = pow(base, Math.floor(e / 2));
    const sq = half * half;
    return e % 2 === 0 ? sq : sq * base;
  };
  return n < 0 ? 1 / pow(x, -n) : pow(x, n);
}

export function myPow(x: number, n: number): number {
  const pow = (base: number, e: number): number => {
    if (e === 0) return 1;
    const half = pow(base, Math.floor(e / 2));
    const sq = half * half;
    return e % 2 === 0 ? sq : sq * base;
  };
  return n < 0 ? 1 / pow(x, -n) : pow(x, n);
}

Şablon bağlantısı

Math & Number Theory’nin modular-exponent şekli, modulusuz: kare-ve-çarp, modPow ile aynı döngü. LC 372 % 1337 ve basamak dizisi ekler.

Yansıma

Üssün bitleri. Tabanı karele, bit 1 ise sonuca çarp. Çarpma sayısı O(log n).
Negatif üs: pozitif üssün tersi. int alt sınırının negatifi taşar; üssü geniş tut veya önce böl.
Üs 0 cevap 1. Taban 0 ve üs negatif: sıfıra bölme.