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

2024-08-26 04:12

本文主要是介绍秋招突击——笔试整理——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——拼多多笔试整理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1107512

相关文章

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

rtmp流媒体编程相关整理2013(crtmpserver,rtmpdump,x264,faac)

转自:http://blog.163.com/zhujiatc@126/blog/static/1834638201392335213119/ 相关资料在线版(不定时更新,其实也不会很多,也许一两个月也不会改) http://www.zhujiatc.esy.es/crtmpserver/index.htm 去年在这进行rtmp相关整理,其实内容早有了,只是整理一下看着方

笔记整理—内核!启动!—kernel部分(2)从汇编阶段到start_kernel

kernel起始与ENTRY(stext),和uboot一样,都是从汇编阶段开始的,因为对于kernel而言,还没进行栈的维护,所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用,前面关于uboot的文章中有提到过(eg:zImage)。uboot启动是无条件的,只要代码的位置对,上电就工作,kern

JavaScript整理笔记

JavaScript笔记 JavaScriptJavaScript简介快速入门JavaScript用法基础语法注释关键字显示数据输出innerHTML innerText属性返回值的区别调试 数据类型和变量数据类型数字(Number)字符串(String)布尔值(Boolean)null(空值)和undefined(未定义)数组(Array)对象(Object)函数(Function) 变量

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

【JavaScript】LeetCode:21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心:连续和(count)< 0时,放弃当前起点的连续和,将下一个数作为新起点,这里提供使用贪心算法解决本题的代码。动态规划:dp[i]:以nums[i]为结尾的最长连续子序列(子数组)和。 dp[i] = max(dp[i - 1]

关于回调函数和钩子函数基础知识的整理

回调函数:Callback Function 什么是回调函数? 首先做一个形象的比喻:   你有一个任务,但是有一部分你不会做,或者说不愿做,所以我来帮你做这部分,你做你其它的任务工作或者等着我的消息,但是当我完成的时候我要通知你我做好了,你可以用了,我怎么通知你呢?你给我一部手机,让我做完后给你打电话,我就打给你了,你拿到我的成果加到你的工作中,继续完成其它的工作.这就叫回叫,手机

站长常用Shell脚本整理分享(全)

站长常用Shell脚本整理分享 站长常用Shell脚本整理分享1-10 站长常用Shell脚本整理分享11-20 站长常用Shell脚本整理分享21-30 站长常用Shell脚本整理分享31-40 站长常用Shell脚本整理分享41-50 站长常用Shell脚本整理分享51-59 长期更新

两道笔试题

“char a='\72'”是什么意思? 这么理解:\为转义字符,\072转义为一个八进制数072,也就是十进制数的58买一送一,将转义字符对照表也一并贴给你吧:转义字符 意义 ASCII码值(十进制) \a 响铃(BEL) 007 \b 退格(BS) 008 \f 换页(FF) 012 \n 换行(LF) 010 \r 回车(CR) 013 \t 水平制表(HT) 009 \v 垂直制表(VT