【美團】2016研發工程師

[程式設計題]最大內插補點

有一個長為n的數組A，求滿足0≤a≤b<n的A[b]-A[a]的最大值。

給定數組A及它的大小n，請傳回最大內插補點。

測試樣例：

[10,5],2      

傳回：0      

簡單題，窮舉

import java.util.*;
 
public class LongestDistance {
    public int getDis(int[] A, int n) {
        // write code here
        int max = 0;
        if (n == 1) {
            return 0;
        } else {
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    int temp = A[j] - A[i];
                    max = Math.max(temp, max);
                }
            }
        }
        return max;
    }
}
           

[程式設計題]棋子翻轉

在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]]      

簡單題，一開始沒有讀懂題意，牛客網大佬的答案

連結：https://www.nowcoder.com/questionTerminal/0b5ab6cc51804dd59f9988ad70d8c4a0
來源：牛客網

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

[程式設計題]拜訪

現在有一個城市銷售經理，需要從公司出發，去拜訪市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他隻能在左右中選擇一個方向，在上下中選擇一個方向，現在問他有多少種方案到達商家位址。

給定一個地圖map及它的長寬n和m，其中1代表經理位置，2代表商家位置，-1代表不能經過的地區，0代表可以經過的地區，請傳回方案數，保證一定存在合法路徑。保證矩陣的長寬都小于等于10。

測試樣例：

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

傳回：2      

重點，回溯法，還是有點懵，參考大佬的做法

https://www.nowcoder.com/questionTerminal/12cbdcdf5d1e4059b6ddd420de6342b6

import java.util.*;
  
public class Visit {
  
    static int count = 0;
    public static int countPath(int[][] map, int n, int m) {
        count = 0;
        // write code here
        int x1 = 0,y1 = 0,x2 = 0,y2 = 0;
        int [][]visit = new int[n][m];
        for (int i = 0;i < n;i ++) {
            for (int j = 0;j < m;j ++) {
                if (map[i][j] == 1) {
                    x1 = i;
                    y1 = j;
                }
                if (map[i][j] == 2) {
                    x2 = i;
                    y2 = j;
                }
            }
        }
        int [][]pos = new int[2][2];
        if (x1 <= x2) {
            pos[0][0] = 1;
            pos[0][1] = 0;
        }else {
            pos[0][0] = -1;
            pos[0][1] = 0;
        }
        if (y1 <= y2) {
            pos[1][0] = 0;
            pos[1][1] = 1;
        }else {
            pos[1][0] = 0;
            pos[1][1] = -1;
        }
        dfs(map, x1, y1, visit, pos);
        return count;
    }
    public static void dfs(int[][] map, int row, int col, int [][]visit, int [][]pos) {
  
        if (map[row][col] == 2) {
            count ++;
            return;
        }
  
        for (int i = 0;i < pos.length;i ++) {
            int x = row + pos[i][0];
            int y = col + pos[i][1];
            if (x >= map.length || x < 0 || y >= map[0].length || y < 0)
                continue;
            if (map[x][y] != -1 && visit[x][y] == 0) {
                visit[x][y] = 1;
                dfs(map, x, y, visit, pos);
                visit[x][y] = 0;
            }
        }
    }
}
           

[程式設計題]直方圖内最大矩形

有一個直方圖，用一個整數數組表示，其中每列的寬度為1，求所給直方圖包含的最大矩形面積。比如，對于直方圖[2,7,9,4],它所包含的最大矩形的面積為14(即[7,9]包涵的7x2的矩形)。

給定一個直方圖A及它的總寬度n，請傳回最大矩形面積。保證直方圖寬度小于等于500。保證結果在int範圍内。

測試樣例：

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

傳回：14      

周遊窮舉，記下最大值

import java.util.*;
 
public class MaxInnerRec {
    public int countArea(int[] A, int n) {
        // write code here
        int minheight=0;
        int area=0;
        for(int i=0;i<n;i++){
            minheight=A[i];
            for(int j=i+1;j<n;j++){
                minheight=Math.min(A[j], minheight);
                area=Math.max(area, minheight*(j-i+1));
            }
        }
        return area;
    }
}
           

[程式設計題]字元串計數

求字典序在s1和s2之間的，長度在len1到len2的字元串的個數，結果mod 1000007。

輸入描述:

每組資料包涵s1（長度小于100），s2（長度小于100），len1（小于100000），len2（大于len1，小于100000）      

輸出描述:

輸出答案。      

示例1

輸入

ab ce 1 2      

輸出

56      

還是沒有弄太懂，也許可以轉換成26進制做

[程式設計題]平均年齡

已知某公司總人數為W，平均年齡為Y歲(每年3月末計算，同時每年3月初入職新人)，假設每年離職率為x，x>0&&x<1,每年保持所有員工總數不變進行招聘，新員工平均年齡21歲。

從今年3月末開始，請實作一個算法，可以計算出第N年後公司員工的平均年齡。(最後結果向上取整)。

輸入描述:

輸入W Y x N      

輸出描述:

輸出第N年後的平均年齡      

示例1

輸入

5 5 0.2 3      

輸出

15      

注意：每一年新招人的時候，老員工都長了一歲，題目的意思是最後一次向上取整，我的代碼每次計算都向上取整了，不改了

錯誤的每次都向上取整的代碼：

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        getAge();
    }
 
    public static void getAge(){
        Scanner scanner=new Scanner(System.in);
        //公司人數
        int W=scanner.nextInt();
        //平均年齡
        int Y=scanner.nextInt();
        //離職率
        double rate=scanner.nextDouble();
        //年數
        int year=scanner.nextInt();
         
        int age=Y;
        for(int i=0;i<year;i++){
            age=ageMethod(W, age, rate);
        }
        System.out.println(age);
    }
    //具體計算方法
    public static int ageMethod(int W,int Y,double rate){
        //離職人數=招聘人數
        int newPeople=(int) (rate*W);
        //新平均年齡，過了一年剩下的員工都長了一歲
        int sumAge=(Y+1)*(W-newPeople)+21*newPeople;
        int newAge=0;
        if(sumAge%W==0){
            newAge=sumAge/W;
        }else{
            //向上取整
            newAge=sumAge/W+1;
        }
        return newAge;
    }
 
}