Giả sử ta có một chuỗi S và ta phải viết các ký tự của chuỗi đó từ trái sang phải vào các dòng. Mỗi dòng có độ rộng tối đa 100 đơn vị, và nếu viết một ký tự làm độ rộng dòng vượt quá 100, ký tự đó sẽ được viết ở dòng tiếp theo. Ta cũng có mảng widths, trong đó widths[0] là độ rộng của 'a', widths[1] là của 'b', và cứ thế.
Ta cần trả lời hai câu hỏi:
- Có bao nhiêu dòng chứa ít nhất một ký tự từ S
- Độ rộng được sử dụng bởi dòng cuối cùng là bao nhiêu
Kết quả trả về là danh sách nguyên có độ dài 2.
Ví dụ, nếu đầu vào là [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10] và S = "bbbcccdddaaa", thì đầu ra sẽ là [2, 4], vì tất cả các chữ cái trừ 'a' có độ dài 10, và chuỗi "bbbcccdddaa" sẽ chiếm 9 * 10 + 2 * 4 = 98 đơn vị. Ký tự 'a' cuối cùng được viết ở dòng thứ hai vì dòng đầu chỉ còn 2 đơn vị. Vậy câu trả lời là 2 dòng, thêm 4 đơn vị ở dòng thứ hai.
Để giải quyết, ta thực hiện các bước sau:
- line := 1, count := 0
- Với mỗi i trong S, thực hiện:
- count := count + widths[ASCII của i - 97]
- Nếu count > 100, thì:
- line := line + 1
- count := widths[ASCII của i - 97]
- Trả về [line, count]
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def numberOfLines(self, widths, S): line = 1 count = 0 for i in S: count += widths[ord(str(i))-97] if count > 100: line += 1 count = widths[ord(str(i))-97] return [line, count] ob = Solution() print(ob.numberOfLines([4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], "bbbcccdddaaa"))
Đầu vào
[4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],"bbbcccdddaaa"
Đầu ra
[2, 4]