Leetcode-第8场双周赛

发表于 分类于 阅读次数：

5067.统计只含单一字母的子串

题目描述

给你一个字符串 S，返回只含 单一字母 的子串个数。

示例 1：

1
2
3
4
5
6
7
8
9
输入： "aaaba"
输出： 8
解释： 
只含单一字母的子串分别是 "aaa"， "aa"， "a"， "b"。
"aaa" 出现 1 次。
"aa" 出现 2 次。
"a" 出现 4 次。
"b" 出现 1 次。
所以答案是 1 + 2 + 4 + 1 = 8。

示例 2:

1
2
输入： "aaaaaaaaaa"
输出： 55

提示：

  1. 1 <= S.length <= 1000
  2. S[i] 仅由小写英文字母组成。
解法1：暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int countLetters(string S) {
        int n=S.size();
        int res=0;
        int temp=1;
        int k=1;
        char c=S[0];
        for(int i=1;i<n;i++)
        {
            if(S[i]==c)
            {
                k++;
                temp+=k;
            }
            else
            {
                res+=temp;
                k=1;
                temp=1;
                c=S[i];
            }
        }
        res+=temp;
        return res;
    }
};

5068.前后拼接

题目描述

给你一个「短语」列表 phrases，请你帮忙按规则生成拼接后的「新短语」列表。

「短语」（phrase）是仅由小写英文字母和空格组成的字符串。「短语」的开头和结尾都不会出现空格，「短语」中的空格不会连续出现。

「前后拼接」（Before and After puzzles）是合并两个「短语」形成「新短语」的方法。我们规定拼接时，第一个短语的最后一个单词 和 第二个短语的第一个单词 必须相同。

返回每两个「短语」 phrases[i] 和 phrases[j]（i != j）进行「前后拼接」得到的「新短语」。

注意，两个「短语」拼接时的顺序也很重要，我们需要同时考虑这两个「短语」。另外，同一个「短语」可以多次参与拼接，但「新短语」不能再参与拼接。

请你按字典序排列并返回「新短语」列表，列表中的字符串应该是 不重复的 。

示例 1：

1
2
输入：phrases = ["writing code","code rocks"]
输出：["writing code rocks"]

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：phrases = ["mission statement",
                "a quick bite to eat",
                "a chip off the old block",
                "chocolate bar",
                "mission impossible",
                "a man on a mission",
                "block party",
                "eat my words",
                "bar of soap"]
输出：["a chip off the old block party",
      "a man on a mission impossible",
      "a man on a mission statement",
      "a quick bite to eat my words",
      "chocolate bar of soap"]

示例 3：

1
2
输入：phrases = ["a","b","a"]
输出：["a"]

提示：

  • 1 <= phrases.length <= 100
  • 1 <= phrases[i].length <= 100
解法1：暴力

思路：phrases的长度只有100，100*100也只有10000的复杂度，所以我们直接暴力，判断首尾，最后对数组排序再去重就得到了结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
        vector<string> res;
        int len=phrases.size();
        for(int i=0;i<len;i++)
        {
            string s1l="";
            string s1r="";
            int l1;
            int k;
            for(k=0;k<phrases[i].size()&&phrases[i][k]!=' ';k++)
            {
                s1l+=phrases[i][k];
            }
            l1=k;
            for(k=phrases[i].size()-1;k>=0&&phrases[i][k]!=' ';k--)
            {
                s1r+=phrases[i][k];
            }
            reverse(s1r.begin(),s1r.end());
            
            for(int j=i+1;j<len;j++)
            {
                string s2l="";
                string s2r="";
                int l2;
                for(k=0;k<phrases[j].size()&&phrases[j][k]!=' ';k++)
                {
                    s2l+=phrases[j][k];
                }
                
                l2=k;
                for(k=phrases[j].size()-1;k>=0&&phrases[j][k]!=' ';k--)
                {
                    s2r+=phrases[j][k];
                }
                reverse(s2r.begin(),s2r.end());
                if(s1r==s2l)
                {
                    string temp=phrases[i]+phrases[j].substr(l2);
                    res.push_back(temp);
                }
                if(s2r==s1l)
                {
                    string temp=phrases[j]+phrases[i].substr(l1);
                    res.push_back(temp);
                }
            }
        }
        sort(res.begin(),res.end());
        vector<string>::iterator iter=unique(res.begin(),res.end());
        res.erase(iter,res.end());
        return res;
    }
};

