美團2018校園招聘內推筆試程式碼分享

美團2018校園招聘內推筆試程式碼分享

因為被美團的大佬翻牌子了,所以內推直接免筆試進面試,恰巧今天遇到同學們答美團的筆試題,熱愛OJ的我就參與了一發,戰果還不錯,2道題都輕鬆AC了。

接下來就和大家分享一下我的做題思路和程式碼,我覺得第一題還有改進的地方,希望大家不吝賜教,我也今晚好好想想有沒有更優秀的解法。

首先是第一題:

序列中任意個連續的元素組成的子序列稱為該序列的子串。

現在給你一個序列P和一個整數K,詢問元素和是K的倍數的子串的最大長度。

樣例輸入:

[1,2,3,4,5],整數K,滿足條件的子串是{5},{2,3},{1,2,3,4},{1,2,3,4,5}。

那麼答案就是5。如果這樣的子串不存在,就輸出0.

這道題和今年藍橋杯上面的一道題很想(雖然我也沒參加,只是自己隨便做了做它的題)。適用動態規劃,維護一個dp矩陣,每個元素是前面元素和%K的結果,注意,我們計算下一個元素時,只需要根據遞推公式: dp[i] = (dp[i-1] arr[i])%K;即可。比如[1,2,3,4,5]就會得到[1,3,1,0,0]。

這時候我們再根據這個dp矩陣來計算最大長度,dp矩陣中元素一定是0,1,…K-1.

先看0.為0就代表前面的元素和正好是K的倍數,那麼我們尋找陣列中最後一個0的位置,就是dp[i]=0的最長子串長度-1.

然後看1,我們找dp矩陣中第一1的位置j和最後一個1之間的位置k的差,這個差值就是dp[i]=1的最長子串長度。相當於前k項和-前j項和正好是K的倍數。

依次類推到K-1,每次都維護最長距離max。最終輸出。

同時加入arr.length==0的判斷。

package com.nowcoder.java;
public class Meituan01 {
public static void main(String[] args) {
int[] arr={1,2,3};
int K = 5;
System.out.println(cal(arr,K));
}
public static int cal(int[] arr,int K){
if(arr.length==0)
return 0;
int max=0;
int[] dp = new int[arr.length];
dp[0] = arr[0]%K;
for(int i=1;i<dp.length;i  ){
dp[i]=(dp[i-1] arr[i])%K;
}
for(int i=0;i<dp.length;i  ){
if(dp[i]==0)
max=i 1;
}
for(int i=1;i<K;i  ){
int pre = 0;
int back = dp.length-1;
while(dp[pre]!=i && pre<back)
pre  ;
while(dp[back]!=i && back>pre)
back--;
int len=back-pre;
if(len>max)
max=len;
}
return max;
}
}

第二題:

太長了我直接貼圖。

這道題乍看很難,其實道理只有一個!

那就是:最大的那一個組的人數一定要比其餘組的和大於等於即可!

package com.nowcoder.java;
import java.util.Arrays;
public class Meituan02 {
public static void main(String[] args) {
int N=2;
int[] arr = new int[]{10,10,20};
System.out.println(check(arr,N));
}
public static boolean check(int[] arr,int N){
if(N<=1)
return false;
Arrays.sort(arr);
int sum = 0;
for(int i=0;i<N-1;i  ){
sum =arr[i];
}
if(sum>=arr[N-1])
return true;
else{
return false;
}
}
}

程式碼如上,

以上