9.1 拼多多寻梦计划笔试题复盘
刷题少，考得不好，痛定思痛，参考了评论区很多大佬的解答贴，复盘整理出来。
第1道
读入一个数列和N值，返回按优先级排序的N个数，满足 （1）所有偶数优先级大于奇数 （2）同为偶数或同为奇数时，数值大的优先级高
输入描述：
每个测试输入的测试用例，包含一个用半角逗号（,）分开的自然数数列和1个参数N，数列和参数N用半角分号（;）隔开这里保证N小于数列的元素个数（不超过100）。
输出描述：
在一行内输出N个满足题目条件的自然数，用逗号隔开
示例1
输入：
555503,772867,756893,339138,399447,40662,859037,628085,855723,974471,599631,636153,581541,174761,948135,411485,554033,858627,402833,546467,574367,360461,566480,755523,222921,164287,420256,40043,977167,543295,944841,917125,331763,188173,353275,175757,950417,284578,617621,546561,913416,258741,260569,630583,252845;10
输出：
913416,566480,420256,339138,284578,40662,977167,974471,950417,948135
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
String line = sc.next();
String[] split = line.split(";");
int N = Integer.valueOf(split[1]);
String[] nums = split[0].split(",");
List<Long> nums_1 = new ArrayList<>();
List<Long> nums_2 = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
long t = Long.valueOf(nums[i]);
if (t % 2 == 0) {
nums_2.add(t);
} else {
nums_1.add(t);
}
}
Collections.sort(nums_1, Collections.reverseOrder());
Collections.sort(nums_2, Collections.reverseOrder());
List<Long> res = new ArrayList<>(N);
for (int i = 0; i < Math.min(nums_2.size(), N); i++) {
res.add(nums_2.get(i));
}
if (res.size() < N) {
for (int i = res.size(), j = 0; i < N; i++, j++) {
res.add(nums_1.get(j));
}
}
for (int i = 0; i < N; i++) {
if (i == 0)
System.out.print(res.get(i));
else
System.out.print("," + res.get(i));
}
}
} 第2道
产品经理小梅喜欢和他的男朋友小白一块玩扑克游戏。每一局，小梅抽取N张扑克牌，自左向右依次排列在桌面上；小白也抽取M（8>=N>=M>=1）张扑克牌，自左向右依次排列在桌面上。 小梅需要进行N个回合，使用手中的扑克牌，组成一个新的扑克牌的序列每个回合，小梅有d、l、r三种策略 选择d时，小梅将最左边的扑克牌丢弃 选择l时，小梅将最左边的扑克牌取出，放到新的扑克牌序列的最左边 选择r时，小梅将最左边的扑克牌取出，放到的扑克牌序列的最右边 N个回合完成，新的扑克牌序列与小白的扑克牌完全样（只考虑数字，不考虑花色），则小梅胜出 小梅向程序员小岛提了一个需求，希望了解获胜的全部方法。简化起见扑克牌仅包合1-9。
输入描述：
首先，输入数字S，作为局数（1<=10）每一局，分别输入两行字符串，分别代表小梅的抽取的扑克牌（从左向右排列）和小白抽取到的扑克牌（从左向右排列）
输出描述：
对于每一局，在开始和结束，分别输出{和}输出获胜的方法，回合策略的结尾输出一个空格。若存在多个获胜方法，请按字典序的升序输出。 示例1
输入：
3 123 3 123 321 45 67
输出：
{
d d l
d d r
}
{
l l l
r l l
}
{
} 暴力搜索可破。
import java.util.*;
public class Main {
static List<String> res;
static Queue<String> road;
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int S = sc.nextInt();
for (int i = 0; i < S; i++) {
String nums1 = sc.next();
String nums2 = sc.next();
res = new ArrayList<>();
road = new ArrayDeque<>();
find(nums1, "", nums2);
printResult(res);
}
}
private static void find(String origin, String now, String target) {
if (target.equals(now)) {
if (origin.length() >= 0) {
for (int i = 0; i < origin.length(); i++) {
road.offer("d");
}
}
res.add(String.join(" ",road));
return;
}
if (origin == null || origin.length() == 0) {
return;
}
String left = String.valueOf(origin.charAt(0));
String norigin = origin.substring(1);
road.offer("d");
find(norigin, now, target);
road.poll();
road.offer("l");
find(norigin, left + now, target);
road.poll();
road.offer("r");
find(norigin, now + left, target);
road.poll();
}
private static void printResult(List<String> res) {
System.out.println("{");
if (res == null || res.size() == 0) {
System.out.println("}");
return;
} else {
Collections.sort(res, (o1, o2) -> o1.compareTo(o2));
for (int i = 0; i < res.size(); i++) {
String s = res.get(i);
System.out.println(String.join(" ", s));
}
}
System.out.println("}");
}
} 第3道
扔n个般子，第i个骰子有可能投掷出Xi种等概率的不同的结果，数字从1到Xi。所有般子的结果的最大值将作为最终结果。求最终结果的期望。
输入描述：
第一行一个整数n，表示有n个骰子。（1<=n<=50） 第二行n个整数，表示每个骰子的结果数xi。（2<=Xi<=50）
输出描述：
输出最终结果的期望，保留两位小数
示例1
输入：
2 2 2
输出：
1.75
这道计算题的技巧是，如计算f(3)，将f(2)、f(1)的概率也囊括了进来，从整体上再将先前计算的f(2)、f(1)减去。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class Main {
static HashMap<Integer, Long> map;
static int n;
static int[] a;
static double[] p;
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
p = new double[a[a.length - 1] + 1];
int begin = 0;
for (int max = 1; max <= a[a.length - 1]; max++) {
while (a[begin] < max)
begin ++;
double p_max = 1.0;
for (int i = begin; i < n; i++) {
p_max *= max / (double)a[i];
}
p_max -= Arrays.stream(p).sum();
p[max] = p_max;
}
double EX = 0;
for (int X = 1; X <= a[a.length - 1]; X++) {
EX += X * p[X];
}
System.out.printf("%.2f",EX);
}
} 第4道
在一块长为n，宽为m的场地上，有n X m个1 X 1的单元格。每个单元格上的数字就是按照从1到n和1到m中的数的乘积。具体如下： n = 3, m = 3 1 2 3 2 4 6 3 6 9 给出一个查询的值K，求出按照这个方式列举的的数中第k大的值v例如上面的例子里，从大到小为（9，6，6，4，3，3，2，2，1） k=1,v=9 K=2,v=6 K=3,v=6 ... k=8,v=2 k=9,V=1
输入描述：
只有一行是3个数n，m，k表示场地的宽高和需要查询的k。使用空格隔开
输出描述：
给出第k大的数的值。
示例1
输入：
3 3 4
输出：
4
备注：
【数据范围】 100%的效据 1 <= n，m <= 40000 1 <= k <= n*m 30%的数据 1 <= n, m <= 1000
原是LeetCode改编，668. 乘法表中第k小的数
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int low = 1, high = m * n;
while (low < high) {
int mid = (low + high) / 2;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += (mid / i > m) ? 0 : m - mid / i;
}
if (cnt < k) high = mid;
else low = mid + 1;
}
System.out.println(low);
}
} 
