腾讯数据与算法提前批笔试题目参考代码
1 2 3 5题是100%; 第4题,当时读题读的太费劲没做出来,等读明白题就要结束了
1. n个检查点通过n-1个
贪心,5种情况,应该还可以缩减没细想
1. 起始点比最小值小
2. 起始点比最大值大
3.起始点在最大值和次大值之间
4.起始点在最小值和次小值之间
5.other
后3种情况要么舍弃最小值,要么舍弃最大值。具体情况不分析了
//package Tencent0310.Test1; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); if (n == 1){ System.out.println(0); return; } int start = sc.nextInt(); int []arr = new int[n]; for (int i = 0; i < n; i++){ arr[i] = sc.nextInt(); } Arrays.sort(arr); int min1 = arr[0], min2 = arr[1], max1 = arr[n-1], max2 = arr[n-2]; if (start <= min1) System.out.println(max2 - start); else if(start >= max1) System.out.println(start - min2); else if (start > min1 && start <= min2){ int res = Math.min(max1 - start, max2 - start + 2 * (start - min1)); System.out.println(res); } else if (start < max1 && start >= max2){ int res = Math.min(start - min1, start - min2 + 2 * (max1 - start)); System.out.println(res); } else { int res1 = Math.min(2 * (max1-start) + start - min2, 2 * (start-min1) + max2 - start); int res2 = Math.min(max1-start + 2 * (start - min2), start-min1 + 2 * (max2 - start)); System.out.println(Math.min(res1, res2)); } //System.out.println(max1 + ";" + max2 + ";" + min1 + ";" + min2); } }
2. 登塔
动态规划,每一步记录两个状态,一个是如果该层是爬上来的最短时间,一个是该层是跳上来的最短时间
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int []arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = sc.nextInt(); int [][]dp = new int[n][2]; dp[0][0] = 0; dp[0][1] = arr[0]; if (n <= 2){ System.out.println(0); return; } dp[1][0] = 0; dp[1][1] = Math.min(dp[0][0], dp[0][1]) + arr[1]; for (int i = 2; i < n; i++){ dp[i][0] = Math.min(dp[i-2][1], dp[i-1][1]); dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i]; } System.out.println(Math.min(dp[n-1][0], dp[n-1][1])); } }
3. 出队顺序
这个不贴代码了,用队列模拟就可以了,代码找不到了,简单写一下,可能与我提交的有出入,单应该这个思路
for(int i = 1; i <= n; i++) queue.offer(i); while(!queue.isEmpty()){ System.out.println(queue.poll()); //格式先不管了 if (!queue.isEmpty()) queue.offer(queue.poll())) }
4. 黑白块
计算黑块有多少个
1 涂成白色 黑块总数减去该区域所有黑块数
2 涂成黑色 黑块总数加上该区域所有白块数
3 重合的部分所有白色变成黑色, 初始状态是白色变成黑色的不用计算了(2中已经计算),需要加上的就是最初状态是黑色,在1中被涂成了白色的数量,也就是黑块总数加上重叠区域最初的黑块数目
1 涂成白色 黑块总数减去该区域所有黑块数
2 涂成黑色 黑块总数加上该区域所有白块数
3 重合的部分所有白色变成黑色, 初始状态是白色变成黑色的不用计算了(2中已经计算),需要加上的就是最初状态是黑色,在1中被涂成了白色的数量,也就是黑块总数加上重叠区域最初的黑块数目
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while(T-- > 0){ int n = sc.nextInt(), m = sc.nextInt(); int xa1 = sc.nextInt(), ya1 = sc.nextInt(); int xa2 = sc.nextInt(), ya2 = sc.nextInt(); int xb1 = sc.nextInt(), yb1 = sc.nextInt(); int xb2 = sc.nextInt(), yb2 = sc.nextInt(); int blackCnt = blackCount(1, 1, n, m); blackCnt -= blackCount(xa1, ya1, xa2, ya2); blackCnt += (xb2 - xb1 + 1) * (yb2 - yb1 + 1) - blackCount(xb1, yb1, xb2, yb2); blackCnt += overlayBlackCount(xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2); System.out.println((n * m - blackCnt) + " " + blackCnt); } } private static int overlayBlackCount(int xa1, int ya1, int xa2, int ya2, int xb1, int yb1, int xb2, int yb2){ int x1 = Math.max(xa1, xb1); int y1 = Math.max(ya1, yb1); int x2 = Math.min(xa2, xb2); int y2 = Math.min(ya2, yb2); if (x1 <= x2 && y1 <= y2){ return blackCount(x1, y1, x2, y2); } return 0; } private static int blackCount(int x1, int y1, int x2, int y2){ /* |-------|-------| | a | b | |-------|-------| | c | d | |-------|-------| 左上角(1, 1) 右下角坐标(x, y) 的矩形中黑块数为(x * y) / 2; 设整个大矩形区域内有 x 个 d = x - (a + c) - (a + b) + a; a + c 和 a + b 和 a 都可以直接算出 */ return ((x2 * y2) >> 1) - (((x1 - 1) * y2) >> 1) - ((x2 * (y1 - 1)) >> 1) + (((x1 - 1) * (y1 - 1)) >> 1); } }
5. 最小差值
这个不用说了吧,就相当于对前面的数据进行二分查找
//package Tencent0310.Test5; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); TreeMap<Integer, Integer> map = new TreeMap<>(); int n = sc.nextInt(); //int []arr = new int[n]; for (int i = 1; i <=n ; i++){ int tmp = sc.nextInt(); //arr[i-1] = tmp; if (i >= 2){ Map.Entry<Integer, Integer> e1 = map.floorEntry(tmp); Map.Entry<Integer, Integer> e2 = map.ceilingEntry(tmp); int min = Integer.MAX_VALUE, p = -1; if (e1 != null){ min = Math.abs(tmp-e1.getKey()); p = e1.getValue(); } if (e2 != null){ if (Math.abs(tmp- e2.getKey()) < min){ min = Math.abs(tmp-e2.getKey()); p = e2.getValue(); } } System.out.println(min + " " + p); } map.put(tmp, i); } } }
#笔试题目##提前批##腾讯#