資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++句子螢幕適配
假設我們有一個rows x cols的螢幕和一個由一系列非空單詞表示的句子，我們需要找到給定句子可以在螢幕上適配多少次。有一些屬性：
一個單詞不會被分成兩行。
句中單詞的順序不能改變。
兩個單詞之間只有一個空格。
句子中的單詞總數不超過100。
每個單詞的長度大於0，小於10。
1 ≤ rows, cols ≤ 20,000。
因此，如果輸入類似於rows = 3，cols = 6，句子是[“a”, “bcd”, “e”]，則輸出為2。
為了解決這個問題，我們將遵循以下步驟：
定義一個map dp，設定ret := 0，n := 句子的陣列大小
當row不為0時
start := ret mod n，len := -1，cnt := 0
如果dp中不存在start，則
當1 + len + sentence[(start + cnt) mod n]的大小 <= cols時
len := 1 + len + sentence[(start + cnt) mod n]
cnt加1
dp[start] := cnt
ret := ret + cnt
否則 ret := ret + dp[start]
row := row – 1
返回ret/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
更新於：2020年4月29日
134 次瀏覽
廣告