5070.与目标颜色间的最短距离

题目描述

给你一个数组 colors，里面有 1、2、 3 三种颜色。

我们需要在 colors 上进行一些查询操作 queries，其中每个待查项都由两个整数 i 和 c 组成。

现在请你帮忙设计一个算法，查找从索引 i 到具有目标颜色 c 的元素之间的最短距离。

如果不存在解决方案，请返回 -1。

示例 1：

1
2
3
4
5
6
输入：colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
输出：[3,0,3]
解释： 
距离索引 1 最近的颜色 3 位于索引 4（距离为 3）。
距离索引 2 最近的颜色 2 就是它自己（距离为 0）。
距离索引 6 最近的颜色 1 位于索引 3（距离为 3）。

示例 2：

1
2
3
输入：colors = [1,2], queries = [[0,3]]
输出：[-1]
解释：colors 中没有颜色 3。

提示：

  • 1 <= colors.length <= 5*10^4
  • 1 <= colors[i] <= 3
  • 1 <= queries.length <= 5*10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] < colors.length
  • 1 <= queries[i][1] <= 3
解法1：左右各遍历1次

1.先从左往右遍历。记录这个索引下，各种颜色离这个索引位置最近的索引（即当前该颜色的最大值）

2.同样从右往左遍历。

3.选择左右离这个索引最近的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        vector<int> res;
        int n=colors.size();
        int m=queries.size();
        vector<vector<int>> left(4,vector<int>(50005,0));
        vector<vector<int>> right(4,vector<int>(50005,0));
        for(int i=1;i<=3;i++)
        {
            int x=-1;
            for(int j=0;j<colors.size();j++)
            {
                if(colors[j]==i)
                    x=j;
                left[i][j]=x;
            }
        }
        for(int i=1;i<=3;i++)
        {
            int x=-1;
            for(int j=colors.size()-1;j>=0;j--)
            {
                if(colors[j]==i)
                    x=j;
                right[i][j]=x;
            }
        }
        for(int i=0;i<m;i++)
        {
            int index=queries[i][0];
            int color=queries[i][1];
            int l=left[color][index];
            int r=right[color][index];
            if(l==-1&&r==-1)
            {
                res.push_back(-1);
                continue;
            }
            int val=INT_MAX;
            if(l!=-1)
                val=min(abs(left[color][index]-index),val);
            if(r!=-1)
                val=min(abs(right[color][index]-index),val);
            res.push_back(val);
        }
        return res;
    }
};

5082.矩阵中1的最大数量

题目描述

现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。

而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。

请你设计一个算法，计算矩阵中最多可以有多少个 1。

示例 1：

1
2
3
4
5
6
7
8
输入：width = 3, height = 3, sideLength = 2, maxOnes = 1
输出：4
解释：
题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。
最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：
[1,0,1]
[0,0,0]
[1,0,1]

示例 2：

1
2
3
4
5
6
输入：width = 3, height = 3, sideLength = 2, maxOnes = 2
输出：6
解释：
[1,0,1]
[1,0,1]
[1,0,1]

提示：

  • 1 <= width, height <= 100
  • 1 <= sideLength <= width, height
  • 0 <= maxOnes <= sideLength * sideLength
解法1：

循环矩阵

以sideLength的正方形为一个循环，找到每个位置在大矩阵中出现的次数，选择出现次数最多的前maxOnes位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        int a[101][101] ={{0}};
        vector<int> cnt;
        for(int i=0; i<width;i++){
            for(int j=0;j<height;j++){
                a[i%sideLength][j%sideLength]++;
            }
        }
        for(int i=0;i<sideLength;i++){
            for(int j=0;j<sideLength;j++){
                cnt.push_back(a[i][j]);
            }
        }
        sort(cnt.begin(),cnt.end());
        reverse(cnt.begin(),cnt.end());
        int ans = 0;
        for(int i=0;i<maxOnes;i++){
            ans += cnt[i];
        }
        return ans;
    }
};