拼多多2021校招部分算法编程题合集

拼多多2021校招部分算法编程题2道,多多的魔术盒子和多多的排列函数

其实根据他的匹配职位我们可以看到,这5道题的难度还是并不高,只是作为一个初步筛选,我这边选择了前两道跟大家分享

拼多多2021校招部分算法编程题合集

[编程题一] 多多的魔术盒子:

多多鸡有N个魔术盒子(编号1~N),其中编号为i的盒子里有i个球。多多鸡让皮皮虾每次选择一个数字X(1 <= X <= N),多多鸡就会把球数量大于等于X个的盒子里的球减少X个。通过观察,皮皮虾已经掌握了其中的奥秘,并且发现只要通过一定的操作顺序,可以用最少的次数将所有盒子里的球变没。

那么请问聪明的你,是否已经知道了应该如何操作呢?

拼多多2021校招部分算法编程题合集

输入描述:

第一行,有1个整数T,表示测试用例的组数。
(1 <= T <= 100)
接下来T行,每行1个整数N,表示有N个魔术盒子。
(1 <= N <= 1,000,000,000)

输出描述:

共T行,每行1个整数,表示要将所有盒子的球变没,最少需要进行多少次操作。

输入例子1:

3
1
2
5

输出例子1:

1
2
3

​详细题解:

#牛人的Python代码:思路就是将 数字转二进制,位数就是结果,真的是牛人,太秀了

n = int(input())
for i in range(n):
    x = int(input())
    print(len(bin(x))-2)

#常规解法一(JAVA):求最少的次数把所有盒子减到0,那么第一次减少的球为中间盒子数量即可,分治求解
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            int value = scanner.nextInt();
            System.out.println(work(value));
        }
  
    }
  
    private static int work(int i) {
        int time = 1;
        while (i != 1){
            i = i/2;
            time++;
        }
        return time;
    }

#常规解法二(C/C++):也可找通过找规律求解。
#比如2、3个盒子需要2次,4、5、6、7个盒子需要3次,则n个盒子需要(logn)下取整+1次

#include<stdio.h>
#include<math.h>
#define N 100
int main(){
   int time;
   int a[N];
    int d[N];
    scanf("%d",&time);
    for(int i=0;i<time;i++){
        scanf("%d", &a[i]);
        d[i]=(log(a[i])/log(2))+1;
    }
     
    for(int j=0;j<time-1;j++){
        printf("%dn",d[j]);
    }
    printf("%d",d[time-1]);
    return 0;
}

[编程题二] 多多的排列函数:

拼多多2021校招部分算法编程题合集

数列 {An} 为N的一种排列。

例如N=3,可能的排列共6种:

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

定义函数F:

拼多多2020校招部分算法编程题合集

其中|X|表示X的绝对值。

现在多多鸡想知道,在所有可能的数列 {An} 中,F(N)的最小值和最大值分别是多少。

输入描述:

第一行输入1个整数T,表示测试用例的组数。
( 1 <= T <= 10 )
第二行开始,共T行,每行包含1个整数N,表示数列 {An} 的元素个数。
( 1 <= N <= 100,000 )

输出描述:

共T行,每行2个整数,分别表示F(N)最小值和最大值

输入例子1:

2
2
3

输出例子1:

1 1
0 2

例子说明1:

对于N=3:
- 当{An}为3,2,1时可以得到F(N)的最小值0
- 当{An}为2,1,3时可以得到F(N)的最大值2

题目详解:

题目没什么难度,主要就是要理解题目。只要明白在{An}的所有排列中,能够让F(N)取得的最大最小值为多少。

比如每四个数 5,6,7,8,我们把它们两两一组 |||8-6|-7|-5|=0,最小值是0;猜测最小值的变化也是4个一组

看到min只有2种取值。0,1,最大值自然就是N-getmin(N-1)

#JAVA题解
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int count=s.nextInt();
        for(int i=0;i<count;i++){
            int n=s.nextInt();
            solution(n);
        }
    }
    public static void solution(int n){
        int min=getMin(n);
        int max=n-getMin(n-1);
        System.out.println(min+" "+max);
    }
    public static int getMin(int n){
        if(n==1||n==2){
            return 1;
        }
        int temp=n%4;
        if(temp==1||temp==2){
            return 1;
        }
        return 0;
    }
}

#C题解 
#include <bits/stdc++.h>
using namespace std;
pair<int, int> p[110000];
int main()
{
   int t;
   cin >> t;
   for (int i = 1, f = 0; i <= 100000; i++, f = (f + 1) % 4)
   {
      if (f == 0 || f == 1)
         p[i].first = 1;
      else
         p[i].first = 0;
      if (f == 0 || f == 3)
         p[i].second = i;
      else if (f == 1|| f == 2 )
         p[i].second = i - 1;
   }
   while (t--)
   {
      int n;
      cin>>n;
      cout<<p[n].first<<" "<<p[n].second<<endl;
   }
}

总结

大厂的面试注重算法思想,有的时候你虽然不能够在规定的时间内将其编码完成,但是只要思路能够跟面试官讲清楚,也是有很大机会过的。

学习注重积累,若有不详尽之处,尽可探讨。

声明:本文由会火号官方原创,如若转载,请注明出处:https://www.huihuohao.com/s/2421.html

发表评论

登录后才能评论