今日学习📃
🎋1、巧拼扑克牌
🎃2、质数拆分
🖼️3、日志统计
🎄4、递增三元组
🎍5、外卖店优先级
🎋1、巧拼扑克牌
🎯题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小明刚上小学，学会了第一个扑克牌“魔术”，到处给人表演。魔术的内容是这样的：
他手里握着一叠扑克牌：A，2，....J，Q，K一共 13 张。他先自己精心设计它们的顺序，然后正面朝下拿着，开始表演。
只见他先从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是 A；然后再从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是 2；......如此循环直到手中只有一张牌，翻开放桌子上，刚好是 K。
这时，桌上牌的顺序是：A,2,3,4,5,6,7,8,9,10,J,Q,K。
请你计算一下，小明最开始的时候手里牌的顺序是怎样的。
把结果写出来，逗号分割，小明“魔术”开始时，最下面的那张牌输出为第一个数据。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
-
package Day_Day_work;
-
-
/**
-
* @author yx
-
* @date 2022-03-13 10:17
-
*/
-
-
public
class 巧排扑克牌 {
-
// 1:输出是逗号+空格
-
public
static
void main(
String[] args) {
-
System.out.
print(
"7, A, Q, 2, 8, 3, J, 4, 9, 5, K, 6, 10");
-
}
-
}
🎪题解分析：
💦1、第一题没啥好说的，自己花几分钟手撸一下，然后在花几分钟验证一下即可
💦2、实在不济，自己模拟一下题目，做个小手工，一张一张自己实现一下这个过程即可
🎃2、质数拆分
🎯题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 2 + 2017 = 2019 与 2017 + 2 = 2019视为同一种方法。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
-
package Day_Day_work.problem;
-
/**
-
* @author yx
-
* @date 2022-03-13 10:52
-
*/
-
public
class 质数拆分__01背包问题 {
-
static
long[] a=
new
long[
2020];
-
static
int[] p=
new
int[
2020];
-
public static void main(String[] args) {
-
a[
0]=
1;
-
int n=
1;
-
for(
int i=
1;i<
2019;i++)
-
{
-
if(
pd(i))
-
{
-
p[n++]=i;
-
}
-
}
-
/**
-
* 下面是01动规核心代码
-
*/
-
for(
int i=
1;i<=n
-1;i++) {
-
for(
int j=
2019;j>=p[i];j--) {
-
a[j] += a[j-p[i]];
-
}
-
}
-
System.out.
println(a[
2019]);
-
}
-
-
static boolean pd(int x) {
//质数判断
-
if(x==
1)
-
{
-
return
false;
-
}
-
for(
int i=
2;i<=(
int) Math.
sqrt(x);i++)
-
{
-
if(x%i==
0)
-
{
-
return
false;
-
}
-
}
-
return
true;
-
}
-
}
🎪题解分析：
💦1、这个题目很容易理解错误，是若干两两不同的组成，而不是两个组成（博主踩过的坑）
💦2、将题目拆分成两个部分：质数判断、背包组合
难点分析：
💦1、能看出题目背后的本质，其实就是背包问题
💦2、熟练01背包问题
💦3、能快速写出质数判断的方法（暴力方法就可）
🖼️3、日志统计
🎯题目描述
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有 N 行。其中每一行的格式是：ts id
表示在 ts 时刻编号 id 的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D)这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
输入描述
输入格式：
第一行包含三个整数 N,D,K
以下 N 行每行一条日志，包含两个整数 ts 和 id。
其中，10^51≤K≤N≤105,0≤ts≤105,0≤id≤105。
输出描述
按从小到大的顺序输出热帖 id。
每个 id 一行。
输入输出样例
示例
输入
输出
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
-
package Day_Day_work;
-
-
import java.util.*;
-
-
/**
-
* @author yx
-
* @date 2022-03-13 15:19
-
*/
-
public
class 日志统计__尺取法 {
-
static
class R{
-
int ts;
//时刻
-
int td;
//id
-
}
-
-
public
static
void main(
String[] args) {
-
Scanner scanner =
new Scanner(System.in);
-
int N=scanner.nextInt(),D=scanner.nextInt(),K=scanner.nextInt();
-
R[] rs=
new R[N];
-
for (
int i =
0; i < N; i++) {
-
R r=
new R();
-
r.ts=scanner.nextInt();
-
r.td=scanner.nextInt();
-
rs[i]=r;
-
}
-
//匿名内部类定义排序器
-
Arrays.sort(rs,
new Comparator<R>() {
-
@Override
-
public
int compare(R o1, R o2) {
-
return o1.ts-o2.ts;
//表示按时刻的升序来排列
-
}
-
});
-
//用于给id计点赞数
-
Map<
Integer,
Integer> cnt=
new HashMap<>();
-
//用于存储答案，TreeSet自动对集合中的元素进行升序排序
-
SortedSet<
Integer> answer=
new TreeSet<
Integer>();
-
/*
-
尺取法
-
*/
-
int j=
0;
-
for (
int i =
0; i < N; i++) {
-
while (j<N&&rs[j].ts-rs[i].ts<D){
//左闭右开,时间区间不能超过D
-
int td=rs[j].td;
-
Integer exist=cnt.get(td);
-
if(exist!=
null){
//不为空的情况下
-
cnt.put(td,exist+
1);
//该id的点赞次数+1
-
}
else {
//最开始的情况
-
cnt.put(td,
1);
//该id第一次出现，直接给赋值为1
-
}
-
if(cnt.get(td)>=K){
//当点赞次数超过K时加入到answer集合中
-
answer.add(td);
-
}
-
j++;
//往后继续取区间
-
}
-
//退出while循环后，i往后移动会+1，则当前的i的点赞数-1，因为后面的区间最小值为i+1
-
//不包括i，将该id下的点赞数-1
-
Integer c=cnt.get(rs[i].td);
//获取该id下的点赞数
-
if(c!=
null){
-
cnt.put(rs[i].td,c-
1);
//更新点赞数
-
}
-
}
-
for (
Integer i:answer) {
-
System.out.println(i);
-
}
-
}
-
}
🎪题解分析：
💦1、该题采用尺取法，区间间隔移动，统计在D时间区间内每个id的获赞数
💦2、使用类绑定时刻和id
难点分析：
💦1、匿名内部类自定义排序器（定义了一个类来绑定时刻和id，所以要重写一下排序方法）
💦2、熟练使用HashMap和TreeSet
💦3、熟练使用尺取法
🎄4、递增三元组
🎯资源限制
时间限制：1.0s 内存限制：256.0MB
给定三个整数数组
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN]，
请你统计有多少个三元组(i, j, k) 满足：
1. 1 <= i, j, k <= N
2. Ai < Bj < Ck输入格式
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
第三行包含N个整数B1, B2, ... BN。
第四行包含N个整数C1, C2, ... CN。
对于30%的数据，1 <= N <= 100
对于60%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000输出格式
一个整数表示答案
样例输入
3
1 1 1
2 2 2
3 3 3样例输出
27
-
package Day_Day_work;
-
-
import java.util.Arrays;
-
import java.util.Scanner;
-
-
/**
-
* @author yx
-
* @date 2022-03-13 16:02
-
*/
-
public class 递增三元组 {
-
public
static
void
main
(String[] args) {
-
Scanner
scanner
=
new
Scanner(System.in);
-
int
N
= scanner.nextInt();
-
int A[] =
new
int[N];
-
int B[] =
new
int[N];
-
int C[] =
new
int[N];
-
for (
int
i
=
0; i < N; i++) {
-
A[i] = scanner.nextInt();
-
}
-
for (
int
i
=
0; i < N; i++) {
-
B[i] = scanner.nextInt();
-
}
-
for (
int
i
=
0; i < N; i++) {
-
C[i] = scanner.nextInt();
-
}
-
//计数
-
int
a
=
0;
-
int
b
=
0;
-
int
c
=
0;
-
//升序排列
-
Arrays.sort(A);
-
Arrays.sort(B);
-
Arrays.sort(C);
-
int
j
=
0;
-
int
k
=
0;
-
long ans=
0;
-
for (
int
i
=
0; i < N; i++) {
-
while (j<N&&A[j]<B[i])j++;
-
while (k<N&&C[k]<=B[i])k++;
-
ans+=(
long) (N-k)*j;
-
}
-
System.out.println(ans);
-
}
-
}
🎪题解分析：
💦1、先将A、B、C三个数组进行升序排序
💦2、以B数组为突破点，从左往右遍历A数组定位小于B[i]的A元素有j个
💦3、以B数组为突破点，从左往右遍历C数组定位小于等于B[i]的C元素有k个
💦4、那么该轮一共有（j）*（n-k）个三元组
💦5、按照该思路从左往右遍历B数组，累加每一轮的三元组数量
🎍5、外卖店优先级
🎯题目描述
"饱了么"外卖系统中维护着 NN 家外卖店，编号 1 ∼ NN。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。
给定 TT 时刻以内的 MM 条订单信息，请你计算 TT 时刻时有多少外卖店在优 先缓存中?
输入描述
第一行包含 3 个整数 N,M,TN,M,T。
以下 MM 行每行包含两个整数 ts,idts,id，表示 tsts 时刻编号 idid 的外卖店收到一个订单。
其中，1 \leq N,M,T \leq 10^5，1 \leq ts \leq T，1 \leq id \leq N1≤N,M,T≤105，1≤ts≤T，1≤id≤N。
输出描述
输出一个整数代表答案。
输入输出样例
示例
输入
输出
1样例解释：
6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。
运行限制
- 最大运行时间：2s
- 最大运行内存: 256M
-
package Day_Day_work;
-
import java.util.Scanner;
-
-
/**
-
* @author yx
-
* @date 2022-03-13 19:42
-
*/
-
/*
-
仔细读题：
-
1、优先级最低减到 0
-
2、优先级大于 5，则会被系统加入优先缓存（进入优先缓存后还有可能被移除）
-
-
思路：
-
1、先模拟，再全部遍历
-
*/
-
public class 外卖店优先__暴力模拟 {
-
public
static
void
main
(String[] args) {
-
Scanner
scanner
=
new
Scanner(System.in);
-
int N=scanner.nextInt();
//M行数据输入
-
int M=scanner.nextInt();
//N家店
-
int T=scanner.nextInt();
//给定的一个时刻
-
int A[][]=
new
int[N][T];
-
int ans=
0;
//计数
-
for (
int
i
=
0; i < M; i++) {
-
int ts=scanner.nextInt();
//输入时刻
-
int id=scanner.nextInt();
//输入店的id
-
A[id-
1][ts-
1]+=
1;
//表示这家店来了一个订单
-
}
-
for (
int
i
=
0; i < N; i++) {
//对每一家店做处理
-
int level=
0;
//优先级
-
boolean k=
false;
//是否能够加入优先缓存
-
for (
int i1=
0;i1<T;i1++){
-
if(A[i][i1]==
0){
//表示没有订单
-
level-=
1;
-
if(level<
0){
-
level=
0;
-
}
-
if (level<=
3){
-
k=
false;
-
}
-
}
else {
-
level+=(
2*A[i][i1]);
-
if(level>
5){
-
k=
true;
-
}
-
}
-
}
-
if(k){
-
ans++;
-
}
-
}
-
System.out.println(ans);
-
}
-
}
🎪题解分析：
💦1、本题解为暴力方法，性价比最高
💦2、定义一个二维数组，行数表示店的数量，列数表示一共有多少个时刻
💦3、先将所有数据存入二维数组
💦4、遍历每一家店
难点分析：
💦1、优先级最低减到 0，就不会再减了
💦2、优先级大于 5，则会被系统加入优先缓存（但是进入优先缓存后还有可能被移除）
💦3、先模拟，再全部遍历
💖写在最后
每日一题，我们一直在路上，这次的题目有点小难度，比较有挑战性
也充分认识到了自己的不足，比如说在动规背包问题上的薄弱，博主接下来将有针对性地加强训练
“心若有所向往，何惧道阻且长，各位有志青年，一起加油 ！”
欢迎一起交流讨论！
转载：https://blog.csdn.net/m0_55858611/article/details/123470753