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

编程题

1、有一个长为n的数组A，求满足0≤a≤b<n的A[b]-A[a]的最大值。

给定数组A及它的大小n，请返回最大差值。

[10,5],2

返回：0

2、在4x4的棋盘上摆满了黑白棋子，黑白两色的位置和数目随机其中左上角坐标为(1,1),右下角坐标为(4,4),现在依次有一些翻转操作，要对一些给定支点坐标为中心的上下左右四个棋子的颜色进行翻转，请计算出翻转后的棋盘颜色。

给定两个数组A和f,分别为初始棋盘和翻转位置。其中翻转位置共有3个。请返回翻转后的棋盘。

[[0,0,1,1],[1,0,1,0],[0,1,1,0],[0,0,1,0]],[[2,2],[3,3],[4,4]]

返回：[[0,1,1,1],[0,0,1,0],[0,1,1,0],[0,0,1,0]]

3、现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。

给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。

[[0,1,0],[2,0,0]],2,3

返回：2

4、有一个直方图，用一个整数数组表示，其中每列的宽度为1，求所给直方图包含的最大矩形面积。比如，对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7x2的矩形)。

给定一个直方图A及它的总宽度n，请返回最大矩形面积。保证直方图宽度小于等于500。保证结果在int范围内。

[2,7,9,4,1],5

返回：14

5、求字典序在s1和s2之间的，长度在len1到len2的字符串的个数，结果mod 1000007。

输入描述:

每组数据包涵s1（长度小于100），s2（长度小于100），len1（小于100000），len2（大于len1，小于100000）

输出描述:

输出答案。

输入例子:

ab ce 1 2

输出例子:

56

6、已知某公司总人数为W，平均年龄为Y岁(每年3月末计算，同时每年3月初入职新人)，假设每年离职率为x，x>0&&x<1,每年保持所有员工总数不变进行招聘，新员工平均年龄21岁。
从今年3月末开始，请实现一个算法，可以计算出第N年后公司员工的平均年龄。(最后结果向上取整)。

输入描述:

输入W Y x N

输出描述:

输出第N年后的平均年龄

输入例子:

5 5 0.2 3

输出例子:

15

参考答案

1、参考代码：

importjava.util.*;
  
public class LongestDistance {
    public int getDis(int[] A, int n) 
        int dis=0;
        if(n>1){
            int min=A[0];
            for(int i=1;i<n;i++){
                if(A[i]-min>dis){
                    dis=A[i]-min;
                }
                if(min>A[i]){
                    min=A[i];
                }
            }
        }
        return dis;
    }
}

2、参考代码：

public static int[][] flipChess(int[][] A, int[][] f) {
        // write code here
        for (int i = 0; i < f.length; i++) {
            int row = f[i][0] - 1;
            int col = f[i][1] - 1;
 
            if (row - 1 >= 0) {
                A[row - 1][col] = (A[row - 1][col] == 0) ? 1 : 0;
            }
 
            if (row + 1 <= 3) {
                A[row + 1][col] = (A[row + 1][col]) == 0 ? 1 : 0;
            }
 
            if (col - 1 >= 0) {
                A[row][col - 1] = (A[row][col - 1]) == 0 ? 1 : 0;
            }
 
            if (col + 1 <= 3) {
                A[row][col + 1] = (A[row][col + 1]) == 0 ? 1 : 0;
            }
        }
        return A;
    }

3、参考代码：

import java.util.*;
 
public class Visit {
    public int countPath(int[][] map, int n, int m) {
        // write code here
        int x1 = -1,y1 = -1;//经理的坐标
        int x2 = -1,y2 = -1;//商家的坐标
        for(int i = 0;i<n;i++){
            for(int j = 0; j<m;j++){
                if(map[i][j]==1){
                    x1 = j;
                    y1 = i;
                }else if(map[i][j]==2){
                    x2 = j;
                    y2 = i;
                }
            }
        }
        int xto = x1>x2?-1:1;//根据经理和商家的方向判断向左还是向右走
        int yto = y1>y2?-1:1;//向上还是向下
        //动态规划的思想 map[y][x]记录着经理到x,y点最多的路程数
        for(int y = y1;y!=(y2+yto);y+=yto){
            for(int x = x1;x!=(x2+xto);x+=xto){
                if(y==y1||x==x1){
                    map[y][x] = 1;
                    continue;
                }
                map[y][x] = map[y-yto][x]+map[y][x-xto];
            }
        }
        return map[y2][x2];
    }
}

4、参考代码：

/**
 * 类似快排的算法。计算当前子数组的最大矩阵面积，是子数组的长度*子数组的最小值。
 * 然后以最小值的下标为分割点，递归的计算左右子数组的最大矩阵面积。
 * 时间复杂度O(nlgn)，空间复杂度O(1)。 * 
 **/
public class MaxInnerRec {
    public int countArea(int[] A, int n) {
        // write code here
        return countCore(A,0,n-1);
    }
     
    private int countCore(int[] A , int left , int right){
        if(left>right)
            return 0;
        if(left==right)
            return A[left];
        int highIndex = findMin(A,left,right);
        int max = (right-left+1)*A[highIndex];
        max = Math.max(max, countCore(A,left,highIndex-1));
        max = Math.max(max, countCore(A,highIndex+1,right));
        return max;
    }
     
    private int findMin(int[] A , int left , int right){
        int min = left;
        for(int i=left+1;i<=right;i++)
        if(A[i]<A[min])
                min = i;
        return min;
    }
}

5、参考代码：

private static int process(String str1, String str2, int len1, int len2) {
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        long res = 0;
        for (int i = len1; i <= len2; i++) {
            char a = ch1[0];
            char b = ch2[0];
            res += (long) Math.pow(26, i - 1) * (b - a);
            long suma = 0;
            long sumb = 0;
            for (int j = 1; j < ch1.length; j++)// 找到比ch1剩余字符串小的字符串个数
            {
                suma = suma + (ch1[j] - 'a') * (long) Math.pow(26, i - 1 - j);
            }
            for (int j = 1; j < ch2.length; j++)// 找到比ch2剩余字符串小的字符串个数
            {
                sumb = sumb + (ch2[j] - 'a') * (long) Math.pow(26, i - 1 - j);
            }
            res = res + sumb - suma;
        }
        res--;
        res= res % 1000007;
        return (int) res;
    }

6、参考代码：

#include <iostream>
#include <cmath>
 
using namespace std;
void AverageAge()
{
    // 总人数为W，平均年龄为Y岁
    // 每年离职率为x，x>0&&x<1
    double W, Y, x, N;
 
    while(cin >> W >> Y >> x >> N)
    {
        while(N--)
        {
            Y = 21 * x + (1 - x) * (Y + 1);
        }
 
        cout << ceil(Y) << endl;
    }
}
 
int main()
{
    AverageAge();
    return 0;
}