本文主要是介绍秋招突击——笔试整理——8/25——拼多多笔试整理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 引言
- 正文
- 第一题——多多删树
- 个人解答
- 第二题、多多的奇数序列
- 个人解答
- 第三题:多多换礼物
- 个人解答
- 参考实现
- 第四题、多多的字符反转
- 个人实现
- 总结
引言
- 今天的拼多多笔试挺难的,感觉自己在技巧性还差很多,很多东西需要看很久,或者说思维方式有问题!总是执着于一个代码想很久!
- 自己没截屏保存,题目来源——万诺coding
正文
第一题——多多删树
个人解答
- 最终结果的有两个部分构成,边权和 + v【连通块数】
- 如果不考虑数组v,那么就剩下边权和,那么不删除肯定是最多的
- 不考虑连通块数,那么就是直接找v中最大的
- 现在是必须删除的话,删除一个边权,就要加上一个V,所以的选择删除最小的边权,然后的找逐个添加对应的v,遍历完毕就是最大值。
- 因为这是一个树,然后删除任何一条变,肯定会增加一个连通块!
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;/*** @author Long Guo* @create 2024-08-25-19:04*///TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int T = in.nextInt();while(T > 0){T--;int n = in.nextInt();int[] nums = new int[n];for(int i = 0; i < n; i++) nums[i] = in.nextInt() ;int[][] grid = new int[n + 1][n + 1];List<Integer> list = new ArrayList<>();in.nextLine();int sumWeight = 0;while (in.hasNextLine()){String line = in.nextLine();//in.nextLine();Scanner str = new Scanner(line);int x = str.nextInt();int y = str.nextInt();int w = str.nextInt();grid[x][y] = w;list.add(x);sumWeight += w;}Collections.sort(list);int res = sumWeight + nums[0];for(int i = 0;i < list.size();i ++){sumWeight = sumWeight - list.get(i);res = Math.max(res, sumWeight + nums[i + 1]);}System.out.println(res);}}
}
总结
- 这个题目有一个关键点,就是他是树,所有节点的入度只能是1,只有一个父节点,但是可以有多个子节点,所以删除任何一条边,都会增加一个连通块!
- 两个角度,只考边权和只考虑序列,然后在结合进行考虑即可!
第二题、多多的奇数序列
个人解答
- 两种操作,都可以将偶数变成奇数,所以应该怎么做?两种操作同时考虑有点复杂,先仅仅考虑一种操作的。
操作一:不断减半
- 不断除以二,直到是奇数为止
- 假设:
- 如果仅仅只有这一种操作,那么将所有的序列变成奇数的步骤数是固定的,直接遍历每一个偶数,然后计算对应的步数就行了!
操作二:两个数字替换为两数之和
- 两个偶数相加 ,肯定还是偶数,并没有很任何意义
- 两个奇数,不需要操作,因为已经满足了条件
- 一个奇数一个偶数,相加直接是奇数
- 假设:
- 如果仅仅只有这一种操作,如果全部都是偶数,没有办法操作,但凡有一个奇数,那么操作次数就是偶数个数之和
两种操作混合
- 这两种操作混合能否带来次数上的改良?
- 如果一个数字需要执行操作一多次,才能变成奇数,就可以执行操作二
- 先选一个需要最小次数就能变成奇数的数字,执行操作一,然后的后续的数字都执行操作二,就是最小的!
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;/*** @author Long Guo* @create 2024-08-25-19:04*///TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int T = in.nextInt();while (T > 0){T --;int n = in.nextInt();int[] nums = new int[n];boolean evenFlag = false;int oddNum = 0;int oper1Min = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {nums[i] = in.nextInt();if((nums[i] & 1) == 1){// 判定是否为奇数evenFlag = true;} else {// 判定是否为偶数,并且记录对应偶数的修改次数的oddNum ++;int oper1Num = 0;int temp = nums[i];while ((temp & 1) == 0){oper1Num ++;temp = temp >> 1;}oper1Min = Math.min(oper1Min, oper1Num);}}// 具体处理if(evenFlag){//存在奇数,直接操作System.out.println(oddNum - 1);}else{// 不存在偶数System.out.println(oper1Min + oddNum - 1);}}}
}
总结
- 这道题按照那种由简单到复杂的思路去分析,还是很好解决的,然后可以使用hashMap在优化一下,提高一下性能!
第三题:多多换礼物
个人解答
- 先从简单的思路入手,看看怎么做,换礼物,只能换比x小的礼物,可以先抱着试试的角度出发,有几种角度可以试试看
从前往后找,能换就换
- 直接换到了最小的1,执行不下去了,这个时候返回-1就行了
从后往前找,能换就换
- 这个时候的返回1,因为就算拿到了最小的,但是结果已经成了
实现
- 初步来看,从后往前换的,能换就换,可以解决这个问题
- 因为只能更换比自己小的数字,所以有以下两种情况
- 情况一:某一个数字比当前数字大
- 你的初始值4,但凡比4大的数字你都不能换,因为你动不了
- 这个时候可以处理一下,如果在不能换的数字中,存在倒序的,直接返回-1
- 情况二:某一个数字比当前数字小
- 这个更换的数字只会越来越大,所以不能从小数开始更换,应该从后往前进行交换,后面的数字越大的,而且后面如果有小数字,肯定是要换出来的,不然会报错!
- 然后换到不能换为止,如果要换的一个数字,和周围两个数字都是有序,就没有必要换了
- 情况一:某一个数字比当前数字大
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;/*** @author Long Guo* @create 2024-08-25-19:04*///TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()){int n = in.nextInt();int x = in.nextInt();int[] nums = new int[n];// 使用一个dp数组来记录前n个元素是否已经是单调递增boolean[] dp = new boolean[n];dp[0] = true;// 增加特判的最大值的boolean进行处理int numBig = 0;int minVal = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {nums[i] = in.nextInt();minVal = Math.min(minVal, nums[i]);if (i > 0 && nums[i] >= nums[i - 1]){dp[i] = dp[i - 1];}// 需要特判一下是否存在无法交换的值不是非单调递减的,不能交换的数字存在特别大的数字if(nums[i] >= x){if(nums[i] > numBig) numBig = nums[i];else {System.out.println(-1);return;}}}// 然后按照序列进行交换// 是否本来就已经有序了if (dp[n - 1]) {System.out.println(0);return;}int count = 0;int i ;for ( i = n - 1;i >= 0;i --){//是否进行更换if(nums[i] < x){// 更换对应的值,这里只要是能够更换,就一定保证从i到n都是单调递增的int temp = x;x = nums[i];nums[i] = temp;count++ ;// 判定一下,是否执行失败的,如果的if (i > 0 && nums[i] >= nums[i - 1] && dp[i - 1]){System.out.println(count);return;}// 判定是否满足迭代终止条件if (i > 0 && x == minVal && !dp[i - 1]){System.out.println(-1);return;}}}}}
}
总结
- 其实这种又不能实现的题目,有一个空子可以钻,他仅仅只需要测试一个样例,如果不能找到就输出零,所以如果什么都没想到,就直接返回-1,能够过一部分样例,这个技巧真好用!
- 当时没看到他说的,只能交换比他价格更低的物品,然后犹豫徘徊了很久,浪费了很多时间!
- 有问题,我并不知道怎么解决!怎么证明!
参考实现
这个推论就不知道怎么实现,怎么证明是这样的?有点说不上来,但是有感觉!
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int x = scanner.nextInt();int[] a = new int[n + 2];int[] b = new int[n + 2];for (int i = 1; i <= n; i++) {a[i] = scanner.nextInt();b[i] = a[i];}int pre = 1;int pos = n + 1;a[pos] = 1000000005; // 相当于 1e9+5 的整数值for (int i = 2; i <= n; i++) {if (a[i] >= a[pre]) {pre = i;} else if (a[i] < a[pos]) {pos = i;}}if (pos != n + 1) {b[pos] = x;}Arrays.sort(b, 1, n + 1);int res = 0;for (int i = 1; i <= n; i++) {if (a[i] > b[i]) {System.out.println(-1);return;}if (a[i] != b[i]) {res++;}}System.out.println(res);}
}
第四题、多多的字符反转
- 这个题费的时间最多,有点轴了,并不知道具体应该怎么做,很难受!
个人实现
思维方式
- 这道题就是见没见过的问题了,我就是想的是随便找一个位置开始反转,然后再找一个位置开始反转,每一次反转都计数,难点在于,有的时候,我并不知道给我一个字符串,我能不能反转出最长的序列,这是最尴尬的。然后就陷入了困顿。
- 那正常应该怎么想?
画图发现了,无论怎么反转,都是成环的情况,所以还是得好好看一下
- 原来是两个相邻的点,相当于圆的一个点,然后同时掰开,然后在放到外侧,外侧两个点本质上也是一个点
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 读取n scanner.nextLine(); // 消耗掉n后的换行符 String st = scanner.nextLine(); // 读取字符串 // 将字符串复制一遍并拼接 String doubledSt = st + st; int len = 1; // 当前长度 int res = 1; // 结果,记录最长无重复字符子串的长度 // 遍历拼接后的字符串 for (int i = 1; i < doubledSt.length(); i++) { if (doubledSt.charAt(i) != doubledSt.charAt(i - 1)) { len++; // 如果当前字符与前一个字符不同,则长度+1 res = Math.max(res, len); // 更新最长长度 } else { len = 1; // 如果当前字符与前一个字符相同,则重置长度为1 } } // 输出结果,但考虑到原字符串长度限制,需要取结果与n的最小值 System.out.println(Math.min(res, n)); scanner.close(); }
}
总结
- 继续加油!
- 转变思维,有简单到复杂,由直观到抽象,这种贪心模拟的题目一直是这样的!
这篇关于秋招突击——笔试整理——8/25——拼多多笔试整理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!