恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝
第一道：模拟（100%）
根据x，y和r的相对大小分成九种情况。需要注意一下
{x^2} + {y^2} = {r^2} 和 x0，y0的特殊情况。
import java.util.*;
public class Solution1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
int x, y, r;
x = scanner.nextInt();
y = scanner.nextInt();
r = scanner.nextInt();
int cnt = 0;
x = x < 0 ? -x : x;
y = y < 0 ? -y : y;
if (r < y) {
if (r > x) {
cnt += 2;
} else if (r < x) {
cnt += 0;
} else {
cnt += 1;
}
} else if (r > y) {
if (r > x) {
if (r*r == x*x + y*y) {
cnt += 3;
} else {
cnt += 4;
}
} else if (r < x) {
cnt += 2;
} else {
if (y == 0) {
cnt += 2;
} else {
cnt += 3;
}
}
} else {
if (r > x) {
if (x == 0) {
cnt += 2;
} else {
cnt += 3;
}
} else if (r < x) {
cnt += 1;
} else {
cnt += 2;
}
}
System.out.println(cnt);
}
}
}
第二道： 糖果甜度（100%）
滑动窗口求最大值，用滑动窗口，设定快慢指针，遇到含糖量过高的就把快慢指针放到此位置重新开始。历一遍数组有甜度大于t的就记录下标，如果两个大于t的下标之间的距离d大于c，就可以有d-c+1种，然后每两个下标算一次加起来就行了
import java.util.*;
public class Solution2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int t = scanner.nextInt();
int c = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i ++) {
a[i] = scanner.nextInt();
}
int[] res = maxWindow(a, c);
int cnt = 0;
for (int i = 0; i < res.length; i ++) {
if (res[i] <= t) {
cnt ++;
}
}
System.out.println(cnt);
}
private static int[] maxWindow(int[] nums, int k) {
if (nums == null || nums.length < 2) {
return nums;
}
LinkedList<Integer> linkedList = new LinkedList<>();
int[] result = new int[nums.length-k+1];
for (int i = 0; i < nums.length; i ++) {
while (!linkedList.isEmpty() && nums[linkedList.peekLast()] <= nums[i]) {
linkedList.pollLast();
}
linkedList.add(i);
if (linkedList.peek() <= i-k) {
linkedList.poll();
}
if (i-k+1 >= 0) {
result[i-k+1] = nums[linkedList.peek()];
}
}
return result;
}
}
第三道（100%）
整体思想是把光标前和光标后分两个部分来存，每一部分都用set维护。
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
char s[N];
multiset<int> ms1, ms2;
vector<int> a1, a2, s1, s2;
int main() {
int n;
scanf("%d%s", &n, s+1);
int add = 0, tot = 0;
for(int i=1; i<=n; i++) {
if(s[i]=='L') {
if(a1.size()) {
int x = a1.back();
a1.pop_back();
a2.push_back(x);
ms1.erase(ms1.find(s1.back()));
s1.pop_back();
ms2.insert(-add);
s2.push_back(-add);
add += x;
}
}
else if(s[i]=='R') {
if(a2.size()) {
int x = a2.back();
a2.pop_back();
a1.push_back(x);
int sum = s2.back();
s2.pop_back();
ms2.erase(ms2.find(sum));
int y = 0;
if(s1.size())
y = s1.back();
s1.push_back(y+x);
ms1.insert(y+x);
add -= x;
}
}
else if(s[i]=='D') {
if(a1.size()) {
int x = a1.back();
a1.pop_back();
ms1.erase(ms1.find(s1.back()));
s1.pop_back();
tot -= x;
}
}
else if(s[i]=='(') {
int sum = 0;
if(s1.size())
sum = s1.back();
a1.push_back(1);
s1.push_back(sum+1);
ms1.insert(sum+1);
tot++;
}
else {
int sum = s1.back();
a1.push_back(-1);
s1.push_back(sum-1);
ms1.insert(sum-1);
tot--;
}
int mn = 0;
if(ms1.size())
mn = min(mn, *ms1.begin());
if(ms2.size()) {
int sum = 0;
if(s1.size())
sum = s1.back();
mn = min(mn, sum+(*ms2.begin())+add);
}
if(mn<0 || tot!=0) {
int ans = 0;
if(mn<0)
ans += -mn;
ans += tot+ans;
printf("-%d", ans);
}
else {
int mx = 0;
if(ms1.size())
mx = max(mx, *(--ms1.end()));
if(ms2.size()) {
int sum = 0;
if(s1.size())
sum = s1.back();
mx = max(mx, sum+(*(--ms2.end()))+add);
}
printf("%d", mx);
}
if(i<n)
printf(" ");
}
printf("\n");
return 0;
}
第四道： 动态规划（100%）
dp[i]表示nums[0:i]这个子数组可以形成的合法排列种数。然后dp[i+1]即把nums[i+1]插到前面排列的某一位置，不同的插入点即是(i - dp2[i] + 1)
一种思路：计算放入第i个数能有多少个集合的时候，前面i-1个数已经生成了n个解，那么加入第i个数，我们考虑这第i个数可以放在原先集合里的解中的哪些数的前面，可以放在m个数前面就有mn个解，再加上可以放在所有解的后面所以一共就是n(m+1)个解
public class Q4 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] strings = scanner.nextLine().split(" ");
int n = Integer.valueOf(strings[0]);
int m = Integer.valueOf(strings[1]);
String[] s = scanner.nextLine().split(" ");
int[] num = new int[n];
for(int i = 0;i < n;i++){
num[i] = Integer.valueOf(s[i]);
}
System.out.println(count(num, m));
}
public static int count(int[] nums,int m){
int mod = 1000000007;
int n = nums.length;
Arrays.sort(nums);
long[] dp = new long[n];
dp[0] = 1;
int[] dp2 = new int[n];
for(int left = 0, right = 0;right < n;right++){
if(nums[right] - nums[left] <= m){
dp2[right] = left;
}else{
while(left < right && nums[right] - nums[left] > m){
left++;
}
dp2[right] = left;
}
}
for(int i = 1;i < n;i++){
dp[i] = dp[i - 1] * (i - dp2[i] + 1) % mod;
}
return (int)dp[n - 1];
}
|