引言
- 今天做了蚂蚁集团的笔试，踩了很多雷，这里整理一下，记录一下，防止下次再踩雷！
正文
第一题——算折扣
题目
-
小苯看中了一件价值为p元的物品，他手里有1个“打折券"和 1个“立减券”。两种优惠券可以都用在物品上，且使用顺序也是任意的。
-
两种优惠券分别以整数x和y的方式给出。
- 打折券:如果当前物品价格为p，使用后，物品价格变为z* p/100上取整
- 立减券:如果当前物品价格为P，使用后，物品价格变为max(0,p-y)。即物品价格立减y元，但最多减到 0。
-
小苯想知道，这件价值为 p的物品最少可以花多少钱买到。
个人实现
- 这个题就是计算一下两种情况的具体价格，然后比大小就行了，是一个签到题，但是卡了一下！int类型整除，后面那个数字忘记加个".0",最后报错了！
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
double p = sc.nextDouble();
double x = sc.nextDouble();
double y = sc.nextDouble();
int cost_1 = (int)Math.ceil(x * p / 100 - y);
int cost_2 = (int)Math.ceil((x - y) * p / 100);
System.out.println(Math.min(cost_1, cost_2));
}
}
}
总结
- 对于Java中的整除而言，如果两边的数据不一致会出现自动类型转换，顺序如下
- byte < short < int < long < float < double
- 这里不要忘记了
第二题
题目
-
小红拿到了一个数组，她可以进行最多一次操作:
- 选择一个元素，使其加1。小红希望操作结束后，数组所有元素乘积的未尾有尽可能多的0。你能帮帮她吗?
-
输入描述
- 第一行输入一个正整数n，代表数组的大小
- n在【1, 1 0 5 10^5 105】
- 第二行输入n个正整数ai，代表数组的元素
- ai在【1, 1 0 9 10^9 109】
- 第一行输入一个正整数n，代表数组的大小
-
输出描述
- 一个整数，标识末尾零的个数
个人实现
错误实现一
这个我直接模拟了，想着就算会越界，也会过一部分样例，然后报一个执行异常啥的，结果一个样例没过，直接报错！
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt();
int[] nums = new int[n];
long mulAll = 1;
for(int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
mulAll *= nums[i];
}
int res = 0;
for(int i = 0 ;i < n;i ++){
int curNum = nums[i] + 1;
long curMul = mulAll / nums[i] * curNum;
int count = 0;
while(curMul % 10 == 0){
count ++;
curMul /= 10;
}
res = Math.max(res, count);
}
System.out.println(res);
}
}
}
- 这样是能够过测试样例，但是一交上去，一个样例都没通过，而且会显示答案错误
- 错误原因分析如下
- int类型的范围【 10 − 10 {10}^{-10} 10−10, 10 10 {10}^{10} 1010】
- long类型的范围【 10 − 19 {10}^{-19} 10−19, 10 19 {10}^{19} 1019】
- 数字最多有 1 0 5 10^5 105个，也就是9的 1 0 5 10^5 105次方，啥玩意都得越界，根本不可能使用这种方法实现
- 下述是越界之后的运行情况：不会报错，不要搞错了！
这些东西还是在做题的时候意识到了，然后测试了一下，发现没有报错，才知道的，浪费了多少时间！！
修改实现二
思路分析
- 10 = 2 *5
- a * b * c，相当于a1 * a2 * a3 * b1 * b2 * b3 * c1 * c2 * c3 ,其中a1 * a2 * a3 = a，b1 * b2 * b3 = b，c1 * c2 * c3 = c
- 这里是若干数相乘，判定最后还剩下几个零，就是看能够拆成几个2和几个5，然后取一个最小值
import java.util.*;
public class Main {
static int[] count2And5(int num) {
int[] res = {0, 0};
if (num % 2 == 0) {
int curNum = num;
while (curNum % 2 == 0) {
res[0]++;
curNum /= 2;
}
}
if (num % 5 == 0) {
int curNum = num;
while (curNum % 5 == 0) {
res[1]++;
curNum /= 5;
}
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[] nums = new int[n];
Map<Integer, Integer> map2 = new HashMap<>();
Map<Integer, Integer> map5 = new HashMap<>();
// 计算所有的整数中的2的数量和5的数量
int count2 = 0;
int count5 = 0;
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
if (map2.containsKey(nums[i]) || map5.containsKey(nums[i])) {
count2 += map2.getOrDefault(nums[i], 0);
count5 += map5.getOrDefault(nums[i], 0);
} else {
int[] countNum = count2And5(nums[i]);
count2 += countNum[0];
count5 += countNum[1];
map2.put(nums[i], countNum[0]);
map5.put(nums[i], countNum[1]);
}
}
// 逐个遍历修改每一个数字
int res = Math.min(count5, count2);
for (int i = 0; i < n; i++) {
// 计算出修改之后的2和5的数量
int curNum = nums[i] + 1;
int curCount2 = 0;
int curCount5 = 0;
if (map2.containsKey(curNum) || map5.containsKey(curNum)) {
curCount2 = map2.getOrDefault(curNum, 0);
curCount5 = map5.getOrDefault(curNum, 0);
} else {
int[] countNum = count2And5(curNum);
curCount2 = countNum[0];
curCount5 = countNum[1];
map2.put(curNum, countNum[0]);
map5.put(curNum, countNum[1]);
}
// 计算修改之后的最大值
int curNum2 = count2 - map2.get(nums[i]) + curCount2;
int curNum5 = count5 - map5.get(nums[i]) + curCount5;
res = Math.max(res,Math.min(curNum2,curNum5));
}
System.out.println(res);
}
}
}
- 记得这样写的代码是全过的，没有问题！
总结
- 数据类型的溢出，并不会报异常，什么问题都没有，会正常输出，然后给你一个答案错误！
- 数据溢出会报答案错误！
第三题
题目内容
- 小苯来到了一座山脉，山谷中有n座山，每座山都有一个高度h1。有些山之间有路径连接，例如如果a号山和b号山之间有路径，如果小苯想的话，他可以从a山走到b山，同样的，也可以从b山走到a山.
- 但小苯很懒，如果两座山之间的高度差大于一定的值k，他就不会走这条路(无论是上山还是下山)，形式化的即。 ∣ h a − h b ∣ > k |h_a - h_b| > k ∣ha−hb∣>k的话，小苯便不会走这条路,
- 现在他提出了q次询问，每次询问他都会给出一组(a,b,k)，他想知道，如果他从a山出发，高度差大于k的路径他不走，能否找到一条路使得他能走到b山呢，请你帮帮他吧，
输入说明
- 输入包含1+m+q行。
- 第一行三个正整数
- n{1≤n≤2 * 1 0 5 10^5 105),m(1≤min(n·(n-1)/2,2x 1 0 5 10^5 105),q(1≤g≤2x 1 0 5 10^5 105)，分别表示山脉中山的个数 n，山脉中山与山之间的路径数量 m，小苯的询问次数 q。
- 接下来一行输入 几个正整数 hi(1 ≤ hi≤ 1 0 5 10^5 105)，表示每座山的高度。
- 接下来 m 行，每行两个正整数 u,υ(1 ≤ u,u≤ n,u≠ v)，表示u号山到v号山有路径连接。
- 接下来q行，每行三个正整数
- α, b,k (1 ≤ a,b≤ n,a≠b),(1≤k≤ 1 0 9 10^9 109)，分别表示小苯每次询问给出的信息。
输出说明
- 可以到达就输出YES，不能就输出NO
样例
5 6 5
3 4 3 6 5
1 2
1 3
2 4
3 4
3 5
4 5
1 4 1
1 4 2
1 4 3
3 4 2
1 5 1
# 输出
NO
YES
YES
YES
NO
个人实现
思路分析
- 这个题目最后问的是否可达，并不是求什么具体的到达路径，所以我默认会使用BFS，层序遍历的速度是快于DFS的，然后再加上限定高度的条件。PS：DFS经过系统判定，会超时
因为是通过高度差来判定当前路径是否能够走，所以需要计算每条路径的高度差，具体见下图
保存每两个点之间所有路径中，高度差最大的那条路径的高度差，具体样例如下，以节点1到节点4为例子
对于测试样例具体执行结果如下
- 1 4 1：1小于最小高度差，所以不能通过
- 1 4 2：2等于最小高度差，所以能够通过
- 1 4 3：3大于最小高度差，所以能够通过
- 一次类推，14 4或者1 4 5都是可以通过的，所以能够计算出到达目标节点的最短
- 所以能够计算出每一个节点最短的路径差就行了，只要计算了，就需要保存或者更新就行
**我觉得可能是我的代码能力还不够，我觉得这个题目，每个一个小时整不出来，真的！正常只能写一个DFS或者BFS **
import javax.crypto.Cipher;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt(); //山头的数量
int m = sc.nextInt(); // 道路的数量
int q = sc.nextInt(); // 询问的次数
int[] h = new int[n + 1]; // 高度
for (int i = 1; i <= n; i++) h[i] = sc.nextInt();
// 创建对应的邻接矩阵
int[][] grid = new int[n + 1][n + 1];
for (int[] row : grid) Arrays.fill(row, -1);
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
grid[a][b] = Math.abs(h[a] - h[b]);
grid[b][a] = grid[a][b];
}
// 遍历询问次数
int[][] minGrid = new int[n + 1][n + 1];
for (int[] row : minGrid) Arrays.fill(row, Integer.MAX_VALUE);// 保存对应节点满足条件的最小高度差
boolean[][] minStatus = new boolean[n + 1][n + 1]; // 是否已经确定完最短路径
for (int i = 0; i < q; i++) {
int start = sc.nextInt();
int goal = sc.nextInt();
int hLimit = sc.nextInt();
// 判定是否已经是最小值，如果已经是最小值了，还是不行，直接跳过
if (minStatus[start][goal]) {
if (minGrid[start][goal] > hLimit) {
System.out.println("NO");
continue;
} else {
System.out.println("YES");
continue;
}
}
// 通过层序遍历来更新minGrid，并进行判断
Queue<int[]> que = new ArrayDeque<>();
// 这里生命一个visted数组
// 默认是-1，表示没有访问过，其他数值记录的是从某一个点出发到当前路径下做需要的最低的高度差
int[] visited = new int[n + 1];
Arrays.fill(visited, Integer.MAX_VALUE);
// 每一个节点记录两个状态，第一个元素是当前节点位置，下一个是从起点到当前节点的最大的高度差
que.offer(new int[]{start, 0});
while (!que.isEmpty()) {
// 队列不为空
int[] curNode = que.poll();
// 遍历所有的邻接节点
for (int j = 1; j <= n; j++) {
if (grid[curNode[0]][j] != -1) {
// 每一个节点要保存一个当前路径下的最大的高度差，然后在所有可能的路径中，保存一个最小的高度差
int curLen = Math.max(curNode[1], grid[curNode[0]][j]);
// 判断下一个目标点是否已经是目标节点
if (j == goal) {
minStatus[start][goal] = true;
minGrid[start][goal] = Math.min(minGrid[start][goal], curLen);
} else {
// 处理相同节点的情况
if (visited[j] <= curLen) {
continue;
} else {
// 当前路径经过这个节点的最大的高度差，小于已经记录的值，说明是一条有效的路线
visited[j] = curLen;
}
// 将当前节点加入到对应的队列中
que.offer(new int[]{j, curLen});
}
}
}
}
if (minStatus[start][goal] && minGrid[start][goal] > hLimit) {
System.out.println("NO");
} else {
System.out.println("YES");
}
}
}
}
}
注意点
- 感觉对于BFS而言，还是得使用一个visited数组记录哪些数据已经是访问过的，然后在遍历后续节点，进行访问
参考实现——使用并查集解决
- 这里很经典地使用了并查集去解决这个问题，其实也是自然而然，通过限定边的长度，再借由并查集计算对应高度差下的连通性，然后查询共同的父节点，判定是否为同一块联通图，进而判定能否到达！
具体步骤见下图
- 先按照询问的高度差对每一次询问进行排序
- 按照边的长度逐个添加，整个过程如下，这样很明显可以看到，每一块联通图限定的高度差，如果起点和终点在同一个联通块上，就是可以访问的，如果不是在一个连通块上，就不能访问。
具体实现如下
import javax.crypto.Cipher;
import java.util.*;
public class Main {
private static int[] fa;
private static int find(int a) {
if (fa[a] == a) {
return a;
} else {
return find(fa[a]);
}
}
private static void union(int x, int y) {
int fx = find(x);
int fy = find(y);
fa[fy] = fx;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt(); //山头的数量
int m = sc.nextInt(); // 道路的数量
int q = sc.nextInt(); // 询问的次数
int[] h = new int[n + 1]; // 高度
for (int i = 1; i <= n; i++) h[i] = sc.nextInt();
// 创建对应的邻接矩阵,包含了三个元素，分别是 hSubtract，start，end
List<int[]> list = new ArrayList<>();
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
list.add(new int[]{Math.abs(h[a] - h[b]), a, b});
}
list.sort((a, b) -> Integer.compare(a[0], b[0]));
// 保存所有的询问情况
List<int[]> listQuery = new ArrayList<>();
for (int i = 0; i < q; i++) {
int start = sc.nextInt();
int goal = sc.nextInt();
int hLimit = sc.nextInt();
listQuery.add(new int[]{hLimit, start, goal, i});
}
listQuery.sort((a, b) -> Integer.compare(a[0], b[0]));
// 创建对应的并查集
fa = new int[n + 1];
for (int i = 1; i <= n; i++) fa[i] = i;
// 从小到大遍历每一个问句，并进行排序
int edgeIdx = 0;
boolean[] ans = new boolean[q + 1];
for (int[] query : listQuery) {
int qK = query[0];
int qS = query[1];
int qE = query[2];
int idx = query[3];
// 遍历其中小于qK的边，并构建对应的联通图
while (edgeIdx < m) {
// 遍历所有的符合条件的边，也就是山峰之间的高度差k <= qk 就表示有效
int k = list.get(edgeIdx)[0];
int s = list.get(edgeIdx)[1];
int e = list.get(edgeIdx)[2];
if(k > qK) break;
// 符合条件构建联通图
union(s, e);
edgeIdx++;
}
// 判定目标是否在同一个联通图内部
int fQS = find(qS);
int fQE = find(qE);
ans[idx] = fQS == fQE;
}
for (int i = 0; i < q; i++) {
if (ans[i]) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
}
总结
- 其实我觉得这个题目是一个类似模板题——联通块，但是之前没有接触过，并查集只是用来证明过传递性，不过传递性不也是连通性吗？总结一下，积累一下，下次肯定能做出来！
总结
- 数据溢出无异常，仅仅一个答案错误
- 小数整除后面加个零
- 我觉得最后一题还是蛮难的，后续我都想了半天，还是蛮难的，图这一块还不是很熟悉！再加油！
- 有的时候就在想，为什么有的题你能写的很快，有的题你只能慢慢想，跟打补丁一样？我觉得很大一部分原因，是写过的题目，知道大概采用什么方法，然后就知道了会采用什么框架，然后往里面套就行了！对于写得慢的题目，找不到一个大概的方法，然后只能自己进行模拟！感觉要重视方法，而不是题目！重视思考方式，而不是具体的代码！
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
