250323拼多多后端暑期笔试
贴个Java代码
计算最终位置
模拟即可
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int t = in.nextInt();
while (t-- > 0) {
int x = in.nextInt(), y = in.nextInt();
String s = in.next();
for (char c : s.toCharArray()) {
if (c == 'W') y++;
else if (c == 'A') x--;
else if (c == 'S') y--;
else x++;
}
System.out.println(x == 0 && y == 0 ? "YES" : "NO");
}
}
}
}
计算区间内幸运数字的个数
如果一个数字的子串数字可以被3整除，那么就是幸运数字
其实只要计算小于100的非法数，因为3位数以及更多位数一定是幸运数字
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
// [8, 19]: 9 10 12 13 15 16 18 19
// 非法的数要么全是mod1组成，要么全是mod2组成，比如11 14 17 22 25 28
// 111也不行，个数还必须不能>=3，所以3位数xxx一定是幸运数字，比如11x一定是幸运数字
while (in.hasNextInt()) { // 注意 while 处理多个 case
int t = in.nextInt();
int[] valid = new int[100];
for (int i = 1; i < 100; i++) { // 判断[1, 99]的数字是否幸运
int x = i, pre = -1;
while (x > 0) {
int cur = x % 10;
if (cur % 3 == 0) valid[i] = 1; // 如果当前位，模三等于0，那么就是幸运
if (pre == -1) pre = cur % 3;
else if (cur % 3 != pre) valid[i] = 1; // 如果当前位模三 不等于 之前位模三，那么这两个位连起来就是幸运数字
x /= 10;
}
}
// System.out.println(Arrays.toString(valid));
int[] sum = new int[100];
for (int i = 1; i < 100; i++) { // 统计前缀和
sum[i] = sum[i-1] + valid[i];
}
while (t-- > 0) {
long l = in.nextLong(), r = in.nextLong();
long res = 0;
if (l >= 100) { // 如果L大于等于100，那么区间内肯定都是幸运数字
res = r - l + 1;
} else {
if (r >= 100) { // 如果L小于100，R大于等于100，那么给右边界缩小到99，然后用前缀和计算100以内的幸运数字个数
res += r - 99;
r = 99;
}
res += sum[(int)r] - sum[(int)(l-1)];
}
System.out.println(res);
}
}
}
}
计算可以看到右边的人的个数之和
可以用单调栈来获得每个元素的后上界
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
long[] nums = new long[n];
for (int i = 0; i < n; i++) nums[i] = in.nextLong();
long res = 0;
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
while(!stack.isEmpty() && nums[stack.peek()] <= nums[i]) { // 递增栈
res += i - stack.pop();
}
stack.push(i);
}
while (!stack.isEmpty()) { // 剩下的元素都可以看到右边所有人
res += n-1 - stack.pop();
}
System.out.println(res);
}
}
}
计算按照索引替换字符后的最小字典序字符串
主要是理解题意，给字符串b排序，然后贪心替换字符串a的对应索引字符
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
// 对于字符串a，有些字符会被替换不止一次，有些字符可能一次都不会被替换
// 我们只需要考虑被替换字符的最小字典序
while (in.hasNextInt()) { // 注意 while 处理多个 case
int t = in.nextInt();
while (t-- > 0) {
int n = in.nextInt(), m = in.nextInt();
String a = in.next(), b = in.next();
int[] nums = new int[m];
for (int i = 0; i < m; i++) nums[i] = in.nextInt();
TreeSet<Integer> set = new TreeSet<>(); // 用TreeSet保存可以替换的索引，相当于去重并排序
for (int x : nums) set.add(x);
char[] cs = b.toCharArray();
Arrays.sort(cs);
char[] res = a.toCharArray();
int idx = 0;
for (int key : set) { // 贪心替换字符串a
res[key-1] = cs[idx++];
}
System.out.println(String.valueOf(res));
}
}
}
}
