【C++】 —— 笔试刷题day_13

一、牛牛冲钻五

标题描述

标题说，牛牛在玩炉石传说，现在牛牛进行了n场游戏，让我们判断牛牛上了几颗星。
   首先输入一个T，表示T组数据；
  然后输入n和k，表示一个进行了n场数据，k表示连胜三场及以上得到的分数
  然我们输出末了的星数和起始星数的差；
  其中L表示失败，减一颗星；W表示胜利，如果连胜超过3场就得到k颗星，否则得到1可星。
  算法分析

这道题算是比力简单的，我们只需要模拟一下整个过程就好了；
   标题中是连胜超过3场，就得到k颗星；
  这里我们就要定义一个变量来记载连胜，当连胜场次超过3就得到k颗星；否则得到1颗星。
  代码实现

1. #include<iostream>
2. using namespace std;
4. int main()
5. {
6.     int T;
7.     cin>>T;
8.     while(T--)
9.     {
10.         int n,k;
11.         cin>>n>>k;
12.         int count = 0;
13.         int ret = 0;
14.         for(int i = 0;i<n;i++)
15.         {
16.             char ch;
17.             cin>>ch;
19.             if(ch == 'L')
20.             {
21.                 ret-=1;
22.                 count = 0;
23.             }
24.             else
25.             {
26.                 count++;
27.                 if(count>=3)
28.                     ret+=k;
29.                 else
30.                     ret+=1;
31.             }
32.         }
33.         cout<<ret<<endl;
34.     }
35.     return 0;
36. }

复制代码

二、最长无重复子数组

标题描述

   这道题，给定一个数组arr，让我们找到其中没有重复元素的最长子数组；返回这个最长子数组的长度。
  算法分析

看到这道题，了解过滑动窗口的可以说是一眼秒了，这种找子串题目。
现在我们先来看暴力解法：
   分别从0、1、…n位置向后遍历，寻找没有重复字符的子串；
  这里在寻找没有字符元素的子串时，我们需要记载区间内每一个元素出现的次数，那这里就要用到一个hash去记载。
  

我们看上图，当i在第一个位置找到没有重复元素的最长子数组时；
如果我们i++后，让j再从i位置开始向后遍历，如果i位置对应的元素不等于j位置对应的元素，那肯定还是走到和从0位置最长的那一个位置。
那这样我们就没有须要让j再从i位置向后遍历了，而是i++，直到i遍历过和j位置元素相称的那一个位置。
那这样我们还得窗口的主要思想就出来了：
   

• 入窗口：将right位置的元素放到hash表中。
  
• 出窗口：当区间[left , right]内出现了重复的元素，那就进行出窗口操纵，直到区间内没有重复的元素。
  
• 更新结果：出窗口操纵之后，区间[left , right]肯定是满足条件的，更新结果即可。
  

  代码实现

1. class Solution {
2. public:
3.     int hash[100001]={0};
4.     int maxLength(vector<int>& arr) {
5.         // write code here
6.         int ret = 0;
7.         int left = 0, right = 0;
8.         while(right<arr.size())
9.         {
10.             hash[arr[right]]++;
11.             while(hash[arr[right]] > 1)
12.             {
13.                 hash[arr[left]]--;
14.                 left++;
15.             }
16.             ret = max(ret,right - left+1);
17.             right++;
18.         }
19.         return ret;
20.     }
21. };

复制代码

三、重排字符串

标题描述

   标题给了我们一个字符串，然后让我们判断，这个字符串可否通过重新排列（只改变字母的顺序，不改变数目），让相邻的字母都不相同。
  如果不可以就输出no；如果可以，就输出yes，并输出其中一种排列方式。
  算法分析

这里这道题，标题描述很简单，但是我们会感觉到无从动手；
这个就直接说思路了，就是使用贪心
   我们先来看它们示例：aabbccc，它可以通过排列变成相邻字符都不相同的字符；
  这里，我们先来排列ccc，由于c出现的次数最多
  

观察上图，很显然，每隔一个位置，放置一个字符，这样那个放置一样的字符数最多（那我们就可以使用这一点来判断，是否能够通过排列构成相邻元素是否都不相同）
   什么意思呢？
  如果每隔一个位置，放置一个字符，这样如果我们出现次数最多的字符，如果它从第一个位置开始，每隔一个位置放置一个，直到末了，还有剩余，那肯定不能通过排列变成满足条件的字符串。
  如果还没到末了一个，次数最多的字符就放置完了，那其他的还是按照每隔一个位置放置一个，就肯定能够通过排列变成满足条件的字符串。
  我们在分析，当出现数目最多的字符，它出现的次数 > 给定字符串的长度+1的一半，那可以就不能通过排列来满足条件了。（这里就不叙述原因了，通过分析上述每隔一个位置放置一个字符，极端情况可以分析出来。
  那如果可以通过排列满足条件，那我们就要进行排列了。
   排列我们遵循的大体规则还是每隔一个位置，放置一个字符。
  这里我们需要先对出现此时最多的字符先进行放置，放置完再依次放置其他字符即可
  代码实现

1. #include <iostream>
2. #include <string>
3. using namespace std;
4. int main()
5. {
6.     int n;
7.     int cnt[26] = {0};
8.     cin>>n;
9.     int MaxCount = 0;
10.     char MaxChar = 0;
11.     for(int i=0;i<n;i++)
12.     {
13.         char ch = 0;
14.         cin>>ch;
15.         cnt[ch-'a']++;
16.         if(cnt[ch-'a'] > MaxCount)
17.         {
18.             MaxCount = cnt[ch-'a'];
19.             MaxChar = ch;
20.         }
21.     }
22.     if(MaxCount > (n+1)/2)
23.         cout<<"no"<<endl;
24.     else
25.     {
26.         cout<<"yes"<<endl;
27.         string ret(n,0);
28.         //先放置出现次数最多的字符
29.         int i =0;
30.         while(MaxCount--)
31.         {
32.             ret[i] = MaxChar;
33.             i+=2;
34.         }
35.         //放置其他字符
36.         for(int j = 0;j<26;j++)
37.         {
38.             if(j+'a' != MaxChar)
39.             {
40.                 while(cnt[j]--)
41.                 {
42.                     if(i>=n) i = 1;
43.                     ret[i] = j+'a';
44.                     i+=2;
45.                 }
46.             }
47.         }
48.         cout<<ret<<endl;
49.     }
50.     return 0;
51. }

复制代码

到这里，本日刷题就结束了
   简单总结：本日标题解决方法：模拟整个过程、滑动窗口、贪心。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。