拼多多提前批（7月28号笔试题
? ? ? 看到昨天同學(xué)拼多多的筆試題，今天試著寫了寫，因為自己并沒有參加過筆試，寫出來的只是我自己能想到的測試用例都過了的，如果有錯誤，歡迎各位大神指出，僅僅是提供一個解題的想法。而且因為自己基本功不夠，寫出的程序基本事件復(fù)雜度都比較高，也歡迎大神提出優(yōu)化改進的方法。
你的任務(wù)是從數(shù)組A中找到這個數(shù)字，并從數(shù)組B中選取一個數(shù)將其替換，使得數(shù)組A是完全嚴格升序排列的。(嚴?格升序排列，即不允許相鄰兩個為相同的數(shù))
請找出數(shù)組B中滿足要求的最大數(shù)字，并輸出最終有序的數(shù)組。如果不存在就輸出NO.?
輸入描述:
?????? 共兩行，第一行是數(shù)組A，第二行是數(shù)組B，元素之間用空格分隔(數(shù)組A的長度，數(shù)組B的長度<?100)
輸出描述:
?????? 共一行，為最終有序的數(shù)組。不存在則輸出NO
示例1
輸入
1?????? 3?????? 7?????? 4?????? 10
2? ? ? 1?????? 5?????? 8?????? 9
輸出：
1? ? ? 3?????? 7?????? 9?????? 0
輸入:
20? ? ?1? ? ? ?23
50? ? ? 26???? 7
輸出：
NO
?
? ? ? ? ?解題思路：這個的解題思路的重點在于改變A[index]和A[index-1]都有可能組成一個升序數(shù)組，其中index是定位到的A[index]<A[index-1]的位置。有一點值得注意，改變A[index]如果有值的話肯定會大于A[index-1]，只有在A[index]沒有符合要求值的情況才會考慮A[index-1]，可以減少時間。
import java.util.Scanner;
public class First {
??? public static void main(String ars[]){
??????? Scanner scanner=new Scanner(System.in);
??????? int[] arrA = parseInts(scanner.nextLine().split(" "));
??????? int[] arrB = parseInts(scanner.nextLine().split(" "));
??????? int res[]=changeToSort(arrA,arrB);
??????? if(res==null){
??????????? System.out.println("No");
??????? }else{
??????????? for(int r:res){
??????????????? System.out.print(r+" ");
??????????? }
??????? }
??? }
??? public static int[] changeToSort(int A[],int B[]){
??????? if(A==null||B==null||A.length==0||B.length==0)
??????????? return null;
??????? int index=Integer.MAX_VALUE;
??????? for(int i=1;i<A.length;i++){
??????????? if(A[i]<A[i-1]){
??????????????? index=i;
??????????????? break;
??????????? }
??????? }
??????? int max=Integer.MIN_VALUE;
??????? if(index==A.length-1){
??????????? for(int i=0;i<B.length;i++){
??????????????? if(B[i]>A[index-1]&&max<B[i])
??????????????????? max=B[i];
??????????? }
??????????? if(max==Integer.MIN_VALUE){
??????????????? index--;
??????????????? for(int i=0;i<B.length;i++){
??????????????????? if(B[i]>max&&B[i]>A[index-1]&&B[i]<A[index+1])
??????????????????????? max=B[i];
??????????????? }
???????????????
??????????? }
??????? }else{
??????????? for(int i=0;i<B.length;i++){
??????????????? if(B[i]>A[index-1]&&B[i]<A[index+1]&&max<B[i])
??????????????????? max=B[i];
??????????? }
??????????? if(max==Integer.MIN_VALUE&&A[index]<A[index+1]){
??????????????? index--;
??????????????? for(int i=0;i<B.length;i++){
??????????????????? if(index-1>0){
??????????????????????? if(B[i]>A[index-1]&&B[i]<A[index+1]&&max<B[i])
??????????????????????????? max=B[i];
??????????????????? }else{
??????????????????????? if(B[i]<A[index+1]&&max<B[i])
??????????????????????????? max=B[i];
??????????????????? }
??????????????? }
??????????? }
??????? }
??????? if(max==Integer.MIN_VALUE){
??????????? return null;
??????? }
??????? A[index]=max;
????? ??return A;
??? }
//這邊只是一個函數(shù)轉(zhuǎn)換，把字符串變成int類的數(shù)組
??? private static int[] parseInts(String[] strArr) {
??????? if (strArr == null || strArr.length == 0) {
??????????? return new int[0];
??????? }
??????? int[] intArr = new int[strArr.length];
??????? for (int i = 0; i < intArr.length; i++) {
??????????? intArr[i] = Integer.parseInt(strArr[i]);
??????? }
??????? return intArr;
??? }
}
?
?
2.給定一個字符串?dāng)?shù)組(字符串長度和數(shù)組的長度均大于1且小于1024)，所有字符均為大寫字母。請問，給定的字符串?dāng)?shù)組是否能通過更換數(shù)組中元素的順序，從而首尾相連，形成一個環(huán)，環(huán)上相鄰字符串首尾銜接的字符相同。
輸入描述:
???????? 一行輸入，空格分隔，表示字符串?dāng)?shù)組。
輸出描述:
???????? 一行輸出，?返回true或者false,表示是否可以形成環(huán)。
例：
輸入：
CAT ???TIGER?? RPC
輸出：
true
輸入：
CAT?? RPC
輸出：
False
?
這個題我的想法是只要每一個字符串可以找到與之相連的字符串并且和別人找到的不重復(fù)就可以，所以用了兩個循環(huán)
import java.util.Scanner;public class Second {public static void main(String ars[]){Scanner scanner=new Scanner(System.in);String string=scanner.nextLine();String[] str=string.split(" ");System.out.println(test(str));}public static boolean test(String strs[]){int length=strs.length;//這邊把數(shù)組里面少于1的都算作false；if(length<=1||strs==null)return false;if(length==2)return strs[0].charAt(strs[0].length()-1)==strs[1].charAt(0)&&strs[1].charAt(strs[0].length()-1)==strs[0].charAt(0);int[] nums=new int[length];boolean[] isEmpty=new boolean[length];for(int i=0;i<length;i++){nums[i]=-1;}for(int i=0;i<length;i++){int lengthTemp=strs[i].length()-1;for(int j=0;j<length;j++){//如果首尾可以相連且沒有j沒有指向i（主要是為了防止兩個形成循環(huán)）// 且j沒有被別的指向過（防止幾個指向同一個）?????????? if(nums[j]!=i&&j!=i&&!isEmpty[j]&&strs[i].charAt(lengthTemp)==strs[j].charAt(0)){nums[i]=j;isEmpty[j]=true;break;}}}for (int i=0;i<length;i++){if(!isEmpty[i]){return false;}}return true;}}? ? ? ? ?3? 多多雞在公司負責(zé)一個分布式任務(wù)執(zhí)行平臺的維護。夏天到了，平臺的服務(wù)器都因中暑而無法執(zhí)行任務(wù)了。所以多多雞必須自己手動來執(zhí)行每個任務(wù)!
??????現(xiàn)在一共有N個待執(zhí)行的任務(wù)，每個任務(wù)多多雞需要P1的時間完成執(zhí)行。同時，任務(wù)之間可能會有一些依賴關(guān)系。比如任務(wù)1可能依賴任務(wù)2和任務(wù)3，那么任務(wù)1必須在任務(wù)2和任務(wù)3都執(zhí)行完成后才能執(zhí)行。
??????多多雞只有一個人，所以同時只能執(zhí)行一個任務(wù)，并且在任務(wù)完成之前不能暫停切換去執(zhí)行其他任務(wù)。?為了提升平臺用戶的使用體驗，多多雞希望最小化任務(wù)的平均返回時長。一個任務(wù)的返回時長定義為任務(wù)執(zhí)行完成時刻減去平臺接收到該任務(wù)的時刻。在零時間，所有N個任務(wù)都已經(jīng)被平臺接收。請你幫多多雞安排下任務(wù)執(zhí)行順序，使得平均返回時長最
小。
?輸入描述:
??????第一行包含2個正整數(shù)N、M，分別表示任務(wù)數(shù)量以及M個任務(wù)依賴關(guān)系。
??????第二行包含N個正整數(shù)，第i(1<=1<=N)個數(shù)表示第i個任務(wù)的處理時間Pi。
????接下來的M行，每行表示一個任務(wù)依賴關(guān)系。每行包含2個整數(shù)Ai(1<=Ai<=N)、B1(1<=Bi<=N)，表示第B1個任務(wù)依賴于第A1個任務(wù)。數(shù)據(jù)保證不會出現(xiàn)循環(huán)依賴的情況。數(shù)據(jù)范圍:
???????? 1<=N<=1000
1<=M<=50000
1<=P1<=10000
?輸出描述:
??????輸出一行，包含N個整數(shù)(兩兩之間用一個空格符分隔)，其中第i(1<=i<=N)個整數(shù)表示多多雞執(zhí)行的第i個任務(wù)的編號。若有多種可行方案,則輸出字典序最小(優(yōu)先執(zhí)行編號輪小的任務(wù)的方案。
例：
輸入：
5?? 6
1? ?2? ? 1? ? ?1? ? 1? ? ? ? ? ? ? ? ? ? ?
1? ?2
1? ?3??????
1? ?4
2? ?5
3? ?5
4? ? 5
輸出：
1? ? ? ? 3?????? 4?????? 2?????? 5?? （輸出的是執(zhí)行順序）；
解題思路：這就是個優(yōu)先級加編號和時間的問題。先對所有的排優(yōu)先級，在優(yōu)先級相同的情況下選出時間短的和編號在前的。
import java.util.ArrayList;import java.util.List;import java.util.Scanner; public class Third {public static void main(String args[]){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int times[]=new int[N];int dependencies[][]=new int[M][2];for(int i=0;i<N;i++){times[i]=sc.nextInt();}for(int i=0;i<M;i++){for(int j=0;j<2;j++){dependencies[i][j]=sc.nextInt();}}int result[]=runnSort(N,M,times,dependencies);for(int re:result)System.out.print(re+" ");}public static int[] runnSort(int n,int m,int[] times,int[][] des){if(n<=0||m<=0)return null;boolean[][] isDes=new boolean[n][n];int res[]=new int[n];//確定依賴關(guān)系，我這邊定義的是，如果i->(依賴)j，則isDes[i][j]=truefor(int i=0;i<m;i++){isDes[des[i][1]-1][des[i][0]-1]=true;}int counts[]=new int[n];//確定優(yōu)先級，依賴越多，優(yōu)先級的數(shù)字越大，優(yōu)先級越低for(int i=0;i<n;i++){counts[i]=1;for (int j=0;j<n;j++){if(j!=i&&isDes[i][j])counts[i]++;}}int key=1;int k=0;//length用來記錄以及處理了哪些，等全部處理完跳出循環(huán)int length=n;while (length>0){//肯定有優(yōu)先級為1的，不然沒法開始List<Integer>list=new ArrayList<>();for (int i=0;i<n;i++){if(counts[i]==key)list.add(i);}key++;if(list.size()==0)continue;length-=list.size();//以下是在優(yōu)先級相同的情況下按照時間短和編號順序排列while (list.size()>0){int max=Integer.MAX_VALUE,index=-1;for(int i=0;i<list.size();i++){if(max>times[list.get(i)]){max=times[list.get(i)];index=i;}}res[k++]=list.get(index)+1;list.remove(index);}}return res;}}?
?4. ??多多雞寶寶在玩搭積木游戲。有N個長方體積木，每個積木的高都是1，長寬都為Li，重量為Wi。
??????現(xiàn)在多多雞寶寶想要用這些積木搭一個高高的金字塔。他打算金字塔的每一層是由且僅由一塊積木組成，同時每一層的積木邊長都嚴格比在其下方的積木小。
??????在多次嘗試之后，多多雞寶寶發(fā)現(xiàn)每塊積木只能承受自身重量的7倍重量,一若超過7倍自重，搭建的金字塔會因此變得不穩(wěn)定。具體來說即:對于每一塊積木，在其上方的積木重量之和必須小于等于其自重的7倍。
??????多多雞寶寶想請你幫他計算一下最高可以搭一個多高的金字塔?
?數(shù)據(jù)范圍:
?1<=N<=100
1<=Li<=1000
1<=Wi<=1000
輸入描述:
?第一行包含1個正整數(shù)N，表示積木的數(shù)量。
第二行包含N個正整數(shù)，第i個數(shù)表示第i個積木的長度Li。
第三行包含N個正整數(shù)，第i個數(shù)表示第i個積木的重量Wi
輸出描述：
輸出占一行，近包含一個整數(shù)，表示可以搭出金字塔的最高高度。
例：
輸入：
10
1? ? 2?????? 3?????? 4?????? 5?????? 6?????? 7?????? 8?????? 9? ? ? 10
1? ? 1? ? ? ?1? ? ? ? 1? ? ? ?1? ? ? ? 1? ? ? 1? ? ? ?1? ? ? ? 1? ? ? 10? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
輸出：
9
解題思路：我個人覺得這個跟動態(tài)規(guī)劃里面的信封問題類似，甚至說他比信封問題更簡單，信封問題要考慮長和寬，由于這個長寬是一致的，考慮長就可以。他在信封問題的改變在于多加了一個重量的參數(shù)，考慮長和寬就變成了考慮體積和重量。這個題目可以從上面往下面堆，這樣做的好處就是你可以僅僅考慮當(dāng)前塊能不能承受，而不用考慮前一塊。因為前一塊能夠成立的話，在計算他的時候肯定就已經(jīng)確定了他可以承受前面的重量。用動態(tài)規(guī)劃來做。
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Four {public static void main(String args[]){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int work[][]=new int[n][2];for(int i=0;i<n;i++){work[i][0]=sc.nextInt();}int wi[]=new int[n];for(int i=0;i<n;i++){work[i][1]=sc.nextInt();}System.out.println(Ta(work));}public static int Ta(int[][] arr ){if(arr==null&&arr.length==0&&arr[0].length==0)return 0;int length=arr.length;//對每個積木進行排序，先按照邊長排序，邊長相同的按照重量排序Arrays.sort(arr, new Comparator<int[]>(){public int compare(int[] o1,int [] o2){//判斷第一個元素是否相等if (o1[0] == o2[0]) {return o1[1] - o2[1];} else {return o1[0] - o2[0];}}});//一個二維數(shù)組，nums[i][0]用來記錄當(dāng)前最多疊了幾層，nums[i][1]用來表示當(dāng)前積木所有的重量int nums[][]=new int[length][2];for(int i=0;i<length;i++){nums[i][0]=1;nums[i][1]=arr[i][1];for(int j=0;j<i;j++){if(nums[j][1]<=arr[i][1]*7&&nums[j][0]+1>nums[i][0]){nums[i][0]=nums[j][0]+1;nums[i][1]=nums[j][1]+arr[i][1];//下面的主要是為了替換得到更少的重量。}else if(nums[j][0]+1==nums[i][0]&&nums[j][1]+arr[i][1]<nums[i][1]){nums[i][1]=nums[j][1]+arr[i][1];}}}int max=nums[0][0];for(int i=0;i<length;i++){if(nums[i][0]>max)max=nums[i][0];}return max;}} ?
?
?
?
總結(jié)
以上是生活随笔為你收集整理的拼多多提前批（7月28号笔试题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 离线语音交互技术路线之语音合成(TTS)
- 下一篇： 盾与战锤（前缀和）