0904小红书笔试

20220904小红书笔试

第一题：镜像序列

已知一个序列的生成方式如下：

• 序列生成需要一个基础序列A，这个序列由n个 不大于100的数字组成，同时给定镜像复制次数m。

• 然后对于A进行m次镜像复制，例如序列A={1，2，3}，则一次镜像复制后得到的序列是{1，2，3，3，2，1}，两次镜像复制得到的序列是B={1，2，3，3，2，1，1，2，3，3，2，1} 。

现在给出你生成一个序列所需要的参数，请你计算该序列的第k位是多少。

输入描述
输入第一行包含三个整数n，m，k，含义如题所示。(1<=n<=100,1<=m<=60,1<=k<=1e18，部分数据k<10000)

输入第二行包含n个正整数，每个正整数都不大于100，表示基础序列A。数字间有空格隔开

输出描述

输出仅包含一个正整数，即序列第k位的数字。

样例输入
3 3 10
1 2 3
样例输出
3
1
2
3
4
5

解题思路

其实不用管到底是镜像了多少次，我们只需要只要k和n即可。用一个数组nums保存初始的序列

int beishu = k / n,int yushu = k % n。

如果是偶数倍，那么此时第k位数字是正序，且为nums[yushu - 1]

如果是奇数倍，那么此时第k位数字是逆序，且为nums[n - yushu]

AC代码

import java.util.Scanner;

