【算法手记11】NC41 最长无重复子数组 NC379 重排字符串

2025/4/18 10:10:35 来源：https://blog.csdn.net/weixin_72357342/article/details/147052700 浏览: 次关键词：【算法手记11】NC41 最长无重复子数组 NC379 重排字符串

🦄个人主页:修修修也

🎏所属专栏:刷题

⚙️操作环境:牛客网

目录

一.NC41 最长无重复子数组

题目详情:

题目思路:

解题代码:

二.NC379 重排字符串

题目详情:

题目思路:

解题代码:

结语

一.NC41 最长无重复子数组

牛客网题目链接(点击即可跳转):NC41 最长无重复子数组

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下:

哈希双指针滑动窗口, 图解如下:

解题代码:

本题解题代码如下:

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

二.NC379 重排字符串

牛客网题目链接(点击即可跳转):NC379 重排字符串

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下:

首先先统计所有字母出现的次数,如果有字母出现的次数大于(总数+1)/2,那么说明这个根本没法重排,所以直接返回"".统计好字母后,先排数量多的,把它们在双数下标间隔一个排列,然后双数下标排满了再把剩下的排在单数位置上,这样就可以保证不会出现相同的字母相邻的情况啦.解法算是一个小贪心,然后统计字母用到了数组存pair键值对的形式.(此处发现一个小tips:sort排pair数组的话会默认按first的值排升序,如果懒得现场手搓排序函数的可以把待排序的数据类型作为pair的first,这样可以省一点事).

解题代码:

本题解题代码如下:

class Solution 
{
public:string rearrangestring(string str) {vector<pair<int,char>> vp;string ret;ret.resize(str.size());for(int i=0;i<26;i++)vp.push_back(pair<int,char>{0,'a'+i});for(auto e:str)if(++vp[e-'a'].first > (str.size()/2))return ""; sort(vp.begin(),vp.end());int i=vp.size()-1, sin=0, even=1;while(sin<ret.size()){while(vp[i].first==0)i--;ret[sin]=vp[i].second;vp[i].first--;sin+=2;}while(even<ret.size()){while(vp[i].first==0)i--;ret[even]=vp[i].second;vp[i].first--;even+=2;}return ret;}
};