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

Hardunion-find

Number of Islands II

Problem (yeniden ifade)

m×n su ızgarası. positions hücreleri tek tek karaya çevirir. Her eklemeden sonra güncel ada sayısını döndür (4-bağlı kara).

Sezgi

Her yeni kara kendi adası olarak başlar (+1), ardından zaten kara olan komşularla birleşir; bileşenler birleşince sayaç azalır.

Yaklaşımlar

Izgarada çevrimiçi Union-Find

Doğrulanmadı

Zaman O(k α(mn))Alan O(mn)

Fikir. Hücre id = r*n+c. parent[id]=-1 su demektir. Yinelenen konumları atla.

Adım adım. m=3,n=3, positions [[0,0],[0,1],[1,2],[2,1]] → [1,1,2,3].

Trade-off’lar. Çevrimdışı ters UF da işe yarar; çevrimiçi mülakatın doğal yoludur.

Çözüm

export function numIslands2(m: number, n: number, positions: number[][]): number[] {
  const parent = Array(m * n).fill(-1);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  let count = 0;
  const res: number[] = [];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (const p of positions) {
    const r = p[0]!, c = p[1]!;
    const id = r * n + c;
    if (parent[id] !== -1) {
      res.push(count);
      continue;
    }
    parent[id] = id;
    count++;
    for (const d of dirs) {
      const nr = r + d[0]!, nc = c + d[1]!;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      const nid = nr * n + nc;
      if (parent[nid] === -1) continue;
      const a = find(id), b = find(nid);
      if (a !== b) {
        parent[b] = a;
        count--;
      }
    }
    res.push(count);
  }
  return res;
}

export function numIslands2(m: number, n: number, positions: number[][]): number[] {
  const parent = Array(m * n).fill(-1);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  let count = 0;
  const res: number[] = [];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (const p of positions) {
    const r = p[0]!, c = p[1]!;
    const id = r * n + c;
    if (parent[id] !== -1) {
      res.push(count);
      continue;
    }
    parent[id] = id;
    count++;
    for (const d of dirs) {
      const nr = r + d[0]!, nc = c + d[1]!;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      const nid = nr * n + nc;
      if (parent[nid] === -1) continue;
      const a = find(id), b = find(nid);
      if (a !== b) {
        parent[b] = a;
        count--;
      }
    }
    res.push(count);
  }
  return res;
}

Şablon bağlantısı

Union-Find ile dinamik bağlanırlık.

Yansıma

Su karaya dönünce 4 komşu karayla birleş. Her eklemeden sonra bileşen sayısı cevap listesine girer.
Aynı hücre iki kez gelirse sayaç artmaz. Çapraz komşu birleşmez.
İlk kara 1. İki bitişik kara ikinci adımda 1’e iner.