leetcode-389周赛

时间:2024-03-18 13:37:20

第一题:字符串及其反转中是否存在同一字符串中

题目如下:

给你一个字符串 s ,请你判断字符串 s 是否存在一个长度为 2 的子字符串,在其反转后的字符串中也出现。

如果存在这样的子字符串,返回 true;如果不存在,返回 false 。

示例 1:

输入:s = "leetcode"

输出:true

解释:子字符串 "ee" 的长度为 2,它也出现在 reverse(s) == "edocteel" 中。

示例 2:

输入:s = "abcba"

输出:true

解释:所有长度为 2 的子字符串 "ab""bc""cb""ba" 也都出现在 reverse(s) == "abcba" 中。

示例 3:

输入:s = "abcd"

输出:false

解释:字符串 s 中不存在满足「在其反转后的字符串中也出现」且长度为 2 的子字符串。

提示:

  • 1 <= s.length <= 100
  • 字符串 s 仅由小写英文字母组成。

第一种思路:暴力破解,将所有长度为2的子字符串放入数组中,再看是否能不能找到在反方向的字符串找到

c++版:

class Solution {
public:
    bool isSubstringPresent(string s) {
        vector<string>l;
        int i;
        int len=s.length();
        string ans="";
        for(i=0;i<len;i++){
            ans+=s[i];
            if(ans.length()==2){
                l.push_back(ans);
                ans=s[i];
            }
        }
          reverse(s.begin(),s.end());
        bool op=false;
        for(auto a:l){
            if(s.find(a)!=-1){
              op=true;
            }
        }
        return op;
        
        
    }
};

第二种:利用二维去存储状态,【x】【y】 翻转之后就是【y】【x】

class Solution {
    public boolean isSubstringPresent(String s) {
        char []u=s.toCharArray();
        boolean[][] res=new boolean[26][26];
        for(int i=1;i<u.length;i++){
            res[u[i-1]-'a'][u[i]-'a']=true;
            if(res[u[i]-'a'][u[i-1]-'a']){
                return true;
            }
        }
        return false;
    }
}

第二题:统计已给定字符开头和结尾的子字符串的总数

给你一个字符串 s 和一个字符 c 。返回在字符串 s 中并且以 c 字符开头和结尾的

非空子字符串

的总数。

示例 1:

输入:s = "abada", c = "a"

输出:6

解释:以 "a" 开头和结尾的子字符串有: "abada""abada""abada""abada""abada""abada"

示例 2:

输入:s = "zzz", c = "z"

输出:6

解释:字符串 s 中总共有 6 个子字符串,并且它们都以 "z" 开头和结尾。

本题很简单,先统计出该字母出现的次数x, 结果就是 x+(x)*(x-1)/2

class Solution {
public:
    long long countSubstrings(string s, char c) {
        long long sum=0,k=0;
        for(int i=0;i<s.length();i++){
            if(s[i]==c) k++ ;
        }
        return k*(k+1)/2;
        
    }
};

 第三题

100255. 成为 K 特殊字符串需要删除的最少字符数 - 力扣(LeetCode)
 

给你一个字符串 word 和一个整数 k

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j  都成立,则认为 word 是 k 特殊字符串

此处,freq(x) 表示字符 x 在 word 中的

出现频率

,而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

示例 1:

输入:word = "aabcaba", k = 0

输出:3

解释:可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba",此时 freq('a') == freq('b') == 2

示例 2:

输入:word = "dabdcbdcdcd", k = 2

输出:2

解释:可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd",此时 freq('b') == 2freq('c') == 3freq('d') == 4

示例 3:

输入:word = "aaabaaa", k = 2

输出:1

解释:可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此,word 变为 "aaaaaa",此时每个字母的频率都是 6

 代码如下:

class Solution {
public:
    int minimumDeletions(string word, int k) {
          vector<int> c(26);
        for (auto e: word)
            ++ c[e - 'a'];
        sort(c.begin(), c.end());
        int n = word.size();
        int ans = n;
        for (int p = 0; p < 26; p ++) {
            if (c[p] == 0)
                continue;
            int tmp = 0;
            for (int i = 0; i < p; i ++)
                tmp += c[i];
            for (int i = p + 1; i < 26; i ++)
                tmp += max(0, c[i] - c[p] - k);
            ans = min(ans, tmp);
        }
        return ans;


    }
};