拼多多2018年秋招提前批

小鱼儿 2022-05-19 09:36 263阅读 0赞

# 题目一: 喝可乐复制问题 #

有A、B、C、D四个人排成一队喝可乐，每次喝完复制自己，问数字n的人名？

import java.util.*;
    public class Solution { 
    
        //获得第N个人喝可乐的名字
        public static String  getName(int  num) {
          String[]str=new String[]{
       "A","B","C","D"};
          if(num>=1&&num<=4) return str[num-1];
          //字符串为ABCD AABBCCDD AAAABBBBCCCCDDDD ....
          int k=2;
          int sum=4;
          while(sum<num){
              k++;
              sum+=Math.pow(2,k);
          }
          int average=(int)Math.pow(2,k-2); //总共四份，没份的数量
          if(sum-num>=3*average){
                return str[0];
          }else if(sum-num>=2*average){
                return str[1];
          }else if(sum-num>=average){
                return str[2];
          }else{
                return str[3];
          }
        }
    
        public static void main(String[]args){
          // System.out.println("Hello World!");
           Scanner sin=new Scanner(System.in);
           while(sin.hasNextInt()){
               int N= sin.nextInt();
               System.out.println(getName(N));
           }
        }
    }

# 题目二: 谁是球王 #

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class PinDuoDuo2 {
    
    public static void main(String[] args) {
    //输入第一行，读取n和m
    Scanner in = new Scanner(System.in);
    String s = in.nextLine();
    String[] strs = s.split(" ");
    
    int n = Integer.valueOf(strs[0]);
    int m = Integer.valueOf(strs[1]);
    //读取投票结果，存放在一个数组中，数组中存放的是选票上的信息
    String[] str = new String[m];
    for (int i = 0; i < m; i++)
    str[i] = in.nextLine();
    // System.out.println(str.length);
    //创建一个新数组，反转str，这样数组中的每一个元素都是以为球星的投票结果，并对其进行排序
    String[] new_str = new String[n];
    
    for (int i = 0; i < n; i++) {
    char[] c = new char[m];
    for (int j = 0; j < m; j++) {
    c[j] = str[j].charAt(i);
    }
    Arrays.sort(c);
    new_str[i] = new String(c);
    }
    
    // for (String s : new_str) { 
    // System.out.println(s);
    // }
    //使用比较字符串的大小，判断是否存在球星，如果有最大值且大于一个，则不存在球星。
    int max = 0;
    
    for (int i = 1; i < n; i++) {
    if (new_str[max].compareTo(new_str[i]) > 0) {
    max = i;
    }
    if (new_str[max].compareTo(new_str[i]) == 0) {
    System.out.println("-1");
    return;
    }
    }
    
    System.out.println(max);
    
    }
    
    }

# 题目三: 运货物问题 #

N个货物分别重W1、W2、…Wn，（100<=W<=300）,一辆车可以运重量300的货，问需要多少辆车。  
思路:先从小到大排序，i、j两个指针，i从0开始遍历去掉3的整数倍个100（每三个100增加一辆车），j从N-1开始去掉大于200的数（大于200的自己一辆车），i、j所指的货物若可以拼车，车数加一，i、j向中间移动，否则，车数加一,j向中间移动。

//采用排序之后双指针移动法(背包问题)
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    
    public class PinDuoDuo3 {
    public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       String s = in.nextLine();
       String[] str= s.split("\\s+");
       ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<str.length;i++){
         list.add(Integer.valueOf(str[i]));
        }
    
      /* for(Integer l:list) System.out.println(l);*/
       Collections.sort(list);
       int i=0;
       int j=list.size()-1;
       int num=0;
       while(i<j){
         if(list.get(i)+list.get(j)>300){
              num++;
               j--;
         }
         if(list.get(i)+list.get(j)<=300){
            num++;
             j--;
           i++;
       }
     }
      if(i==j){
         num++;
      }
      System.out.println(num);
    }
    }

# 题目四: 变成靓号的最少代价 #

题意简单，号码长度为n，每个数字范围是0-9，同样的数字的个数大于等于k，则为靓号，找出成本最小且字典序最小的靓号。  
代码如下，因为是最后一道，写的有些仓促，代码有点不忍直视。主要思路就是首先用number数组记录每个数字出现的次数，然后遍历10种可能，就是将每个数字为靓号，共10种可能。用anscost和ansstr记录结果，然后每个数字比较字典序。重点在于如何修改，才能使得成本最低。  
比如，对于要使得7的个数大于等于k，那么首先进行广度优先遍历，dif = 1..9，即往7的左右两边遍历，显然先替换大于7的会使得字典序更小，因此先7+dif，再计算7-dif，直到数字7的个数==k，然后记录原号码中每个数字中有多少个数要替换为7。然后从左往右替换大于7的数字，  
再从右往左替换小于7的数字即可。

#include<iostream>
    #include<queue>
    #include<string>
    #include<algorithm>
    #include<sstream>
    using namespace std;
    int main(){
     vector<int> number(10, 0);
     vector<int> times(10, 0);
     string ansstr;
    int ansi;
    int n, k;
    int anscost = -1;
    string str;
    bool flag = false;
    cin>>n>>k;
    char c;
    for(int i = 0; i < n; i++){
    cin>>c;
    str.push_back(c);
    number[c-'0']++;
    if(number[c-'0'] >= k){
    flag = true;
    }
    }
    if(flag) cout<<str<<endl;
    else{
    for(int i = 0; i <= 9; i++){
    for(int ii = 0; ii <= 9; ii++) times[ii] = 0;
    if(number[i] == 0) continue;
    int tmpcost = 0;
    int t = number[i];
    int dif = 1;
    while(t < k){
    if(i+dif <= 9){
    if(number[i+dif] + t >= k){
    times[i+dif] = k-t;
    tmpcost += (dif)*(k-t);
    break;
    }
    else{
    times[i+dif] = number[i+dif];
    tmpcost += (dif)*number[i+dif];
    t += number[i+dif];
    }
    }
    if(i-dif >= 0){
    if(number[i-dif] + t >= k){
    times[i-dif] = k-t;
    tmpcost += dif*(k-t);
    break;
    }
    else{
    times[i-dif] = number[i-dif];
    tmpcost += number[i-dif];
    t += number[i-dif];
    }
    }
    dif++;
    }
    string sstr(str);
    for(int j = 0; j < sstr.size(); j++){
    int ttt = sstr[j]-'0';
    if(sstr[j]-'0' > i && times[(int)(sstr[j]-'0')] > 0){
    times[ttt] = times[(int)(sstr[j]-'0')]- 1;
    sstr[j] = '0'+i;
    }
    }
    cout<<" "<<endl;
    for(int j = sstr.size()-1; j >= 0; j--){
    if(sstr[j]-'0' < i && times[(int)(sstr[j]-'0')] > 0){
    times[(int)(sstr[j]-'0')]--;
    sstr[j] = '0'+i;
    }
    }
    if(anscost == -1){
    anscost = tmpcost;
    ansi = i;
    ansstr = sstr;
    }
    else if(anscost > tmpcost){
    ansi = i;
    anscost = tmpcost;
    ansstr = sstr;
    
    }
    else if(anscost == tmpcost){
    anscost = tmpcost;
    if(ansstr > sstr){
    ansi = i;
    ansstr = sstr;
    }
    }
    }
    cout<<anscost<<endl;
    cout<<ansstr<<endl;
    }
    
    }