美团研发工程师编程题-2016年

编程题

1、请设计一个算法，给一个字符串进行二进制编码，使得编码后字符串的长度最短。

输入描述:

每组数据一行，为待编码的字符串。保证字符串长度小于等于1000。

输出描述:

一行输出最短的编码后长度。

输入例子:

MT-TECH-TEAM

输出例子:

33

2、对于一个由0..n的所有数按升序组成的序列，我们要进行一些筛选，每次我们取当前所有数字中从小到大的第奇数位个的数，并将其丢弃。重复这一过程直到最后剩下一个数。请求出最后剩下的数字。

输入描述:

每组数据一行一个数字，为题目中的n(n小于等于1000)。

输出描述:

一行输出最后剩下的数字。

输入例子:

500

输出例子:

255

3、有一个二维数组(n*n),写程序实现从右上角到左下角沿主对角线方向打印。

给定一个二位数组arr及题目中的参数n，请返回结果数组。

[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]],4

返回：[4,3,8,2,7,12,1,6,11,16,5,10,15,9,14,13]

4、在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于2)，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用实践复杂度低的方法实现。

给定价格序列prices及它的长度n，请返回最大收益。保证长度小于等于500。

[10,22,5,75,65,80],6

返回：87

参考答案

1、参考代码：

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>
#define MAX 1000 
using namespace std; 
int main()
{
    char newString[MAX] = {0};
    while(cin>>newString)
    {
        int i, j;
        int countNum = 0;     //统计不同字符个数
        int sum = 0;              //记录编码后的长度
        int first = 0, second = 0;      //分别记录队列的最小两个值
        int len = strlen(newString);
        priority_queue <int, vector<int>, greater<int> > huffmanQueue;   //定义小值优先级高的队列
         sort(&newString[0], &newString[len]);
     
         for(i = 0; i < len; )
         {
                 j = i;
                 while((j < len)&&(newString[j] == newString[i]))   
                {
                      j++;
                }
               huffmanQueue.push(j - i);   //将字符newString[i]的个数压入队列
                i = j;
               countNum++;
        }
        for(i = 0; i < countNum - 1; i++)  //霍夫曼编码步骤
        {
              first = huffmanQueue.top();
              huffmanQueue.pop();
              second = huffmanQueue.top();
              huffmanQueue.pop();
              huffmanQueue.push(first + second);  
              sum += first + second;
        }
        cout<<sum<<endl;
    }//while
    return 0;
} 

2、参考代码：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i <= n; i ++ )
                list.add(i);
            while (list.size() != 1) {
                // 从0开始list移除一次,i再加一次,i始终指向奇数位
                for (int i = 0; i < list.size(); i = i + 1)
                    list.remove(i);
            }
            System.out.println(list.get(0));
        }
    }
}

3、参考代码：

/**
 *  题意很简单，主要是边界的处理：
 *   1. 沿着主对角线打印，所以每次打印之后x与y都要加1，直到x或y超出边界。
 *   2. 每轮遍历的起始点，是遵循(0,n-1)...（0,0）...（n-1,0）。
  *           也就是y先减小到0，然后x增加到n-1。所以遍历的终止条件是startX>=n。 *
 **/
import java.util.*;
 
public class Printer {
    public int[] arrayPrint(int[][] arr, int n) {
        // write code here
        int[] res = new int[n*n];
        int index = 0;
        int startX = 0;
        int startY = n-1;
        while(startX<n){
            int x = startX;
            int y = startY;
            while(x<n&&y<n)
                res[index++]=arr[x++][y++];
            if(startY>0)
                startY--;
            else
                startX++;
        }
        return res;
    }
}

4、参考代码：

import java.util.*;
//已通过测试，发现好多人都不喜欢写注释，喜欢直接粘代码，
public class Stock {
    //简单说一下我的做题思路，
    //其实我的原始思路是用二分法做，先把数组从中间分开，
    //然后在两部分中分别找最大差值，然后保存最大差值进行相加
    //完事之后，将中间的指针，也就是进行二分的指针向右移或者向左移
    //又划分成了两部分，依次找最大差值，
    //直到最后两个差值之和为最大值，返回最大值。
    public int maxProfit(int[] prices, int n) {
        int temp1 = 0,temp2 = 0 , temp3 = 0, l = 0;
        //既然从中间划分两部分，之后又要在往前划分和往后划分，
        //所以直接一开始就从最前面开始划分，将数组划分两部分
        while(l<n){
            //l变量用来划分数组
            //第一个for循环寻找的最大差值，仅限于l变量之前。
             for(int i = 0 ; i < l+1 ; i++){
                for(int j = i+1 ; j < l+1 ; j++){
                    if(prices[j]-prices[i]>temp1){
                        temp1 = prices[j]-prices[i];
                    }
                }
            }
            //第二个for循环寻找的最大差值，仅限于l变量之后。
            for(int i = l+1 ; i < n ; i++){
                for(int j = i+1 ; j < n ; j++){
                    if(prices[j]-prices[i]>temp2){
                        temp2 = prices[j]-prices[i];
                    }
                }
            }
            //判断两个变量之和是否是最大差值
            if(temp2+temp1>temp3){
                 temp3 = temp2+temp1 ;
            }
            //此处一定要将两个部分的最大差值重新置0；
            //否则结果会出错。因为它里面存有之前的最大差值
            //如果不重置，那么最后在判断的时候会重复计算。
            temp2 = 0 ;
            temp1 = 0;
            l++;
        }
        return temp3;
    }
}