TikTok真题第8天 | 418.屏幕可显示句子的数量、395.至少有K个重复字符的最长子串、1010.总持续时间可以被60整除的歌曲对

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;
    }
};