美团笔试记录

2023-03-12 | 阅读：次

翻转字母

给定一个字符串，问最少修改其中多少个字母，可以让修改后的字符串不存在相邻的相同字母。

输出最小的修改次数

贪心

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        String s = in.nextLine();
        char[] c = s.toCharArray();
        int count=0;
        for(int i=1; i<c.length;i++) {
            if(c[i]==c[i-1]) {
                do {
                    c[i]= (char) (c[i]+1);
                } while (i<c.length-1&&c[i]==c[i+1]);
                count++;
            }
        }
        System.out.println(count);
    }
}

捡金币

在一个n*m方格型地图上，每个格子有若干枚金币，且染有蓝色或红色。小明起初在左上角（0，0）处，拥有0枚金币。他每次可以向下或者向右走一格，到达该格后可以获取该格上的所有金币。

如果他走到的格子和他所在的格子颜色不同，那么他需要支付k枚金币才能进行这次移动。如果颜色相同则不用支付。你需要保证任何时候小明的金币数不小于0.

他可以在任意位置结束他的旅程，求出他结束时可以有的最大金币数量。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in =new Scanner(System.in);
        int n=in.nextInt(),m=in.nextInt(),k=in.nextInt();
        boolean[][] isRed = new boolean[n][m];
        boolean[][] canNotPass = new boolean[n][m];

        int[][] gold =new int[n][m];
        in.nextLine();
        for(int i=0;i<n;i++) {
            String s = in.nextLine();
            for(int j=0;j<m;j++) {
                isRed[i][j]= s.charAt(j) == 'R';
            }
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                gold[i][j] = in.nextInt();
            }
        }
        int max = 0;
        int[][] dp=new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(i==0&&j==0) {
                    continue;
                }
                int up=0, left=0;
                boolean canGoUp=i>0,canGoLeft=j>0;
                if(i>0) {
                    if(isRed[i-1][j]!=isRed[i][j]) {
                        up-=k;
                    }
                    if(!canNotPass[i-1][j])
                        up+=dp[i-1][j];
                    if(canNotPass[i-1][j]||up<0) {
                        canGoUp=false;
                    }
                }
                if(j>0) {
                    if(isRed[i][j-1]!=isRed[i][j]) {
                        left-=k;
                    }
                    if(!canNotPass[i][j-1])
                        left+=dp[i][j-1];
                    if(canNotPass[i][j-1]||left<0) {
                        canGoLeft=false;
                    }
                }
                if(!canGoUp&&!canGoLeft) {
                    canNotPass[i][j]=true;
                    dp[i][j]=Integer.MIN_VALUE;
                    continue;
                }

                dp[i][j]=gold[i][j]+Math.max(left, up);
                max=Math.max(max, dp[i][j]);
            }
        }
        System.out.println(max);
    }
}
/*
3 3 3
BBR
BRB
RBB
0 1 10
2 10 100
10 100 100
 */

/*
3 3 3
BRB
BBB
RRB
0 1 10
0 0 0
10 100 0
 */

/*
1 1 1
B
0
 */

观星

有n颗流星，每个流星有出现时间s和消失时间t。在[s,t]的时间刻可以观测到它。求出能同时观测到的最大流星数以及可以观测到这个数量的时间刻数。

注意到交换两颗流星的出现时间（或消失时间）对结果没有影响。用

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {

        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        int max=0;

        int[][] stars =new int[n][2];
        for (int i = 0; i < n; i++) {
            stars[i][0]=in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            stars[i][1]=in.nextInt();
        }
        Map<Integer, Integer> effect =new HashMap<>();
        for (int[] star : stars) {
            effect.put(star[0], effect.getOrDefault(star[0], 0)+1);
            effect.put(star[1]+1, effect.getOrDefault(star[1]+1, 0)-1);
        }

        Map<Integer, Integer> sums=new HashMap<>();
        List<Integer> toDoList = effect.keySet().stream().sorted().collect(Collectors.toList());
        int p=0;
        for (int i =0; i<toDoList.size();i++) {
            int j=toDoList.get(i);
            int len=0;
            if(i>0) {
                len=j-toDoList.get(i-1);
            }
            sums.put(p, sums.getOrDefault(p, 0)+len);
            p+=effect.getOrDefault(j, 0);
            max=Math.max(p,max);
        }

        System.out.printf("%d %d%n",max, sums.get(max));
    }
}

/*
3
1 2 3
2 3 4
 */

坦克大战

D和W在一个16*16的地图上进行坦克大战。D一开始在左上角（0，0），面朝右侧，W一开始在右下角（15，15），面朝左侧。坦克会占领自己所在的格子。它们各给出了一个256长度的指令列表，包含以下指令：

U指令：使坦克面朝上方，如果上方一格未被对方占领，则移动到该格并占领之。

D指令：使坦克面朝下方，如果下方一格未被对方占领，则移动到该格并占领之。

L指令：使坦克面朝左方，如果左方一格未被对方占领，则移动到该格并占领之。

R指令：使坦克面朝右方，如果右方一格未被对方占领，则移动到该格并占领之。

F指令：朝面朝的方向直线开火。如果对方正在开火的路径上则被击中。

每回合双方都会按照指令移动一次。如果双方同时进入了一个未占领的格子，则发生碰撞，平局。

