PDD temu支付 hr面挂

A卷，选择题不做记录，只做编程题记录。编程题有点思考量，最终还是写完了，3/3，希望有面试编程1：一个数组，每次可以选择一个元素a[i]，拆成两个和为a[i]的正整数x,y问最少多少次拆分可以让数组最大值不超过最小值的2倍n<=2e5,1<=a[i]<=1e9解法：记录最小值mn，把超过2mn的数字都强制拆成2mn，不足保留余数。这样每次拆分代价就是a[i]/(2mn)-1，如果a[i]无法整除2mn需要多拆一次。复杂度O(n)编程2：一个数组，每次可以选择两个下标i,j，如果n/i==n/j（下取整），则可以把a[i]和a[j]同时变成gcd(a[i],a[j])令最终数组和最小n<=2e5,a[i]<=1e9解法：不妨令n/i（下取整）相同的元素放在一起考虑，他们之间会相互影响，则最小化元素和，就是把每个元素变成他们的公共gcd，计算公共gcd只需要顺序累计gcd即可。复杂度O(nloga[i])编程3：一个数组，每次可以交换两个相邻元素，让数组变成单峰序列，求最小交换次数n<=5e5,a[i]<=1e9解法：按数值从小到大考虑。最小的数值肯定是排在序列头或者序列尾，可以发现每次考虑完最小元素，剩余元素就变成了一个规模缩小的子问题。只需要每次看把最小元素放在头所需步骤更少，还是放在尾所需步骤更少。另外还需要考虑相同元素的情况。先考虑最小元素是单独出现的情况，只需判断元素在原数组里，前面有多少个数字，后面有多少个数字即可。考虑完就把数字从原数组删掉。这里可以用线段树、树状数组、或者提前预处理逆序对也ok然后是相同数字如何处理，假设有k个相同的最小元素。不妨考虑其中q个放在队头，p个放在队尾。很显然我们需要按照这些元素原来的相对顺序，前q个依次放队头，后p个逆序依次放队尾，这样是最优的。直到这个顺序就可以枚举多少个放队头，这里预处理每个元素移动到队头队尾所需的步骤，然后用前缀和优化即可。最终总复杂度O(nlogn)

第一题 min*2>=max先找最小值，然后ans+=(nums[i]-1)/(min*2)例：最小值为3min*2=6任何大于6的num最优分解是6+(num-6)总的分解次数就是(num-1)/6补充：7实际不能分解为1+6而应该分解为3+4，但是我们不需要单独处理这种情况，只需要知道都是分解一次即可要用long long，没用20%第二题 gcd同一个区间所有数gcd，然后*区间大小，最后所有区间加起来就行要用long long ，没用0%第三题 先递增后递减我过了25，10％单独判断是否有序，15%正常求解我的想法是 先找到最小的，然后移动到最左或最右（比较一下哪边近）（不用真的...

本来也没想投秋招，国庆时投了一下，果然很悲哀投递无反应：滴滴腾讯百度快手小红书阿里云简历挂：虾皮笔试：美团