9.10 美团笔试

1、直接将除法转换为乘法，比较即可（100%）

Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t-->0){
    long n = scanner.nextLong();
    long x = scanner.nextLong();
    long y = scanner.nextLong();
    long k = scanner.nextLong();
    if (k * y < x * (n - k + 1)) {
        System.out.println("Win");
    } else if (k * y == x * (n - k + 1)) {
        System.out.println("Tie");
    } else {
        System.out.println("Lose");
    }
}

2、计算和与0的个数，再判断（100%）

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int sum = 0;
int zero = 0;
for (int i = 0; i < n; i++) {
    int t = scanner.nextInt();
    sum += t;
    if (t == 0) {
        zero++;
    }
}
sum += zero;
if (sum == 0) {
    System.out.println(zero + 1);
} else {
    System.out.println(zero);
}

3、dfs（82%），动态规划没写出来

求大佬分享动态规划的AC代码

public class Main {
    static int[][] dires = {{2, 0}, {2, 1}};
    static long max = 0;
    static long[] roomValue;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] room = new int[n];
        int[] value = new int[n];
        int maxRoomNum = 0;
        for (int i = 0; i < n; i++) {
            room[i] = scanner.nextInt();
            maxRoomNum = Math.max(room[i], maxRoomNum);
        }
        for (int i = 0; i < n; i++) {
            value[i] = scanner.nextInt();
        }
        for(int i=0;i<n;++i){
            roomValue[room[i]] += value[i];
        }
        dfs(1, maxRoomNum, 0);
        System.out.println(max);
        // dp没写对
//        int[] dp = new int[maxRoomNum * 2 + 2];
//        dp[1] = roomValue[1];
//        max = roomValue[1];
//        for (int i = 1; i < maxRoomNum; i++) {
//            for (int[] d : dires) {
//                int next = i * d[0] + d[1];
//                dp[next] = Math.max(roomValue[next] + dp[i], dp[next]);
//                max = Math.max(dp[next], max);
//            }
//        }
    }

    static void dfs(int start, int maxRoomNum, long val) {
        if (start > maxRoomNum) {
            if (val > max) {
                max = val;
            }
            return;
        }
        for (int[] d : dires) {
            dfs(start * d[0] + d[1], maxRoomNum, val + roomValue[start]);
        }
    }
}

4、0%，求大佬分享思路

5、前缀和 + 贪心（100%）

要使分段最多，每一个位置能分就分，留给后面的数就越多。每个位置从上一个断开的位置开始遍历。

        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = s.length();
        // preSum[i]：s[0:i]的数字和
        int[] preSum = new int[n + 1];
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += s.charAt(i - 1) - '0';
            preSum[i] = sum;
        }
        int ans = 0;
        // 上一段切开的位置
        int last = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = last; j < i; ++j) {
                if ((preSum[i] - preSum[j]) % 7 == 0) {
                    ans++;
                    last = i;
                }
            }
        }
        System.out.println(ans);