如果其中一方开火击中了对方，则开火者胜利。如果双方同时击中对方，则平局。如果256回合结束后双方仍存活，则比较占领的格子数，占领数多者获胜，相同则平局。

输出最后的胜利者（D或W）或是平局（P）

模拟题，面向对象

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in =new Scanner(System.in);
        String cmd1=in.nextLine(),cmd2=in.nextLine();
        int[][] map=new int[16][16];
        Tank t1=new Tank(0,0,6,map,1),t2=new Tank(15,15,4, map,2);
        map[0][0]=1;
        map[15][15]=2;
        for (int i = 0; i < 256; i++) {
            char act1=cmd1.charAt(i), act2=cmd2.charAt(i);
            if(act1=='F'&&act2=='F') {
                boolean res1=t1.shoot(t2), res2=t2.shoot(t1);
                if(res1&&res2) {
                    System.out.println(i+1);
                    System.out.println("P");
                    return;
                }
                if(res1) {
                    System.out.println(i+1);
                    System.out.println("D");
                    return;
                }
                if(res2) {
                    System.out.println(i+1);
                    System.out.println("W");
                    return;
                }
            }else if(act1=='F') {
                boolean res1=t1.shoot(t2);
                if(res1) {
                    System.out.println(i+1);
                    System.out.println("D");
                    return;
                }
                t2.act(act2);
            }else if(act2=='F') {
                boolean res2=t2.shoot(t1);
                if(res2) {
                    System.out.println(i+1);
                    System.out.println("W");
                    return;
                }
                t1.act(act1);
            } else {
                t1.act(act1);
                t2.act(act2);
                if(t1.x==t2.x&&t1.y==t2.y) {
                    System.out.println(i+1);
                    System.out.println("P");
                    return;
                }
            }
        }
        if(t1.capture>t2.capture) {
            System.out.println(256);
            System.out.println("D");
        } else if(t1.capture< t2.capture) {
            System.out.println(256);
            System.out.println("W");
        } else {
            System.out.println(256);
            System.out.println("P");
        }
    }
}

class Tank{
    int x;
    int y;

    int dir;

    int[][] map;

    int id;

    int capture=0;

    public Tank(int x, int y, int dir, int[][] map, int id) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.map = map;
        this.id=id;
    }

    public void act(char c) {
        if(c=='U') {
            dir=8;
            if(y>0&&(map[y-1][x]==0||map[y-1][x]==id)) {
                y-=1;
                if(map[y][x]==0){
                    capture++;
                }
                map[y][x]=id;
            }
        }
        if(c=='D') {
            dir=2;
            if(y<15&&(map[y+1][x]==0||map[y+1][x]==id)) {
                y+=1;
                if(map[y][x]==0){
                    capture++;
                }
                map[y][x]=id;
            }
        }
        if(c=='L') {
            dir=4;
            if(x>0&&(map[y][x-1]==0||map[y][x-1]==id)) {
                x-=1;
                if(map[y][x]==0){
                    capture++;
                }
                map[y][x]=id;
            }
        }
        if(c=='R') {
            dir=6;
            if(x<15&&(map[y][x+1]==0||map[y][x+1]==id)) {
                x+=1;
                if(map[y][x]==0){
                    capture++;
                }
                map[y][x]=id;
            }
        }
    }

    public boolean shoot(Tank target) {
        if(dir==8) {
            return target.x==x&&target.y<y;
        }
        if(dir==2) {
            return target.x==x&&target.y>y;
        }
        if(dir==4) {
            return target.y==y&&target.x<x;
        }
        if(dir==6) {
            return target.y==y&&target.x>x;
        }
        return false;
    }
}

红蓝树

对一个有根树，每个树节点被染成蓝色或红色。如果一个节点的所有子节点（不包括它自己）中蓝节点和红节点数量相同，那么它就是红蓝平衡的。

给出一个红蓝树，求其中红蓝平衡的节点数量。

一开始以为是二叉树，但不影响做法，还是后序遍历

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

public class Main {

    public static void main(String[] args) {

        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        in.nextLine();
        TreeNode[] treeNodeList=new TreeNode[n];
        String s = in.nextLine();
        for (int i = 0; i < n; i++) {
            treeNodeList[i]= new TreeNode(s.charAt(i),i+1);
        }
        for (int i = 1; i < n; i++) {
            int par = in.nextInt();
            TreeNode parentNode = treeNodeList[par-1];
            parentNode.childs.add(treeNodeList[i]);
        }
        treeNodeList[0].cal();
        System.out.println(TreeNode.count.size());
    }
}

class TreeNode{
    
    static List<Integer> count=new ArrayList<>();
    int redChild=0;
    int blueChild=0;

    char color;

    int id;

    List<TreeNode> childs=new ArrayList<>();

    public TreeNode(char color, int id) {
        this.color = color;
        this.id=id;
    }
    
    public void cal() {
        for (TreeNode child : childs) {
            child.cal();
            redChild+=child.redChild;
            blueChild+=child.blueChild;
            if(child.color=='R') {
                redChild++;
            } else {
                blueChild++;
            }
        }
        if(redChild==blueChild) {
            count.add(id);
        }
    }
}

Newtank

美团笔试记录

目录

翻转字母

捡金币

观星

坦克大战

红蓝树