网易互娱笔试-初级游戏研发工程师-复盘

第1道

如果把一个数的各位数字反向排列所得的数和原数一样,则称这个数为回文数。给定一个十迸制的正整数X,判断X在二进制下(去掉前导0)是否是回文数。如的二进制为1011。

输入描述:

输入的第一行是一个正整数(0<T<=100),表示有组测试数据。对于每一个测试数据包含一个正整数x(0<X<=
10000000)

输出描述:

对于每一组测试样例,如果x在二进制下是回文数则输出YES,否则输NO

示例1

输入:

3
1
4
7

输出:

YES
NO
YES

Integer.toBinaryString() API 很好用

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            Integer t = sc.nextInt();
            String binaryString = Integer.toBinaryString(t);
            char[] s = binaryString.toCharArray();
            boolean flag = true;
            for (int l = 0, r = binaryString.length() - 1; l < r; l++, r--) {
                if (s[l] != s[r]) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

第2道

给定一棵二叉树,每个结点有一个正整数权值。若棵二叉树,每一层的结点权值和都严格小于下一层的结点权值和,则称这棵二叉树为递增二叉树。
现在给你一棵二叉树,你需要判断其是不是一棵递增二叉树。

输入描述:

输入的第一行是一个正整数(0<T<=50)。接下来有T组样例对于每组样例,输入的第一行是一个正整数N,表示树的结点个数(0<N<=1000,结点编号为0到N-1):按下来是N行,第k行表示编号为k的结点,输入格式为:VALUE LEFT RIGHT,其中VALUE表示其权值,是一个不超过5000的自然数;LEFT和RIGHT分别表示该结点的左子编号和右子编号。如果其不存在左子或右子,则工LEFT或R工RIGHT为-1.

输出描述:

对于每一组样例,翰出一个字符串。如果该二叉树是一棵递增树,则输出YES,否则输出NO.

示例1

输入:

2
8
2 -1 -1
1 5 3
4 -1 6
2 -1 -1
3 0 2
2 4 7
7 -1 -1
2 -1 -1
8
21 6 -1
52 4 -1
80 0 3
31 7 -1
21 -1 -1
59 -1 -1
50 5 -1
48 -1 1

输出:

YES
NO

先找根节点,再层次遍历

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();
            if (N == 1) {
                System.out.println("NO");
                break;
            }
            int[][] tree = new int[N][3];
            int[] f = new int[N];
            Arrays.fill(f, -1);
            for (int j = 0; j < N; j++) {
                tree[j][0] = sc.nextInt(); // value
                tree[j][1] = sc.nextInt(); // left
                if (tree[j][1] != -1) f[tree[j][1]] = j;
                tree[j][2] = sc.nextInt(); // right
                if (tree[j][2] != -1) f[tree[j][2]] = j;
            }
            int root = -1;
            for (root = 0; root < N; root++) {
                if (f[root] == -1) {
                    break;
                }
            }
            boolean flag = true;
            Queue<Integer> firstQueue = new ArrayDeque<>();
            Queue<Integer> secondQueue = new ArrayDeque<>();
            firstQueue.offer(root);
            while (!(firstQueue.isEmpty())) {
                int firstSum = 0, secondSum = 0;
                while (!firstQueue.isEmpty()) {
                    Integer parent = firstQueue.poll();
                    firstSum += tree[parent][0];
                    if (tree[parent][1] != -1) {
                        secondQueue.offer(tree[parent][1]);
                        secondSum += tree[tree[parent][1]][0];
                    }
                    if (tree[parent][2] != -1) {
                        secondQueue.offer(tree[parent][2]);
                        secondSum += tree[tree[parent][2]][0];
                    }
                }
                if (secondQueue.size() == 0) break;
                if (firstSum >= secondSum) {
                    flag = false;
                    break;
                }
                Queue<Integer> temp = firstQueue;
                firstQueue = secondQueue;
                secondQueue = temp;
            }
            if (flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
        sc.close();
    }
}

第3道

小Y很喜欢喝咖啡,但是同事告诉他经常喝咖啡可能不太好,所以小Y限制自己喝咖啡的间隔不能低于κ天。但是,在一个月30天当中,固定有M天是小Y最喜欢的游戏更新版本的日子,这个时候小Y一定会喝咖啡庆祝这些日子。
小Y想知道,在满足上面的条件下,这个月最多能喝多少次咖啡呢?

输入描述:

输入的第一行是一个正整数T(0<T<=500),表示样例个数。对于每一个样例,第一行是两个正整数K(0<=K<=30)、M(0<=M<=30)分别表示喝咖啡的最小间隔和固定喝咖啡的日子。按下来一行是M个不重复的由空格分隔的整数,表示小Y固定喝咖啡的日子。题目保证这些日子按照从小到大的顺序给出,它们之间的间隔不会低于K天,且范国均在1到30之间(含1和30)。

输出描述:

对于每一组样例,输出一个正整数,表示小Y这个月最多能喝咖啡的次数。

示例1

输入:

5
0 10
1 2 3 4 5 6 7 8 9 10
1 15
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
1 7
5 9 13 17 21 25 29
5 2
1 30
5 2
7 30

输出:

30
15
15
5
5

这道题目的边界条件真的很经典。

边界条件一定要写出恒成立的不等式,推出来;
而不是像我之前,+1 - 1 取上界 取下界 地凑一凑就行了,运行一下匹配验证,根本濑得去思考,这道题上吃了大亏

严格不等式:
① day[0] - cnt * (K+1) >= 1
=> cnt <= (day[0] -1)/(K+1) 数学除
=> 根据题目意思,(day[0] - 1)/(K+1) 向下取整
② day[j-1] + cnt * (K+1) < day[j]
=> cnt < (day[j] - day[j-1])/(K+1) 数学除
=> 根据题目意思,(day[j] - day[j-1])/(K+1) 向下取整 再-1
③ day[M-1] + cnt * (K+1) <= 30
=> cnt <= (30 - day[M-1])/(K+1) 数学除
=> 根据题目意思, (30 - day[M-1])/(K+1) 向下取整

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int K = sc.nextInt();
            int M = sc.nextInt();
            int max = M;
            int[] days = new int[M];
            for (int j = 0; j < M; j++) {
                days[j] = sc.nextInt();
            }
            if (M == 0) {
                max = 30 / (K + 1);
            } else {
                for (int j = 0; j < M; j++) {
                    if (j == 0) {
                        int cnt = (days[j] - 1) / (K + 1);
                        max += cnt;
                    } else {
                        int gap = days[j] - days[j - 1];
                        int cnt = gap / (K + 1) - 1;
                        max += cnt;
                    }
                    if (j == M - 1) {
                        int gap = 30 - days[j];
                        max += gap / (K + 1);
                    }
                }
            }
            System.out.println(max);
        }
        sc.close();
    }
}