1、拿硬币
题目描述
有n个硬币排成一排，每次要你从最左边或者最右侧拿出一个硬币。总共拿k次，写一个算法，使能拿到的硬币的和最大。
输入描述：
第一行为一个数组（可能包含负数），数组中每个值代表硬币的价值
第二行为能拿几次
输出描述：
拿到的最大的硬币和
分析设计
这是典型的滑窗问题，有两种思路，一个是直接求最大的和，另一个是用总和减去最小的和。
求最大的和，需要把数组进行二倍扩展，然后下边从n-k到n+k，从这里取连续的k个数使得和最大；
求最大的和，无需改变数组，下标从0到n，从这里取连续的n-k个数使得和最小，然后用数组总和减去该最小和即可。
代码实现
import java.util.*;
public class Main{
public static void main(String[] args){
int mod = 1000000007;
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int len = str.length();
String[] s = str.substring(1, len - 1).split(",");
int n = s.length;
int[] nums = new int[n * 2];
for(int i = 0; i < n; ++i){
nums[i] = Integer.parseInt(s[i]);
nums[i + n] = nums[i];
}
int k = sc.nextInt();
long maxSum = Long.MIN_VALUE;
int l = n - k, r = n - k;
long sum = 0;
while(r < n + k){
sum += nums[r];
while(r - l + 1 > k){
sum -= nums[l];
l++;
}
if(r - l + 1 == k){
maxSum = Math.max(maxSum, sum);
}
r++;
}
System.out.println(maxSum);
}
}2、开宝箱
题目描述
有n个宝箱, 打开宝箱会获得buff或者debuff, 数组b的每个元素代表打开每个宝箱会获得的正向或反向收益, 现在知道每个宝箱里的buff和debuff值, 需要依次打开宝箱, 每打开一个宝箱, 都会获得相应的收益, 我们根据相邻宝箱收益差定义稳定性v[b]
你可以修改b数组中的元素, 最多修改k次(可以把元素指修改为任意值), 需要使得v[b]尽可能小
输入描述：
输入为两行, 第一行包括n和k两个整数(1<=k<=n<=2000), 第二行包括n个整数b1,b2,...,bn(-10^9<=bi<=10^9)
数字间两两有空格隔开
输出描述：
一个整数代表最小的v[b]值
分析设计
求助：哪位大佬帮忙解决一下？
3、最大会议
题目描述
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
输入描述：
一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi
输出描述：
可以参加的 最大 会议数目
分析设计
贪心的思想，由于每个时间点最多参加一个会议，我们可以从1开始遍历所有时间。
对于每一个时间点，所有在当前时间及之前时间开始，并且在当前时间还未结束的会议都是可参加的。显然，在所有可参加的会议中，选择结束时间最早的会议是最优的，因为其他会议还有更多的机会可以去参加。
怎样动态获得当前结束时间最早的会议呢？我们可以使用一个小根堆记录所有当前可参加会议的结束时间。在每一个时间点，我们首先将当前时间点开始的会议加入小根堆，再把当前已经结束的会议移除出小根堆（因为已经无法参加了），然后从剩下的会议中选择一个结束时间最早的去参加。
代码实现
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int len = str.length();
String[] s = str.substring(1, len - 1).split(",");
int n = s.length / 2;
int[][] event = new int[n][2];
for(int i = 0; i < n * 2; i += 2){
event[i / 2][0] = Integer.parseInt(s[i].replace("[", ""));
event[i / 2][1] = Integer.parseInt(s[i + 1].replace("]", ""));
}
Arrays.sort(event, (o1, o2) -> o1[0] - o2[0]);
PriorityQueue<Integer> pq = new PriorityQueue<>();
int ans = 0;
int last = 1, i = 0;
while(i < n || !pq.isEmpty()){
while(i < n && event[i][0] == last){
pq.offer(event[i++][1]);
}
while(!pq.isEmpty() && pq.peek() < last){
pq.poll();
}
if(!pq.isEmpty()){
pq.poll();
ans++;
}
last++;
}
System.out.println(ans);
}
}