美团笔试3道多选+算法题2.92/4

第一题 91%

package meituan;

import java.nio.file.Path;import java.util.ArrayList;import java.util.List;import java.util.Scanner;

public class test1 {public static void main(String[] args){Scanner in = new Scanner(System.in);int enemysNum = in.nextInt();int a = in.nextInt();int b =in.nextInt();List<int[]> pos = new ArrayList<>();for(int i=0 ; i<enemysNum ; ++i){int x = in.nextInt();int y = in.nextInt();pos.add(new int[] {x,y});}

    //System.out.println("d");
    int ans=0;
    for(int i=0 ; i<enemysNum ; ++i){
        int count=1;
        List<Integer> list = new ArrayList<>();
        list.add(i);
        for(int j=0 ; j<enemysNum ; ++j){
            if(j==i){
                continue;
            }
            int k=0;
            for(; k<list.size() ; ++k){
                if(Math.abs(pos.get(list.get(k))[0]-pos.get(j)[0])>a || Math.abs(pos.get(list.get(k))[1]-pos.get(j)[1])>b){
                    break;
                }
            }
            if(k==list.size()){
                ++count;
                list.add(j);
            }


        }
        ans = Math.max(ans, count);
    }
    System.out.println(ans);
 }
}

第二题 A

package meituan;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class test2 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[len];
        for(int i=0 ; i<len ; ++i){
            nums[i] = in.nextInt();
        }
        int maxLen=0;
        for(int i=0 ; i<len ; ++i){
            Set<Integer> set = new HashSet<>();
            for(int j=i ; j<len ; ++j){
                if(!set.contains(nums[j])){
                    set.add(nums[j]);
                    if(set.size()>k){
                        maxLen = Math.max(j-i, maxLen);
                        break;
                    }
                }
            }
        }
        System.out.println(maxLen);


    }
}

第三题：91%

package meituan;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class test3 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = s.length();
        int start;

        List<int[]> wrongPos = new ArrayList<>();
        start = n/2;
        int left=start-1, right=start+1;
        if(n%2 == 0){
            right = start;
        }
        while(left>=0 && right<n){
            if(s.charAt(left) != s.charAt(right)){
                wrongPos.add(new int[]{left, right});
            }
            --left;
            ++right;
        }
        //System.out.println(wrongPos.get(0)[0] +" "+ wrongPos.get(0)[1] );
        if(wrongPos.size() == 0){
            StringBuilder sb = new StringBuilder(s);
            for(int i=0 ; i<n ; ++i){

                if(sb.charAt(i) > 'a'){
                    sb.setCharAt(i, 'a');
                    sb.setCharAt(n-i-1,'a');
                    break;
                }
            }
            System.out.println(sb.toString());
        }

        else if(wrongPos.size() == 1){
            StringBuilder sb = new StringBuilder(s);
            if(sb.charAt(wrongPos.get(0)[0]) > sb.charAt(wrongPos.get(0)[1])){
                sb.setCharAt(wrongPos.get(0)[0], sb.charAt(wrongPos.get(0)[1]));
            }
            else{
                sb.setCharAt(wrongPos.get(0)[1], sb.charAt(wrongPos.get(0)[0]));
            }
            if(n%2 == 1){
                sb.setCharAt(n/2, 'a');
            }
            System.out.println(sb.toString());
        }

        else{//两个不同的情况
            StringBuilder sb = new StringBuilder(s);
            if(sb.charAt(wrongPos.get(0)[0]) > sb.charAt(wrongPos.get(0)[1])){
                sb.setCharAt(wrongPos.get(0)[0], sb.charAt(wrongPos.get(0)[1]));
            }
            else{
                sb.setCharAt(wrongPos.get(0)[1], sb.charAt(wrongPos.get(0)[0]));
            }

            if(sb.charAt(wrongPos.get(1)[0]) > sb.charAt(wrongPos.get(1)[1])){
                sb.setCharAt(wrongPos.get(1)[0], sb.charAt(wrongPos.get(1)[1]));
            }
            else{
                sb.setCharAt(wrongPos.get(1)[1], sb.charAt(wrongPos.get(1)[0]));
            }

            System.out.println(sb.toString());
        }



    }
}

第四题 应该能A过，但是最后没编译成功，所以A了0~~~

package meituan;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class test4 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int money = in.nextInt();
        int y = in.nextInt();
        //System.out.println(num+" "+money+" "+y);

        List<int[]> goodsList = new ArrayList<>();
        for(int i=0 ; i<num ; ++i){
            int ori = in.nextInt();
            int pst = in.nextInt();
            goodsList.add(new int[]{ori, pst});
        }

        dfs(goodsList, money, 0, y, 0, 0);
        System.out.println(maxGood+" "+minCost);


    }
    static int maxGood = 0;
    static int minCost = Integer.MAX_VALUE;

    public static void dfs(List<int[]> list, int money, int cost, int y, int gn, int index){

        if(y<0 || money<0 || index>list.size()){
            return;
        }
        System.out.println(gn +" "+cost+ " " +index+" "+y);
        if(money>=0){
            if(maxGood < gn){
                maxGood = gn;
                minCost = cost;
            }
            else if(maxGood == gn){
                minCost = Math.min(minCost, cost);
            }

        }
        System.out.println(maxGood +" "+minCost);
        System.out.println();

        if(index == list.size()){
            return;
        }
        dfs(list, money-list.get(index)[0], cost+list.get(index)[0], y, gn+1, index+1);
        if(y>0){
            dfs(list, money-list.get(index)[1], cost+list.get(index)[1], y-1, gn+1, index+1);
        }
    }
}