การติดตั้งหน้าจอประโยคใน C++

สมมติว่าเรามีหน้าจอแถว x cols และประโยคที่แสดงโดยรายการคำที่ไม่เว้นว่างไว้ ดังนั้นเราต้องค้นหาว่าประโยคที่กำหนดนั้นสามารถติดตั้งบนหน้าจอได้กี่ครั้ง มีคุณสมบัติบางอย่าง -

• คำจะไม่ถูกแบ่งออกเป็นสองบรรทัด

• ต้องไม่เปลี่ยนลำดับของคำในประโยค

• จะมีช่องว่างเพียงช่องเดียวระหว่างคำสองคำ

• จำนวนคำทั้งหมดในประโยคจะไม่เกิน 100

• ความยาวของแต่ละคำมากกว่า 0 แต่น้อยกว่า 10

• 1 ≤ แถว cols ≤ 20,000

ดังนั้นหากอินพุตเป็นเหมือนแถว =3 และ cols =6 และประโยคคือ [“a”, “bcd”, “e”] ผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ dp ตั้งค่า ret :=0, n :=ขนาดของอาร์เรย์ประโยค

• ในขณะที่แถวไม่ใช่ 0

  • start :=ret mod n, len :=-l and cnt :=0

  • ถ้า start ไม่มีอยู่ใน dp แล้ว

    • ในขณะที่ 1 + len + ขนาดของประโยค[(start + cnt) mod n] <=cols

      • len :=1 + len + ประโยค[(start + cnt) mod n]

      • เพิ่มขึ้นอีก 1

    • dp[start] :=cnt

    • ret :=ret + cnt

  • มิฉะนั้น ret :=ret + dp[start]

  • แถว :=แถว – 1

• ผลตอบแทนย้อนหลัง/n

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int wordsTyping(vector<string>& sentence, int rows, int cols) {
      unordered_map <int, int> dp;
      int ret = 0;
      int n = sentence.size();
      while(rows--){
         int start = ret % n;
         int len = -1;
         int cnt = 0;
         if(!dp.count(start)){
            while(1 + len + (int)sentence[(start + cnt) % n].size() <= cols){
               len = 1 + len + sentence[(start + cnt) % n].size();
               cnt++;
            }
            dp[start] = cnt;
            ret += cnt;
         }
         else{
            ret += dp[start];
         }
      }
      return ret / n;
   }
};
main(){
   vector<string> v = {"a","bcd","e"};
   Solution ob;
   cout << (ob.wordsTyping(v, 3, 6));
}

อินพุต

["a","bcd","e"]
3
6

ผลลัพธ์

2