数据结构
网络
关系数据库管理系统(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 次浏览
广告