大家好,我是LvZi,今天带来
笔试狂刷--Day13(模拟 + 贪心 + 滑动窗口)
一.⽜⽜冲钻五(模拟)
题目链接:⽜⽜冲钻五(模拟)
分析:
模拟
代码:
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
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 < n; i++) {
if(s[i] == 'W') {
if(i - 1 >= 0 && i - 2 >= 0 && s[i - 1] == 'W' && s[i - 2] == 'W') ret += k;
else ret += 1;
}else {
ret--;
}
}
System.out.println(ret);
}
}
}
二.最⻓⽆重复⼦数组
题目链接:最⻓⽆重复⼦数组
分析:
滑动窗口
代码:
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
// write code here
int ret = 0, n = arr.length;
int[] cnt = new int[100000];
for(int l = 0, r = 0; r < n; r++) {
cnt[arr[r]]++;
while(cnt[arr[r]] > 1) {
cnt[arr[l++]]--;
}
ret = Math.max(ret, r - l + 1);
}
return ret;
}
}
三.重排字符串(较难)
题目链接:重排字符串
分析:
贪心
选择最优的放置字符的策略
- 先把出现次数最多的字符
隔着放完
- 再处理剩下的字符
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
char[] s = in.next().toCharArray();
int[] hash = new int[26];
int maxCnt = 0;
char maxChar = '0';
// 得到字符数量最多的字符和其对应的数量
for(int i = 0; i < n; i++) {
if(++hash[s[i] - 'a'] > maxCnt) {
maxCnt = hash[s[i] - 'a'];
maxChar = s[i];
}
}
if(maxCnt > (n + 1)/2) {
System.out.println("no");
return;
}
System.out.println("yes");
// 进行重排
int i = 0;// 下标
char[] ret = new char[n];
while(maxCnt-- > 0) {
ret[i] = maxChar;
i += 2;
}
// 处理剩下的字符
for(int k = 0; k < 26; k++) {
if(hash[k] != 0 && (char)(k + 'a') != maxChar) {
while(hash[k]-- > 0) {
if(i >= n) i = 1;
ret[i] = (char)(k + 'a');
i += 2;
}
}
}
System.out.print(new String(ret));
}
}
总结:
- 本题的核心还是在于想到贪心的策略
先处理出现次数最多的字符,处理的方式为间隔一个位置重排字符
,有点类似于小学奥数题目,实际上是感性的尝试最优策略