題目出處

2249. Count Lattice Points Inside a Circle

難度

medium

個人範例程式碼

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        self.ans_set = set()
        for circle in circles:
            self.get_lattice_for_each(circle)

        return len(self.ans_set) 

    def get_lattice_for_each(self, circle):
        cx, cy, r = circle
        for x in range(cx, cx+r+1):
            for y in range(cy, cy+r+1):
                if (cx - x)**2 + (cy - y)**2 <= r**2:
                    self.ans_set.add((x, y))
                    self.ans_set.add((x-2*(x-cx), y))
                    self.ans_set.add((x, y-2*(y-cy)))
                    self.ans_set.add((x-2*(x-cx), y-2*(y-cy)))

算法說明

搜尋範圍內有哪些點，直接的去抓 top, down, left, right，並找尋出現的點

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

速度優化

這邊我們可以做一個數學上的小加速，我們只需要分析 1/4 圓，就能進行後續分析。

優化前

def get_lattice_for_each(self, circle):
    x, y, r = circle
    down, top = y-r, y+r
    left, right = x-r, x+r
    for c_x in range(left, right+1):
        for c_y in range(down, top+1):
            if (x - c_x)**2 + (y - c_y)**2 <= r**2:
                self.ans_set.add((c_x, c_y))

優化後

def get_lattice_for_each(self, circle):
    cx, cy, r = circle
    for x in range(cx, cx+r+1):
        for y in range(cy, cy+r+1):
            if (cx - x)**2 + (cy - y)**2 <= r**2:
                self.ans_set.add((x, y))
                self.ans_set.add((x-2*(x-cx), y))
                self.ans_set.add((x, y-2*(y-cy)))
                self.ans_set.add((x-2*(x-cx), y-2*(y-cy)))

錯誤的討論

這邊我第一次不小心想的太單純，順便記錄一下，
我一開始想說直接把 (cx, cy) 當原點，然後直接加即可，

問題在於「計算出的 (x, y)」，「並不是從 (cx, cy) 出發，而是從 (0, 0) 出發」，
因此才會導致不能直接像我們下圖想的那麼單純，直接減 x

input handling

如果沒有 nums，return nums

Boundary conditions

for loop 控制範圍

Reference

[Java/C++/Python] O(1) Space