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

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

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

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

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

输入描述:

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

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

3125

123

#牛人的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 100int 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("%d\n",d[j]);    }    printf("%d",d[time-1]);    return 0;}

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

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

例如N=3，可能的排列共6种：

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

定义函数F:

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

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

输入描述:

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

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

223

1 10 2

对于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;   }}

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

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