小红书笔试

, , ,

博客的最大评分

题目描述

博客有点赞数和评论数，在 n 篇博客中选取 k 篇，使得评分最高。

评分规则：选取的博客中的点赞数之和与评论数最小值的乘积。

示例

n = 4, k = 2

点赞数：[1,2,3,4]

评论数： [4,3,2,1]

答案： 10（选取第二篇与第三篇）

解析

  1. 将输入的点赞数与评论数创建 Blog 对象，并根据对象的评论数对数组排序。
  2. 之后将后 k 个博客放入优先队列，同时计算初始评分。
  3. 遍历剩余对象，不断调整选中的对象，移除最小的点赞数，添加新的点赞数，计算新的评分，保留最大值。

ps：本题还可通过动态规划的的方式解决

时间复杂度： O(nlogn)

空间复杂度： O(n)

参考

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
public static void main(String[] args) {
    Scanner in = new Scanner(System._in_);

    int n = in.nextInt();
    int k = in.nextInt();

    Blog[] blogs = new Blog[n];

    for (int i = 0; i < n; i++) {
        int good = in.nextInt();
        blogs[i] = new Blog(good);
    }
    for (int i = 0; i < n; i++) {
        blogs[i].comment = in.nextInt();
    }

    Arrays._sort_(blogs, (a, b) -> a.comment - b.comment);

    int sum = 0;
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);
    int ans = 0;

    for(int i = n - k; i < n; i++){
        int temp = blogs[i].good;
        sum += temp;
        pq.offer(temp);
    }
    ans = blogs[n-k].comment * sum;

    for(int i = n - k - 1; i >= 0; i--){
        sum -= pq.poll();

        Blog temp = blogs[i];
        sum += temp.good;

        ans = Math._max_(ans, temp.comment * sum);
    }
    System._out_.println(ans);
}

class Blog{
    int good;
    int comment;

    Note(int good){
        this.good = good;
    }
}

新账号的新增粉丝量

题目描述

小红有有 n 个旧账号，每个账号粉丝数量为 ai，现在小红创建了新的账号，希望新账号的粉丝数量恰好为 x。

小红可以选择在旧帐号推荐新账号，在第 i 个旧号推荐一次新号粉丝数量增加 ai/2，多次可增加 ai。最多可以从旧号中选择一个账号进行多次推荐。

解析

使用动态规划解决问题，其中 dp[i][j][k]表示选择前 n 个旧账号达到粉丝数为 j 的最小操作数，k 表示是否使用过多次推荐。

在遍历过程中有几种选择：

  • 不选择当前账号
  • 选择当前账号
  • 多次使用当前账号

最后返回最小值，无法达到则返回-1。

时间复杂度： O(nx)

空间复杂度： O(nx)

参考

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
public int maxFans(int[] before, int x){
    int n = before.length;

    int[][][] dp = new int[n + 1][x + 1][2];

    for (int[][] ints : dp) {
        for (int[] anInt : ints) {
            Arrays._fill_(anInt, Integer._MAX_VALUE _/ 2);
        }
    }

    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= x; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = Math._min_(dp[i][j][k], dp[i-1][j][k]);
                int half = before[i - 1] / 2;
                int all = before[i - 1];

                if(j >= half){
                    dp[i][j][k] = Math._min_(dp[i][j][k], dp[i - 1][j - half][k] + 1);
                }
                if(k == 1 && j >= all){
                    dp[i][j][k] = Math._min_(dp[i][j][k], dp[i - 1][j - all][0] + 1);
                }
            }
        }
    }
    int min = Math._min_(dp[n][x][0], dp[n][x][1]);

    min = min == (Integer._MAX_VALUE _- 1) ? -1 : min;
    return min;
}

yzlzzzdeveloper