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

2023-12-29 12:08:56

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

文章来源:https://blog.csdn.net/Jack199274/article/details/135281826
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。