删除公共字符串、排序子序列、逆置字符串、字符串中连续最长的数字串、数组中次数出现一半的数字

前言

这是关于字符串的相关练习

基础知识

详见string的博客👉戳我

习题

删除公共字符串

删除公共字符串

一、暴力循环

去str1里面找str2的值，然后erase。

时间复杂度 $O(M{N}^2)$

#include 
#include 
using namespace std;

int main()
{
    string str1, str2;
    getline(cin, str1);
    cin >> str2;
    for(size_t j = 0; j < str2.size(); ++j){
        while(str1.find(str2[j]) != string::npos)
            str1.erase(str1.find(str2[j]), 1);
    }
    cout << str1 << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、哈希
题目说了全是字符，而字符最多也就128个，因此定义一个hash[128];

遍历 str2 ，将对于的 hash 值++

再遍历 str1 ，借助 hash 判断 str1 有无要删除的字符。没有的话就加到 ret 上去。

#include 
#include 
using namespace std;

int main()
{
    string str1, str2;
    getline(cin, str1); // cin遇到空格就结束了，用getline输入一行
    getline(cin, str2);
    int hash[128] = {0};
    string ret;
    for(int i = 0; i < str2.size(); ++i)
        hash[str2[i]]++;
    for(int i = 0; i < str1.size(); ++i){
        if(hash[str1[i]] == 0)
            ret += str1[i];
    }
    cout << ret << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

排序子序列

排序子序列

a[i] <= a[i+1] 就是非递减，a[i] >= a[i+1] 就是非递增

a[i] < a[i+1] 是递增，a[i] > a[i+1] 是递减

1 2 3 3 2 1中的 1 2 3 子序列是递增也是非递减，满足。

3 2 1 是递减的，也是非递增，同样满足。

也就是只要遍历非递减或者非递增，就能逐个排除，核心是找非递减非递增的边界。

注意while遍历时不要越界，把 i < v.size() 写在前面。

#include 
#include 
using namespace std;

int main(){

    int n;
    cin >> n;
    vector<int> v;
    v.resize(n);
    int tmp = 0;
    while(n--){
        cin >> v[tmp++];
    }
    int ret = 0, i = 0;
    while(i < v.size()){
        if(v[i] < v[i+1]){
            while(i < v.size() && v[i] <= v[i+1]) // 遍历非递减
                ++i;
            ++i, ++ret; // 碰到边界之后++
        }
        else if(v[i] == v[i+1]) // 相等时不能判断
            ++i;
        else{
            while(i < v.size() && v[i] >= v[i+1]) // 遍历非递增
                ++i;
            ++i, ++ret;
        }
    }
    cout << ret << endl;
    return 0;
}
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

注意，这个代码是有问题的， i 走到 n-1 时，i+1 去访问时会产生越界，只不过牛客的测试用例没有检测出来罢了。

逆置字符串

逆置字符串

#include 
#include 
#include 
using namespace std;

int main()
{
	string str;
	getline(cin, str);
	reverse(str.begin(), str.end()); // 先完全倒置一遍
	for (size_t i = 0; i < str.size(); ++i) {
		int tmp = i;
		while (i < str.size() && str[i] != ' ') // 注意别越界 查找单词分界
			++i;
		reverse(str.begin() + tmp, str.begin() + i); // 倒置每一个单词
	}
	cout << str << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

字符串中找出连续最长的数字串

字符串中找出连续最长的数字串

#include 
#include 
using namespace std;

bool IsContinuousDigit(string& str, int begin, int end){
    for(begin; begin < end; ++begin){
        if(!isdigit(str[begin]))
            return false;
    }
    return true;
}
bool IsContinuousAlpha(string& str, int begin, int end){
    for(begin; begin < end; ++begin){
        if(!isalpha(str[begin]))
            return false;
    }
    return true;
}

int main()
{
    string str;
    cin >> str;
    auto it = str.begin();
    int maxCount = 0, count = 0;
    while(it != str.end()){
        count = 0; // 重置count
        if(isalpha(*it)){ // 字母
            while(it != str.end() && isalpha(*it)){ // 一直是字母
                ++it;
                ++count;
            }
            maxCount = max(maxCount, count);
        }
        else{
            while(it != str.end() && isdigit(*it)){ // 一直是数字
                ++it;
                ++count;
            }
            maxCount = max(maxCount, count);
        }
    }
    string ret;
    // 寻找maxCount个数据的子串
    for(size_t i = 0; i < str.size(); i++){
        if(IsContinuousDigit(str, i, i+maxCount) || IsContinuousDigit(str, i, i+maxCount))
            ret += str.substr(i, maxCount);
    }
    cout << ret << endl;
}
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

由于我一开始看错题目了，把字符串看成数字串。因此多了很多多余操作。

如果只是数字串的话。可以考虑用一个额外的空间tmp来存储全是数字的串，然后当走到不是数字时，与ret比较哪个大，tmp大就把tmp的内容赋值给ret，如果ret大，就清空tmp
继续遍历。

#include 
#include 
using namespace std;

int main()
{
    string str, tmp, ret;
    cin >> str;
    for(size_t i = 0; i < str.size(); ++i)
    {
        if(str[i] >= '0' && str[i] <= '9'){
            tmp += str[i];
        }
        else{ // 非数字时比较size大小
            if(tmp.size() > ret.size())
                ret = tmp;
            else
                tmp.clear();
        }
    }
    // i走到\0的时候，也有可能最后的数字串是最大的，
    // 但此时因为已经跳出for循环了，因此需要再比较一次
    if(tmp.size() > ret.size())
        ret = tmp;
    else
        tmp.clear();
    cout << ret << endl;
    return 0;
}
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

数组中次数出现一半的数字

数组中次数出现一半的数字

一、排序+验证
时间复杂度$O(nlo{g}_{2}n)$不符合要求了，虽然也能跑过。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size() / 2];
        // 虽然这也能通过，但这是因为牛客的测试用例比较少的缘故 有些特殊情况没有考虑
    }
};
1
2
3
4
5
6
7
8

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        // 考虑为空的清空
        if(numbers.empty())
            return 0;
        sort(numbers.begin(), numbers.end()); // 排序
        int midNum = numbers[numbers.size()/2];
        int count = 0;
        for(int i = 0; i < numbers.size(); ++i)
            if(midNum == numbers[i])
                ++count;
        if(count > numbers.size()/2) // 判断是否出现次数超过一半
            return midNum;
        else
            return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、众数非众数互相抵消

