笔试专题（六）

最长无重复子数组（滑动窗口）

题目链接

题解

1. 滑动窗口
2. 什么时候进窗口？
不出现重复的元素时进窗口
3. 什么时候判断？
进完窗口之后判断
4. 怎么判断？
hash表中出现两次就进入判断
5. 什么时候出窗口？怎么出窗口？
判断之后出窗口，left++，hash表中对应元素减一
6. 什么时候更新结果？怎么更新结果？
出完窗口之后更新结果，更新最长的长度，right - left + 1

代码

class Solution 
{
public:
    int maxLength(vector<int>& arr) 
    {
        int hash[100001] = {0};
        // 滑动窗口
        int n = arr.size();
        int left = 0,right = 0;
        int ans = 1;
        while(right < n)
        {
            // 进窗口
            hash[arr[right]]++;
            while(left < n && hash[arr[right]] == 2)
            {
                // 出窗口
                hash[arr[left]]--;
                left++;
            }
            // 更新结果
            ans = max(ans,right - left + 1);
            right++;
        }
        return ans;
    }
};

重排字符串（贪心 + 构造）

题目链接

题解

1. 贪心 + 构造
2. 优先处理相同的字母，优先处理最长的相同字母，每次隔一个格子放一个字符
3. 最长的相同字符决定了是否能够重排
4. 怎么重排呢？
先排偶数的位置排最多的字符，再排奇数位置，利用hash表判断是否存在并且不是最多的字符再排

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    string s;
    cin >> n >> s;
    
    // 找出最长的字符是哪个和字符的长度
    int maxcount = 0;
    int maxchar = 0;
    int hash[26] = {0};
    for(auto ch : s)
    {
        hash[ch - 'a']++;
    }
    for(int i = 0;i < 26;i++)
    {
        if(hash[i] > maxcount)
        {
            maxcount = hash[i];
            maxchar = i + 'a';
        }
    }
    // 不能重排  
    if(maxcount > ((n+1)/2))
    {
        cout << "no" << '\n';
        return 0;
    }
    
    cout << "yes" << '\n';
    // 可以重排
    string t = s;
    // 先排最长的字符,排完偶数的位置
    int i = 0;
    while(maxcount--)
    {
        t[i] = maxchar;
        i += 2;
    }
    // 再排剩余字符
    for(int j = 0;j < 26;j++)
    {
        if(hash[j] && j + 'a' != maxchar)
        {
            while(hash[j]--)
            {
                // 排奇数的位置
                if(i >= n) i = 1;
                t[i] = (j + 'a');
                i += 2;
            }
        }
    }
    // 打印最终的字符串
    for(int i = 0;i < n;i++) cout << t[i];
    cout << '\n';
    
    return 0;
}

牛牛冲钻五（模拟）

题目链接

题解

1. 模拟
2. 特判，如果该点是W，并且有前两个点，并且前两个点都是W，加k星，否则加1星，如果该点不是W，减1星，如果该点是W但是没有前两个点，加1星

代码

#include<iostream>
#include<string>
using namespace std;

int main()
{
    int t;
    cin >> t;
    
    while(t--)
    {
        int n,k;
        string s;
        cin >> n >> k >> s;
        
        long long sum = 0;
        for(int i = 0;i < n;i++)
        {
            if(i >= 2 && s[i] == 'W')
            {
                if(s[i-1] == 'W' && s[i-2] == 'W')
                sum += k;
                else sum += 1;
                continue;
            }
            if(s[i] == 'W') sum += 1;
            else sum -= 1;
        }
        cout << sum << '\n';
    }
    
    return 0;
}