秋招突击——笔试整理——8/25—

本文主要是介绍秋招突击——笔试整理——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();  }  
}