美团笔试(2024.4.9)

第一场实习笔试，A了3.3道，算法还是不太熟

第一题：

简单模拟即可

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int count = 0;
        int[][] array = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                array[i][j] = in.nextInt();
            }
        }
        for(int i = 0; i < m - 1; i++){
            for(int j = 0; j < n - 1; j++){
                int a = array[i][j];
                int b = array[i][j + 1];
                int c = array[i + 1][j];
                int d = array[i + 1][j + 1];
                if(a == b && a == c && a == d && b == c && b == d && c == d){
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

第二题：

贪心策略，按绝对值从小到大排序，优先需绝对值小的，直到和大于等于k

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long k = scanner.nextLong();
        int[] array = new int[n];
        int count = 0;
        long sum = 0;
        for(int i = 1; i <= n; i++){
            array[i - 1] = scanner.nextInt();
        }
        for(int i = 0; i < n; i++){
            array[i] = Math.abs(array[i]);
        }
        Arrays.sort(array);
        for(int i = 0; i < n; i++){
            if(sum >= k){
                break;
            }
            sum = sum + array[i];
            count++;
        }
        if(sum > k){
            System.out.println(count - 1);
        }else{
            System.out.println(count);
        }
    }
}

第三题：

DFS，用HashMap建树，每次DFS时返回该节点所代表子树红、黑节点的存在情况

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

public class Main {
    public static HashMap<Integer, List<Integer>> map = new HashMap<>();
    public static HashMap<Integer, String> map1 = new HashMap<>();
    public static int count = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String n = scanner.nextLine();
        String s = scanner.nextLine();
        int n1 = Integer.valueOf(n);
        for(int i = 0; i < s.length(); i++){
            map1.put(i + 1, s.substring(i, i + 1));
        }
        for(int i = 0; i < n1 - 1; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if(!map.containsKey(a)){
                List<Integer> list = new ArrayList<>();
                list.add(b);
                map.put(a, list);
            }else {
                List<Integer> list = map.get(a);
                list.add(b);
                map.put(a, list);
            }
        }
        boolean[] bb = DFS(1);
        System.out.println(count);
    }
    public static boolean[] DFS(int index){
        boolean[] ans = new boolean[2];
        if(!map.containsKey(index)){
            String s = map1.get(index);
            if(s.equals("B")){
                ans[0] = true;
            }else{
                ans[1] = true;
            }
            return ans;
        }
        List<Integer> list = map.get(index);
        String s = map1.get(index);
        if(s.equals("B")){
            ans[0] = true;
        }else{
            ans[1] = true;
        }
        boolean left = ans[0];
        boolean right = ans[1];
        int flag = 0;
        for(Integer i: list){
            boolean[] a = DFS(i);
            ans[0] = a[0] || ans[0];
            ans[1] = a[1] || ans[1];
            boolean left1 = left || a[0];
            boolean right1 = right || a[1];
            if (left1 == true && right1 == true){
                flag = 1;
            }
        }
        if(flag == 1){
            count++;
        }
        return ans;
    }
}

第四题：没做

第五题：暴力DFS，30%

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

public class Main {
    public static HashSet<String> set = new HashSet<>();
    public static int count = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        for (int i = 0; i < s.length(); i++){
            if(!set.contains(s.substring(i, i + 1))){
                count = (count + 1) % 100000007;
                set.add(s.substring(i, i + 1));
            }
            DFS(s, s.substring(i, i + 1), i);
        }
        System.out.println(count);
    }
    public static void DFS(String s, String s1, int index){
        if(index >= s.length() - 1){
            set.add(s1);
            return ;
        }
        for(int i = index + 1; i < s.length(); i++){
            String ss2 = s.substring(i, i + 1);
            String ss3 = s1.substring(s1.length() - 1, s1.length());
            if(!ss2.equals(ss3)){
                String s2 = s1 + s.substring(i, i + 1);
                if(s2.length() > 0 && !set.contains(s2)){
                    count = (count + 1) % 100000007;
                }
                set.add(s2);
                DFS(s, s2, i);
            }
        }
    }
}