public class Solution_小红书_镜像序列 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextLong();
        int[] nums = new int[n];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int count = (int) (k / n);
        int yushu = (int) (k % n);
        if (count % 2 == 0) {
            System.out.println(nums[yushu - 1]);
        } else {
            System.out.println(nums[n - yushu]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第二题：乘积为7

题目描述：
给定n个整数a1, a2, a3 … an。每次操作可以选择其中一个数，并将这个数加上1或者减去1。小红非常喜欢7这个数，他想知道至少需要多少次操作可以使这n个数的乘积为7？

输入描述
第一行输入一个正整数n，表示整数的个数。

第二行输入n个整数a1, a2, a3 … an，其中ai 表示第i个数。

输出描述
输出一个整数，表示将所有数的乘积变为7最少需要的操作次数。

样例输入
5
-6 0 2 -2 3
样例输出
6

提示
1 ≤ n ≤ 30000，-109  ≤ ai ≤ 109

样例说明

一种可能的操作方式如下：

第一次操作将a1减1，得到[-7,0,2,-2,3]

第二次操作将a4加1，得到[-7,0,2,-1,3]

第三次操作将a3减1，得到[-7,0,1,-1,3]

第四次操作将a5减1，得到[-7,0,1,-1,2]

第五次操作将a5减1，得到[-7,0,1,-1,1]

第六次操作将a2加1，得到[-7,1,1,-1,1]，此时所有数的乘积为7。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解题思路

因为7是质数，所以要么是1 * 7要么是-1 * -7.所以首先将nums排序，找到正负数分隔点fenge

如果nums中有奇数个负数，那么分别计算 1 * 7这种和 -1 * -7这种的操作次数

先计算 1 * 7

• 因为是奇数个负数，所以必然是最小的fenge-1个奇数最后变成-1，这样他们的乘积就会变成1，然后第fenge-1到第n-1个全部是1，最后一个是7

再计算 -1 * -7

• 因为是奇数个负数，所以最小的变成-7，那么还需要将最小的正数变成-1才行。所以从第2到最小正数全部变成-1，从第2大正数到n全部变成1

判断在奇数个负数情况下，输出1 * 7和-1 * 7两种情况下的最小操作次数

如果nums中有偶数个负数，也是需要分别计算两种情况

先计算 1 * 7

• 因为是偶数个负数，所以将这些负数变成-1，然后将第一个正数到第n-1个数变成1，最后一个数变成7

再计算 -1 * -7

• 因为是偶数个负数，所以将最小的负数变成-7，其他负数全变成-1，所有正数全部变成1

判断在偶数个负数情况下，输出1 * 7和-1 * 7两种情况下的最小操作次数

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

public class Solution_小红书_乘积为7 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums);
        long ans = 0;
        if (nums[0] >= 0) {
            //全是正值
            for (int i = 0; i < n - 1; i++) {
                ans += Math.abs(nums[i] - 1);
            }
            ans += Math.abs(nums[n - 1] - 7);
            System.out.println(ans);
        }
        if (nums[n - 1] < 0) {
            //如果全是负数
            for (int i = 1; i < n; i++) {
                ans += Math.abs(nums[i] + 1);
            }
            ans += Math.abs(nums[0] + 7);
            System.out.println(ans);
        }
        //第三种情况就是有正有负
        //切割成两个数组，分别计算看最终大小
        else {
            int fenge = 0;
            for (int i = 1; i < n; i++) {
                if (nums[i - 1] < 0 && nums[i] >= 0) {
                    fenge = i;
                    break;
                }
            }
            //考虑分割及其左右，
            long zheng = 0;
            long fu = 0;
            if (fenge % 2 == 0) {
                for (int i = 0; i < fenge; i++) {
                    zheng += Math.abs(nums[i] + 1);
                }
                for (int i = fenge; i < n - 1; i++) {
                    zheng += Math.abs(nums[i] - 1);
                }
                zheng += Math.abs(nums[n - 1] - 7);
                fu += Math.abs(nums[0] + 7);
                for (int i = 1; i < fenge; i++) {
                    fu += Math.abs(nums[i] + 1);
                }
                for (int i = fenge; i < n; i++) {
                    fu += Math.abs(nums[i] - 1);
                }
                System.out.println(Math.min(zheng, fu));
            } else {
                for (int i = 0; i < fenge - 1; i++) {
                    zheng += Math.abs(nums[i] + 1);
                }
                for (int i = fenge - 1; i < n - 1; i++) {
                    zheng += Math.abs(nums[i] - 1);
                }
                zheng += Math.abs(nums[n - 1] - 7);

                //负数
                fu += Math.abs(nums[0] + 7);
                for (int i = 1; i <= fenge; i++) {
                    fu += Math.abs(nums[i] + 1);
                }
                for (int i = fenge + 1; i < n; i++) {
                    fu += Math.abs(nums[i] - 1);
                }
                System.out.println(Math.min(zheng, fu));
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

第三题：最小过路费用

题目描述：
小明的旅途中需要经过一个国家。这个国家有n个城市，编号为1到n。小明会从1号城市进入，目标是从n号城市出去（即要从1号城市到达n号城市）。有m条双向道路连接这n个城市，每条道路的长度都是1，并且都有一个过路费（是[1,100000]之间的整数）。当小明在一号城市时，他可以预先花费X的费用办一张特权卡，他可以获得所有过路费不超过X的道路的通行权（而其他道路无法通过）。小明一天最多只能走k长度的路，他想知道如果他想在一天之内从1号城市走到n号城市，他最少需要花费多少来办特权卡，即求X的最小值？

输入描述
第一行是3个整数n，m，k，分别表示城市数，道路数和小明一天最多能走的长度。

第二行m个整数，分别为u1, u2, …, um，分别表示第i条道路的一个端点。

第三行m个整数，分别为v1, v2, …, vm，分别表示第i条道路的另一个端点。

第四行m个整数，分别为w1, w2, …, wm，分别表示第i条道路的过路费。

数字间两两有空格隔开。数据保证一定存在解。

输出描述

一行一个整数，表示X的最小值。

样例输入
5 6 3
1 1 2 3 3 4
2 5 3 4 5 5
1 3 1 2 1 1
样例输出
1

提示
n<=100000，m<=200000，1<=w<=100000。
1
2
3
4
5
6
7
8
9
10
11
12

时间不够，偷分18%