微众银行9.13笔试+复盘
先说下自己的笔试情况：0.81 + 0.91 + 0.18
1. 拼接数字，有两种方法可以做，第一种是类似全排列的解法，只不过要把每次收集的上限改为3。我笔试中使用这个方法只过了81%，原因是没有加base case，题目中给了N张卡片， N的范围是1 <= N <= 100000。加上特殊判断条件应该就可以ac了。
第二种方法是，先将卡片上的数字按照长度排列，然后长度一样的话，按照字典序排序。需要注意的是，取出前三个数字以后，还需要特殊处理。比如取出56，561，3。
不能单纯按照字典序排列，否则就是561563，但是565613才是最优解。所以需要两两相加比较，比如o1:56, o2:561 (o2+o1).compareTo(o1+o2) ,56就到了前面。
public class Main {
static long ans = Long.MIN_VALUE;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
long[] arr = new long[N];
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextLong();
}
// base case
if (N == 0) {
System.out.println(0);
return;
} else if (N == 1) {
System.out.println(arr[0]);
return;
} else if (N == 2) {
String s1 = arr[0] + "";
String s2 = arr[1] + "";
System.out.println(Math.max(Long.parseLong(s1 + s2), Long.parseLong(s2 + s1)));
return;
}
// 代表访问过的数组位置
int[] visited = new int[N];
process(arr, new ArrayList<>(), visited);
System.out.println(ans);
}
// 收集最大的数字
private static void process(long[] arr, ArrayList<String> tmp, int[] visited) {
if (tmp.size() == 3) {
// 已经收集完三个数字
strToLong(new ArrayList<>(tmp));
return;
}
for (int i = 0; i < arr.length; i++) {
if (visited[i] == 1) {
continue;
}
visited[i] = 1;
tmp.add(arr[i] + "");
process(arr, tmp, visited);
visited[i] = 0;
tmp.remove(tmp.size() - 1);
}
}
// 将String类型转换为Long类型
private static void strToLong(ArrayList<String> tmp) {
StringBuilder res = new StringBuilder();
for (String s : tmp) {
res.append(s);
}
long aLong = Long.parseLong(res.toString());
ans = Math.max(ans, aLong);
}
} public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
// 使用字符串数组接收整数
String[] nums = new String[N];
for (int i = 0; i < N; i++) {
nums[i] = sc.next();
}
// 对数字进行排序，从大到小排序。先按照长度从大到小排序，毕竟长度越长，拼接后的位数越多，也就越大
// 如果长度相同按照，按照字典序进行排序，也就是o1 = "91", o2 = "81" 那么91应该排在前面
Arrays.sort(nums, (o1, o2) -> o1.length() == o2.length() ? o2.compareTo(o1) : o2.length() - o1.length());
// 取出来3个数字，这时候取出来的三个，可能是3个长度从大到小排列的三个数字，也可能是长度都相同，按照字典序排序的三个数字
// 但是可以保证的是，这三个一定是长度排名前三的数字（可以第四个也是和第三个长度一样，但是字典序不如第三个）
String[] tmp = new String[3];
for (int i = 0; i < 3; i++) {
tmp[i] = nums[i];
}
// 这时候长度已经定了，现在就是看怎么排列最大的问题了，肯定是按照字典序从大到小排列
// 比如三个数字是 1234 91 99，这时候99 91 1234 这样拼接最大
// 但是如果测试用例为1 2 56 561，通过第一轮排序后剩下的是2 56 561，如果只按照字典序从大到小排序的话
// 561 56 2，最后输出的就是561562.但是很显然565612是最大的
// 所以需要两两相加排序，比如此时o1 = "56", o2 = "561"
// (o1 + o2) = "56561" (o2 + o1) = "56156"
// 很显然(o1 + o2).compareTo(o2 + o1)，会返回一个4（遇到的第一位不相同的字符，ASCII码相减）
// 然后返回的是正数，就会调整顺序，所以改成(o2 + o1).compareTo(o1 + o2))
Arrays.sort(tmp, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
StringBuilder sb = new StringBuilder();
for (String s : tmp) {
sb.append(s);
}
System.out.println(Long.parseLong(sb.toString()));
} 2. 移位游戏，这道题过了91%，因为当时找bug的时候，全把注意力放在了两个数字能不能为0的case，但是题目中给的参数范围1≤ a,b ≤10^18，根本不会有0的存在。
具体解法，放代码里面了。
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
long[][] arr = new long[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = scanner.nextLong();
arr[i][1] = scanner.nextLong();
}
for (int i = 0; i < arr.length; i++) {
long a = arr[i][0];
long b = arr[i][1];
System.out.println(get(a, b));
}
}
public static int get(long num, long target) {
if (num == target) {
// num和target本来就相等
return 0;
}
if (num > target && num % 2 != 0) {
// 如果num大于target，代表需要除法运算
// 但是num不可以被2整除，也就代表着不能被2、 4、 8整除
// 所以不可能变成target
return -1;
}
int option = 0;
// 不能使用除法，例如num = 90, target = 5
// 90 / 2 = 45, 45 / 2 = 22, 22 / 2 = 11, 11 / 2 = 5
// 这样就会num == target，实际上是不可能相等的，因为运算过程中自动向下取整，才会出现相等的情况。
long max = Math.max(num, target);
long min = Math.min(num, target);
while (min != max) {
min *= 2;
option++;
if (min > max) {
// 迭代不断增大的过程中，居然min 大于了 max，说明min根本就不可能通过乘2和max相等
return -1;
}
}
// 这里啰嗦一句，说一下我是怎么通过option生成返回值的
// 如果option，也就是num 变成 target（或者target变成num）所需的2的次数
// 不管是乘2也好，除2也好，反正到这说明他们是可以通过option次变成对方的
// 所以一个option就代表一个2 ^ 1。首次尽最大努力，用2 ^ 8来完成转换操作。
// 比如通过9次乘2操作，num变成了target。那么使用3次2 ^ 8无疑是最省的方案。
// 有点贪心的思想吧，能只用2 ^ 3次方，就只用 2 ^ 3。
// 例如option = 13, 14 % 3 = 2。说明不能只使用2 ^ 3，那么就看看能最多用几次2 ^ 3， 14 / 3 = 4
// 然后剩下一个tmp = 14 % 3 = 2，那么 2，就使用 2 ^ 2次方尽最大努力来凑齐。
// 这里因为第一步是模运算，option mod 3，所以只会有三个结果 0, 1, 2
// 那肯定等于0的提前返回了，等于2的，使用一次2 ^ 2，然后返回，等于1的，就用一次2 ^ 1。最后返回
if (option % 3 == 0) {
// 只用2 ^ 3就可以完成简化操作，那么直接返回
return option / 3;
}
// 到这说明，不可以只使用2 ^ 3完成简化操作
// 能使用 2 ^ 3简化的最大次数
int three = option / 3;
// 剩下的值
int tmp = option % 3;
// 能使用 2 ^ 2简化的最大次数
int two = 0;
// 能使用 2 ^ 1简化的最大次数
int one = 0;
if (tmp % 2 == 0) {
// 可以用2 ^ 2简化所有
two = tmp / 2;
} else {
// 只能用2 ^ 1简化
one = tmp;
}
// 这里为了容易理解，三数相加。其实在判断的时候，就可以返回结果了。
return three + two + one;
}
} 3. 上升子序列，这时候没找到很好的解法，笔试完补了一个暴力递归的方法，当时卡在了怎么生成所有的情况，看来递归还得多练。 public class Main {
static long ans = 0;
static long mod = 998244353;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 每个数组的长度
int N = scanner.nextInt();
// 数组的可取值范围[1,M]
int M = scanner.nextInt();
int[] nums = new int[N];
process(nums, 0, M);
System.out.println(ans % mod);
}
private static void process(int[] nums, int index, int M) {
if (index == nums.length) {
// 已经填满了nums，可以进行一次判断
if (judge(nums) == 3) {
ans++;
}
return;
}
for (int i = 1; i <= M; i++) {
nums[index] = i;
process(nums, index + 1, M);
}
}
private static int judge(int[] nums) {
int ans = 0;
int N = nums.length;
int[] dp = new int[N];
Arrays.fill(dp, 1);
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
通过这几天的笔试带来的经验教训：
- 注意看给定参数的范围，非常重要！
- 最近考察排列组合问题很多，比如好多思想都是凑齐硬币、求子集、全排列等等。
