算法笔记day10

目录

1.牛牛冲钻五

2.最长无重复子数组_牛客题霸_牛客网

3.重排字符串

1.牛牛冲钻五

算法思路：

特别简单的模拟题，没什么说的。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{    
    int t = 0;
    cin >> t;
    while(t)
    {
        int n ,k ;
        cin >> n >> k;
        string s;
        cin >> s;
        int ret = 0;
        int cnt = 0;
        for(int i = 0; i < n; i++)
        {
            if(s[i] == 'W')
            {
                cnt++;
                if(cnt >= 3)
                {
                    ret += k;
                }
                else
                {
                    ret += 1;
                }
            }
            else
            {
                cnt = 0;
                ret -= 1;
            }  

        }
        cout << ret << endl;
        t--;
    }
    return 0;
}

2.最长无重复子数组_牛客题霸_牛客网

算法思路：

这是一道滑动窗口的题目，只需分析好，什么时候入窗口，什么时候出窗口，什么时候更新返回值。

维护一个窗口，窗口内的元素不会重复，一定会用到哈希表。

入窗口：hash[right]++，将当前元素存储到哈希表中。

出窗口：hash[left]--，将当前元素存从哈希表中删除，直到窗口内没有重复元素。

class Solution {
public:
    
    int maxLength(vector<int>& arr) 
    {
        unordered_map<int,int> map;

        int left = 0, right = 0;
        int ret = 0;
        for(right; right < arr.size(); right++)
        {
            map[arr[right]]++;//入窗口

            while(map[arr[right]] > 1 && left < right)//出窗口
            {
                map[arr[left]]--;
                left++;
            }
            ret = max(ret, right - left + 1);//维护返回值
        } 
        return ret;
    }
};

3.重排字符串

算法思路：

1.判断字符串是否能重排

一定要想到 出现次数最多的字符，如果一个字符出现次数超过一个临界值，就无法进行重排。

将字符串分为，出现最多的字符，和其他字符，将出现最多的字符和其他字符，两个组成一组，这样不就能保证，无相邻的相同字符。

举例： abbcccc

ca cb cb c：找规律发现，只要出现最多的字符  <=（n + 1）/ 2 ，那么就能重排

2.重排

先将出现最多的字符，间隔放置 ，c_ c_ c_c，再将其他字符填入空中

#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;
using std::cin;


int hash[26] = { 0 }; //记录字母出现的次数
string s;

string ret;//返回值
int n = 0;


int main()
{
    cin >> n >> s;
    
    char maxChar = 0;//出现最多次数的字符
    int maxCount = 0;//最多的次数
    for(int i = 0; i < n; i++)
    {
        int index = s[i] -'a';
        if(++hash[index] > maxCount)
        {
            maxChar = s[i];
            maxCount = hash[index];
        }
    }
    
    
    if(maxCount > (n + 1) / 2)
    {
        cout << "no" << endl;
    }
    else
    {
        cout << "yes" << endl;
        ret.resize(n);
        int index = 0;
        while(maxCount--)// 处理出现最多次的字符
        {
            ret[index] = maxChar;
            index += 2;
        }
        
        
        for(int i = 0; i <26 ; i++)//处理其他字符
        {
            if(hash[i] && i + 'a' != maxChar)
            {
                while(hash[i]--)
                {
                    if(index >= n)
                    {
                        index = 1;
                    }
                    
                    ret[index] = i + 'a';
                    index += 2;
                }
            }
        }
        cout << ret << endl;
    }    
    
    return 0;
}