出现次数大于数组长度一半的数记为众数，其他的数则是非众数。

遍历，逐个比较前后2个数，如果2个数不相等，互相抵消。

最坏情况下，每次消去一个众数和非众数，如果存在众数，那么最后剩下的就一定是众数。

当然，可能数组中没有众数，因此还需要验证一下是否为众数。

如何相互抵消呢？利用一个count，把第一个数给ret，此时count为1，继续遍历，判断当前数与ret是否相等，相等++count，不相等抵消掉，也就是–count

复杂度为 $O(N)$

class Solution {
    public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty())// 考虑为空的清空
            return 0;
        int ret = numbers[0];
        int count = 1; // 出现的次数，默认为一次
        for(size_t i = 1; i < numbers.size(); ++i){
            if(count != 0){ // count > 1时，通过--count就能达到抵消效果
                if(numbers[i] == ret)
                    ++count;
                else // 不相等
                    --count;
            }else{ // count为0需要更新ret
                ret = numbers[i];
                count = 1;
            }
        }
        count = 0; // 验证是否为众数
        for(int i = 0; i < numbers.size(); ++i)
            if(ret == numbers[i])
                ++count;
        if(count > numbers.size()/2) // 判断是否出现次数超过一半
            return ret;
        else
            return 0;
    }
};
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