目录

⽜⽜冲钻五（模拟）

题目解析

讲解算法原理

编写代码

最⻓⽆重复⼦数组（滑动窗⼝）

题目解析

讲解算法原理

编写代码

---

⽜⽜冲钻五（模拟）

题目解析

1.题目链接：登录—专业IT笔试面试备考平台_牛客网

2.题目描述

题目描述

牛牛最近在玩炉石传说，这是一款一对一对战的卡牌游戏，牛牛打算努力冲上钻五分段，获得丰厚的天梯奖励。

炉石传说的段位可以用星数来表示，具体规则为：若牛牛本场失败，则扣除一星；若牛牛本场获胜，需要看牛牛是否触发了连胜奖励，若牛牛获得了至少三连胜（即本局对局的上一局和上上局都获胜）则获得kkk星，否则获得一星。

现在给出牛牛游玩的nnn场记录，请你判断牛牛最终的星数和初始星数的差。

输入描述:

第一行输入一个整数T(1≤T≤104)T(1\leq T\leq 10^4)T(1≤T≤104)，测试组数。

每个测试的第一行输入两个整数n(3≤n≤105)n(3\leq n\leq 10^5)n(3≤n≤105)和k(2≤k≤100)k(2\leq k \leq 100)k(2≤k≤100)，牛牛共打了几场比赛与连胜奖励的星数。

接下来一行输入一个长为nnn的字符串，之中WWW表示获胜，LLL表示失败，保证只含有这两种字母。

保证所有用例的Σn≤105\Sigma n\leq 10^5Σn≤105。

输出描述:

对每个测试用例，输出一个整数，表示牛牛最终的星数和初始星数的差。

示例1

输入

2 5 3 WWWLW 5 3 WLLLL

2
5 3
WWWLW
5 3
WLLLL

输出

5 -3

5
-3

讲解算法原理

解法：
算法思路：
简单模拟题，属于每次笔试的热⾝题~

编写代码

c++算法代码：

#include <iostream>
#include <string>
using namespace std;
int t, n, k;
string s;
int fun()
{
 int ret = 0;
 for(int i = 0; i < s.size(); i++)
 {
 if(s[i] == 'L')
 {
 ret--;
 }
 else
 {
 if(i - 1 >= 0 && i - 2 >= 0 && s[i - 1] == 'W' && s[i - 2] == 'W')
 {
 ret += k;
 }
 else
 {
 ret += 1;
 }
 }
 }
 return ret;
}
int main()
{
 cin >> t;
 while(t--)
 {
 cin >> n >> k >> s; cout << fun() << endl; }
 
 return 0;
}

java算法代码：

import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
 Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- != 0)
 {
 int n = in.nextInt(); int k = in.nextInt(); char[] s = in.next().toCharArray();  int ret = 0; for(int i = 0; i < s.length; i++) { if(s[i] == 'L') ret -= 1; else
 {
 if(i - 1 >= 0 && i - 2 >= 0 && s[i - 1] == 'W' && s[i - 2] 
== 'W')
 { ret += k; } else { ret += 1; } } }
 System.out.println(ret);
 }
 }
}

 

最⻓⽆重复⼦数组（滑动窗⼝）

题目解析

1.题目链接：最长无重复子数组_牛客题霸_牛客网

2.题目描述

描述

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

数据范围：0\le arr.length \le 10^50≤arr.length≤105，0 < arr[i] \le 10^50<arr[i]≤105

示例1

输入：

[2,3,4,5]

返回值：

4

说明：

[2,3,4,5]是最长子数组        

示例2

输入：

[2,2,3,4,3]

返回值：

3

说明：

[2,3,4]是最长子数组        

示例3

输入：

[9]

返回值：

1

示例4

输入：

[1,2,3,1,2,3,2,2]

返回值：

3

说明：

最长子数组为[1,2,3]       

示例5

输入：

[2,2,3,4,8,99,3]

返回值：

5

说明：

最长子数组为[2,3,4,8,99]     

讲解算法原理

解法：
算法思路：
经典滑动窗⼝题⽬。

编写代码

c++算法代码：

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

java算法代码：

import java.util.*;
public class Solution
{
 public int maxLength (int[] arr) 
 {
 int[] hash = new int[100010]; int left = 0, right = 0, n = arr.length; int ret = 0; while(right < n)
 {
 hash[arr[right]]++; // 进窗⼝
 while(hash[arr[right]] > 1) // 判断 {
 // 出窗⼝
 hash[arr[left]]--; left++;
 }
 ret = Math.max(ret, right - left + 1); // 更新结果 right++; }
 return ret;
 }
}