Đề bài
Hãy hình dung một lưới có height hàng và width cột, cả hai đều đánh số từ 0. Một đường dấu sao bắt đầu ở ô góc trên bên trái, mỗi bước dịch sang phải một cột: nó đi xuống mỗi lần một hàng cho đến khi chạm hàng dưới cùng, rồi đi lên mỗi lần một hàng cho đến khi chạm hàng trên cùng, và cứ lặp lại như vậy. Nói chính xác: đặt P = 2(height − 1) và p = c mod P. Cột c có dấu sao duy nhất ở hàng p nếu p < height, ngược lại ở hàng P − p. Mọi ô còn lại là dấu cách.
Hãy viết zigzag_wave_pattern(width, height).
Đầu vào
width: Số cột.
height: Số hàng.
Đầu ra
Trả về height chuỗi theo thứ tự từ trên xuống, đã xóa dấu cách thừa ở cuối. Hàng nào không có dấu sao thì là chuỗi rỗng.
Ràng buộc
1 ≤ width ≤ 80, 2 ≤ height ≤ 20
Ví dụ
Đầu vào:
width = 9
height = 3
Kết quả mong đợi:
expected = ["* * *", " * * * *", " * *"]
Đầu vào:
long long width = 9;
long long height = 3;
Kết quả mong đợi:
std::vector<std::string> expected = {"* * *", " * * * *", " * *"};
Đầu vào:
long width = 9;
long height = 3;
Kết quả mong đợi:
string[] expected = new string[] {"* * *", " * * * *", " * *"};
Giải thích
P = 4, nên các cột từ 0 đến 8 lần lượt dùng hàng 0, 1, 2, 1, 0, 1, 2, 1, 0: ["* * *", " * * * *", " * *"].
Đầu vào:
width = 5
height = 2
Kết quả mong đợi:
expected = ["* * *", " * *"]
Đầu vào:
long long width = 5;
long long height = 2;
Kết quả mong đợi:
std::vector<std::string> expected = {"* * *", " * *"};
Đầu vào:
long width = 5;
long height = 2;
Kết quả mong đợi:
string[] expected = new string[] {"* * *", " * *"};
Giải thích
Với hai hàng, dấu sao luân phiên ở trên và ở dưới: ["* * *", " * *"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chuyển động lặp lại sau mỗi 2(height − 1) cột.
Gợi ý 2
Trong một chu kỳ, hàng đi xuống từ 0 đến height − 1 rồi đi lên trở lại.
Gợi ý 3
Có thể dễ hơn nếu bạn tạo trước một lưới 2 chiều toàn dấu cách, rồi mới đổi từng hàng thành chuỗi.
Độ phức tạp mong đợi
thời gian O(width * height), bộ nhớ phụ O(width * height)
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.