Đề bài
The infinite spiral starts at the top-left cell. The first four rows and columns are shown below. Continue the same pattern in expanding square layers. Coordinates start at 1.
1 2 9 10
4 3 8 11
5 6 7 12
16 15 14 13Return one cell value without constructing the entire grid.
Implement number_spiral(row, column).
Input
row: The row counted from the top, starting at 1.
column: The column counted from the left, starting at 1.
Output
Return the number at that position.
Ràng buộc
1 ≤ row, column ≤ 1,000,000,000. The value fits a signed 64-bit integer.
Ví dụ
Đầu vào:
row = 3
column = 2
Kết quả mong đợi:
expected = 6Đầu vào:
long long row = 3;
long long column = 2;
Kết quả mong đợi:
long long expected = 6;Đầu vào:
long row = 3;
long column = 2;
Kết quả mong đợi:
long expected = 6;Giải thích
In the displayed third row, the second value is 6.
Đầu vào:
row = 1
column = 4
Kết quả mong đợi:
expected = 10Đầu vào:
long long row = 1;
long long column = 4;
Kết quả mong đợi:
long long expected = 10;Đầu vào:
long row = 1;
long column = 4;
Kết quả mong đợi:
long expected = 10;Giải thích
The fourth square layer begins at 10 in the top row.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
The spiral is built in square layers, so a cell belongs to a layer determined by the larger coordinate.
Gợi ý 2
Use the parity of that layer to decide whether values increase along a row or a column.
Gợi ý 3
Pay attention to whether the layer reaches from the top-left corner or the opposite corner first.
Độ phức tạp mong đợi
O(1) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.