1274. Number of Ships in a Rectangle #92
Description
https://leetcode.com/problems/number-of-ships-in-a-rectangle
Burada, bir deniz (Sea) satranç tahtasına benzeyen bir grafikle (cartesian plane) belirtilmiş.
Bize sorulan şu:
int[] topRight, int[] bottomLeft, koordinatları ile bir büyük kare veriliyor. Biz bu karedeki gemi sayısını bulmalıyız.
Gemiler, koordinat noktaları ile belirtiliyor ama bizim bu noktaları içeren array'e doğrudan erişimimiz yok.
Biz bu array'e "Sea" denilen bir interface aracılığı ile erişip, bizim vereceğimiz karede gemi olup olmadığını soracağız.
Biz kareyi nasıl belirtiyoruz?
Biz de bu şekilde int[] topRight, int[] bottomLeft koordinatlarını, Sea interface'indeki hasShip methoduna gönderebiliriz.
Sorun şu ki, hasShip methodu, bizim gönderdiğimiz kare içerisinde "kaç gemi olduğunu" değil, "gemi olup olmadığını" veriyor.
Soru ise bizden, kendi verdikleri büyük karede kaç gemi olup olmadığını soruyor.
Not: Burada topRight= karenin sağ-üst noktasıdır; bottomLeft ise sol-alt noktasıdır. Kareyi bu iki nokta ile belirleyeceğiz.
Önemli not: Divide-and-conquer algoritması çalışılmalı.