418.屏幕可显示句子的数量

题目链接：418.sentence-screen-fitting

解法：

这道题，看题解都很难看懂，哪怕看出点门道了，也很难用自己的话解释出来。

有几点必须清楚：

（1）将字符串列表连接成一个长字符串，每个字符串后面都加一个空格。假设这个字符串会一直循环下去，那么其实就是一个滚动数组。

（2）如果长字符串的长度为len，滚动数组的某个位置为start，那么该位置的元素为 string[start % len]。所以解法中通过 start % len 获取start这个位置在长字符串中对应的元素。

（3）定义的start，非常不好理解。我觉得可以理解为原矩阵中，新的一行的位置，在滚动数组中对应的位置。比如第一个f，在原矩阵中应该是下标为6的（对矩阵展开，从0开始计下标），但在滚动数组中是7。题解中，通过 ++ 或者 -- 的操作，是为了得到滚动数组中对应的位置。

（4）移动start时两种情况需要处理一下：1) 一行的开头刚好是space，start指针直接+1，即原矩阵remove一个space，而滚动数组中保留这个space，所以start+1。注意，明明是消除space，反而还要加1，因为滚动数组中保留了这个space；2）一行的开头刚好是一个word的中间，如果前一个为空格，则start不变，如果不为空格，则start需要减1。即start需要退回到该word的开头，在上一行增加一些space。

参考题解：https://medium.com/@rebeccahezhang/leetcode-418-sentence-screen-fitting-9d6258ce116e

[LC 418]. Sentence Screen Fitting – BlurryJam, life is a game

边界条件：无

时间复杂度：O(row * col)

空间复杂度：O(length)，length为长字符串的长度。

class Solution {
public:int wordsTyping(vector<string>& sentence, int rows, int cols) {string str;for (const auto& s: sentence) {str += s + ' ';}int len = str.size();int start = 0;for (int i=0; i<rows; i++) {start += cols;if (str[start % len]==' ') {start++;} else {while (start > 0 && str[(start-1) % len]!=' ') {start--;}}}return start / len;}
};

395.至少有K个重复字符的最长子串

题目链接：395.longest-substring-with-at-least-k-repeating-characters

解法：

一种解法是滑动窗口，看评论区说挺难滑的，比较复杂，这次就跳过了。

参考的是递归的实现思路。

（1）递归的终止条件：如果字符串 s的长度少于 k，那么一定不存在满足题意的子字符串，返回 0；

（2）递归内部实现：如果一个字符 c 在 s 中出现的次数少于 k次，那么 s中所有的包含 c 的子字符串都不能满足题意。所以，应该在 s 的所有不包含 c的子字符串中继续寻找结果：把 s 按照 c 分割，得到很多子字符串 t；下一步要求 t作为源字符串的时候，它的最长的满足题意的子字符串长度，这就是递归子问题了。一旦找到一个这样的t，就会一直递归下去，直到返回结果。

（3）如果 s 中的每个字符出现的次数都大于 k 次，那么 s 就是我们要求的字符串，直接返回该字符串的长度。

参考题解：递归

边界条件：无

时间复杂度：O(N∗26∗26)，因为函数最多执行 26 次，for循环遍历一次是26个字符，循环里面对 s分割时间复杂度是O(N)。
空间复杂度：O(26∗26)，函数最多执行 26 次，每次最多开辟26的map空间。

class Solution {
public:int longestSubstring(string s, int k) {if(s.size() < k) return 0;unordered_map<char, int> counter;for (char c: s) {counter[c]++;}for (const auto&pair: counter) {char c = pair.first;int count = pair.second;if (count < k) {// 注意res的位置int res = 0;size_t start = 0;size_t pos = s.find(c, start);string sub;// 用来实现split的效果，string:npos表示没找到while (pos != string::npos) {sub = s.substr(start, pos-start);res = max(res, longestSubstring(sub,k));start = pos+1;pos = s.find(c, start);}sub = s.substr(start);res = max(res,longestSubstring(sub,k));return res;}}return s.size();}
};

1010.总持续时间可以被60整除的歌曲对

题目链接：1010.pairs-of-songs-with-total-durations-divisible-by-60

解法：

和两数之和类似，区别在于两数之和中，存储的是 当前的num，寻找的是target-num，而这里存储的是当前time的模，寻找的是模和当前的模可以相加为target(60)的数。

当前time的模为 time % 60，对应的数的模为：60 - time % 60，比如time=62，那么对应的数可以是58,118，模=60 - 62 % 60 = 58。这是 time 不为60的倍数的情况。

一种特殊情况是time=60,120,etc。这种情况下 time % 60 = 0, 而上面的公式 60 - 60 % 60 = 60，不满足要求，所以改为 (60 - time % 60) % 60。

而(60 - time % 60) % 60在time不为60的情况下，等价于60 - time % 60，于是一般情况和特殊情况都统一为了：(60 - time % 60) % 60

参考题解：借鉴两数之和

边界条件：无

时间复杂度：O(n)

空间复杂度：O(60)

class Solution {
public:int numPairsDivisibleBy60(vector<int>& time) {int res = 0;vector<int> cnt(60);for (int t: time) {// 注意这两行代码的顺序res += cnt[(60 - t % 60) % 60];cnt[t % 60]++;}return res;}
};