小红书2020秋招笔试真题

1、字符串倒序

【题目描述】薯队长带着小红薯参加密室逃脱团建游戏，首先遇到了反转游戏，小红薯们根据游戏提示收集了多个单词线索，并将单词按要求加一个空格组成了句子，最终要求把句子按单词反转解密。
说明：收集的时候单词前后可能会有多个空格，反转后单词不能有多个空格，具体见输入输出样例。
输入描述
输入一个字符串。包含空格和可见字符。长度<=10000。
输出描述
输出一个字符串，表示反转后结果。
输入样例

the sky is blue!

输出样例

blue! is sky the

【解题思路】

字符串操作。根据题意实现即可

【参考代码】

import java.util.*;
import java.lang.*;
 
public class Main {
    public static void getReverseSentence(String str) {
        String[] s = new String(str).split("\\s+");
        if (s.length == 0) {
            System.out.println(" ");
        } else if (s.length == 1) {
            System.out.println(s[0]);
        } else {
            System.out.print(s[s.length - 1]);
            for (int i = s.length - 2; i >= 0; i--) {
                System.out.print(" " + s[i]);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        getReverseSentence(str);
    }
}

2、笔记精选

【题目描述】薯队长写了n篇笔记， 编号从 1～n，每篇笔记都获得了不少点赞数。 薯队长想从中选出一些笔记，作一个精选集合。挑选的时候有两个规则：
1. 不能出现连续编号的笔记。
2. 总点赞总数最多
如果满足1，2条件有多种方案，挑选笔记总数最少的那种。
输入描述
输入包含两行。第一行整数n 表示多少篇笔记。
第二行n 个整数分别表示 n 篇笔记的获得的点赞数。（0<n<=1000, 0<=点赞数<=1000)
输出描述
输出两个整数x y。空格分割。
x 表示总点赞数，y表示挑选的笔记总数。
输入样例

4 1
2 3 1

输出样例

4 2

【解题思路】

扫描一次，满足不相邻且总赞数更多更新状态。

【参考代码】

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int optimalSum = 0;
        int excludeSum = 0;
        int optimalCount = 0;
        int excludeCount = 0;
        for (int i = 0; i < n; i++) {
            int like = scanner.nextInt();
            int nextOptimalSum = optimalSum;
            int nextOptimalCount = optimalCount;
            if (excludeSum + like > optimalSum
                    || (excludeSum + like == optimalSum && excludeCount + 1 < optimalCount)) {
                nextOptimalSum = excludeSum + like;
                nextOptimalCount = excludeCount + 1;
            }
            excludeSum = optimalSum;
            excludeCount = optimalCount;
            optimalSum = nextOptimalSum;
            optimalCount = nextOptimalCount;
 
        }
        System.out.println(String.format("%s %s", optimalSum, optimalCount));
    }
}

3、击败魔物

【题目描述】薯队长来到了迷宫的尽头，面前出现了N只魔物，H_i表示第i只魔物的血量，薯队长需要在T个回合内击败所有魔物才能获胜。每个回合薯队长可以选择物理攻击一只魔物，对其造成1点伤害（物理攻击次数无上限）; 或者消耗1点法力释放必杀技对其造成固定X点伤害（薯队长开始拥有M点法力）。问X至少多大，薯队长才有机会获胜；如果无论如何都无法在T回合内获胜，则输出-1
输入描述
第一行三个整数分别表示：N T M
第二行有N个整数：H₁ H₂ H₃ … H_N
对于50%的数据：
0 < N < 10^3
0 < T < 10^3
0 <= M <= T
0 < H_i < 10^4
对于100%的数据
0 < N < 10^5
0 < T < 10^7
0 <= M <= T
0 < H_i < 10^7

输出描述
输出一个整数，表示必杀技一次最少造成多少固定伤害

输入样例

3 4 3
5 2 1

输出样例

3

【解题思路】

二分答案，贪心的进行判断是否可行。

【参考代码】

#include <bits/stdc++.h>
 
using namespace std;
 
bool check(int x, int n, int t, int m, vector<int> arr) {
    for (int i = 0; i < n; ++i) {
        if (m <= 0 || t <= 0) {
            break;
        }
        if (arr[i] < x) {
            continue;
        }