首页 > 8.15美团后端笔试
头像
zttttttt
编辑于 2021-08-15 20:09
+ 关注

8.15美团后端笔试

第一题直接排序,这里就不贴代码了
第二题 我的理解是从后往前找最长回文子串,写了两个辣鸡解法,a了64%
import java.util.Arrays;
import java.util.Scanner;

/**
 * description:
 * author:zt
 * date:2021-08-15
 */
public class A {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String text = in.next();
        System.out.println(solve2(text));
    }
    //判断原字符串是不是回文
    //不是 在判断该字符串结尾的最长回文子串是多长
    public static int solve(String text){
//        char[] c = text.toCharArray();
        int n = text.length();
        int[][] dp = new int[n][n];
        for (int i = n-1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                if (text.charAt(i)!=text.charAt(j)) dp[i][j] = -1; //不能构成回文
                else {
                    if (j-i<=2) dp[i][j] = j-i+1;
                    else {
                        if (dp[i+1][j-1]!=-1) dp[i][j] = dp[i+1][j-1]+2;
                        else dp[i][j] = -1;
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i][n-1]>max) max = dp[i][n-1];
        }
        return n-max;
    }

    public static int solve2(String text){
        if (check(text)) return 0;
        StringBuilder sb = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        sb.append(text);
        for (int i = 1; i <= text.length(); i++) {
            String s = text.substring(0, i);
            String s1 = sb2.append(s).reverse().toString();
            sb.append(s1);
            if (check(sb.toString()))  return i;
            sb = new StringBuilder();
            sb2 = new StringBuilder();
        }
        return text.length();
    }
    public static boolean check(String text){
        int L=0, R=text.length()-1;
        while (L<R){
            if (text.charAt(L)!=text.charAt(R)) return false;
            L++; R--;
        }
        return true;
    }
}
第三题两个list分别统计将往右走和往左走的节点,然后排序。两层遍历统计会相遇的最近的两个节点
import java.util.*;

/**
 * description:
 * author:zt
 * date:2021-08-15
 */
public class B {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < count; i++) {
            int index = in.nextInt();
            String dir = in.next();
            if (dir.equals("R")) right.add(index);
            else left.add(index);
            map.put(index,i);
        }
        for (int i : solve(left, right, map)) {
            System.out.println(i);
        }

    }

    //right向右走 left向左走
    public static int[] solve(ArrayList<Integer> left,ArrayList<Integer> right,Map<Integer,Integer> map){
        int l=left.size(), r=right.size();
        int len = left.size()+right.size();
        int[] res = new int[len];
        for (int i = 0; i < res.length; i++) {
            res[i] = -1;
        }
        Collections.sort(left);
        Collections.sort(right);
        for (int i = right.size()-1; i >= 0; i--) {
            if (right.get(i)>left.get(l-1)) {
                Integer index = map.get(right.get(i));
                res[index] = -1;
            }
            int target = -1;
            for (int j = left.size()-1; j >= 0; j--) {
                if (left.get(j)==Integer.MAX_VALUE) continue;
                else if (left.get(j)>right.get(i) && (left.get(j)-right.get(i))%2==0){
                    target = left.get(j);
                }
            }
            if (target!=-1) {
                int tmp1 = map.get(right.get(i));
                int tmp2 = map.get(target);
                int tmp3 = (target-right.get(i))/2;
                res[tmp1] = tmp3; res[tmp2] = tmp3;
                left.set(left.indexOf(target),Integer.MAX_VALUE);
            }
            else res[map.get(right.get(i))] = -1;
        }

        return res;
    }
}
第四题放弃了....直接看第五题,动态规划(类似跳台阶)
import java.util.Scanner;

/**
 * description:
 * author:zt
 * date:2021-08-15
 */
public class C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        int maxJump = in.nextInt();
        int[] take = new int[maxJump];
        String s = in.next();

        for (int i = 0; i < maxJump; i++) {
            take[i] = in.nextInt();
        }
        //take[i-1]表示跳i格
        int solve = solve(s.toCharArray(), take, s.length());
        System.out.println(solve);
    }

    public static int solve(char[] c,int[] take,int n){
        int[] dp = new int[n];
        for (int i = 0; i < dp.length; i++) {
            if (c[i]=='x') dp[i] = -1;
            else dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for (int i = 1; i < c.length; i++) {
            if (c[i]=='o'){
                for (int j = take.length; j > 0; j--) {
                    if (i>=j) {
                        if (dp[i-j]!= -1) dp[i] = Math.min(dp[i],dp[i-j]+take[j-1]);
                    }
                }
            }
        }
        return dp[n-1];
    }
}


全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