小红书0819秋招笔试真题解析
关注我们，每周更新两到三次大厂最新笔试题解析
前言：
本次题目难度总体并不大，但是题目比较灵活，特别是第三题，表面诱导你dp，实际则是个序列问题。
话说七夕了，我特意这么晚发你还看题？
1、小红背单词
小红每天都要背单词，然后她会把每天记住了多少单词记录下来，并在小红书上打卡。当小红背单词时，如果她已经记住了i个单词，且背了一个没有记住的新单词i+1次，则她就会记住这个新单词。
例如，当她按顺序背[“you“、“thank”、"thank”]时，她第一次背单词"you"时她就能记住“you”。而由于她已经记住了一个单词，所以需要背两次“thank"才能记住"thank”。现在你知道了小红背单词的顺序，请你求出小红今天记住了多少个单词。
输入描述：
第一行一个整数n(1<=n<=10000)。接下来n行，每行一个字符串，保证每个字符串长度不超过 10.
输出描述：
输出一个整数，表示她记住了多少个单词。
样例输入：
5
you
thank
queue
queue
thank
样例输出
2
提示：
小红先记住了单词"you”，又因为背了两次"queue"于是记住了单词"queue”.由于已经记住了两个单词，所以背两次"thank"还不能让小红记住.
思路与代码：
用HashMap记录每个单词的次数，同时用set记录已经背过的单词，已经背过的单词不计入。
import java.util.*;
public class Main11111 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] s = new String[n];
sc.nextLine();
for(int i = 0; i < n; i++){
s[i] = sc.nextLine();
}
HashMap<String, Integer> map = new HashMap<>();
HashSet<String> set = new HashSet<>();
int ans = 0;
for(int i = 0; i < n; i++){
if(set.contains(s[i]))continue;
map.put(s[i], map.getOrDefault(s[i],0) + 1);
if(map.get(s[i]) > ans){
ans++;
set.add(s[i]);
}
}
System.out.println(ans);
}
}
2、小红的回文串
小红有一个字符串，她可以进行以下操作:
-拆分。把’w'拆成2个’v'，’m’拆成 2个'n’。
-轴堆成。把’b’轴对称成’d’，’p’轴对称成’q’，反之亦然。
-翻转。把’b’反转成’q’，把’d’翻转成’p’，把’n’翻转成’u’
经过若干次操作，小红想知道这个字符串能不能变成回文串。
输入描述：
第一行输入一个整数 T(1<=T<=10^4)表示询问次数
接下来T行，每行输入一个字符串表示询问。
所有字符串长度之和不超过 10^5。
输出描述：
输出T行，每行输出"YES”或“NO”表示是否可以变成回文串。
样例输入：
5
Wovv
bod
pdd
moom
lalalai
样例输出
YES
YES
YES
YES
NO
思路与代码：
使用一个StringBuilder转换字符串s，如果为bdqp，统一转换为b。
如果为w，转为vv 如果为n，转为u 如果为m，转为uu
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] s = new String[n];
sc.nextLine();
for(int i = 0; i < n; i++){
s[i] = sc.nextLine();
}
String[] ans = new String[n];
Arrays.fill(ans, "NO");
int index = 0;
for(String str : s){
StringBuilder sb = new StringBuilder();
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(c == 'b' || c == 'd' || c == 'q' || c =='p')sb.append('b');
else if(c == 'w')sb.append('v').append('v');
else if(c == 'm')sb.append('u').append('u');
else if(c == 'n')sb.append('u');
else sb.append(c);
}
String s1 = sb.toString();
int i = 0, j = s1.length() - 1;
boolean flag = true;
while(i < j){
if(s1.charAt(i) != s1.charAt(j)){
flag = false;
}
i++;
j--;
}
if(flag){
ans[index] = "YES";
}
index++;
}
for(String x : ans){
System.out.println(x);
}
}
}
3、小红的攻略
小红是小红书的一个博主，她有很多的粉丝，有一些粉丝想让小红出一篇上尾市的旅游攻略。
上尾市有n个景点，有 m条路线，每个景点的攻略价值是 a，要花费h时间浏览，不同景点之间的交通时间为 w。
小红最多会选择3个相邻的景点，然后按顺序将景点写进攻略，她需要保证每个景点的浏览时间加上景点之间的交通时间总和不超过k，并且使得攻略的价值尽可能大，即是点的总价值尽可能大。
求小红的攻略的最大价值。
输入描述：
第一行输入三个整数 n,m(1<=n,m <=10^5),k(1 <=k<= 10^9)
第二行输入n 个整数表示数组 a(1 <=a:i<=10^9)。
第三行输入n个整数表示数组 h(1<=h<=10^9)
接下来m行，每行输入三个整数 u,v(1<=u,v <=n),w(1<= w<=10^9) 表示景点u,v 之间的交通时间为 w。
输出描述
一个整数，小红的攻略的最大价值。
样例输入：
4 4 6
4 3 2 1
1 2 3 4
1 2 1
2 3 1
2 4 1
3 4 1
样例输出：
9
说明
路线3-2-1的价值为4 + 3 + 2 = 9耗费时间1+1+2+1+3 = 8 路线1-2-3也一样，都是最优方案 可以证明，答案最大不超过9
思路与代码：
枚举终点，每次枚举时按照消耗的代价从小到大进行排序。用一个pre数组记录前缀结点的最大价值 对于每个终点，从代价由大到小枚举中间点，再利用二分找出这个中间点的相邻点，因为代价是从小排序的，所以价值加上二分找到的点的pre值即可。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
static int maxn = 100010;
static long[] a = new long[maxn];
static long[] h = new long[maxn];
static List<Edge>[] E = new ArrayList[maxn];
static long res = 0;
static long[] pre = new long[maxn];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long k = sc.nextLong();
for(int i = 1; i <= n; i++){
a[i] = sc.nextLong();
}
for(int i = 1; i <= n; i++){
h[i] = sc.nextLong();
if(h[i] <= k){
res = Math.max(res, a[i]);
}
}
for(int i = 0; i < maxn; i++){
E[i] = new ArrayList<>();
}
for(int i = 0; i < m; i++){
int from = sc.nextInt();
int to = sc.nextInt();
int time = sc.nextInt();
E[from].add(new Edge(a[to], time + h[to]));
E[to].add(new Edge(a[from], time + h[from]));
if(time + h[from] + h[to] <= k){
res = Math.max(res, a[from] + a[to]);
}
}
//枚举终点，挑两个点满足条件，权值尽可能大，带价值和<k并且value尽可能大，第三个点的下标要<第二个点的下标
for(int i = 1; i <= n; i++){
if(E[i].size() < 2){
continue;
}
//代价从小到大排序
Collections.sort(E[i], (e1, e2) -> Long.compare(e1.time, e2.time));
kaishi(i);
res = Math.max(res, a[i] + function(i, k - h[i]));
}
System.out.println(res);
}
//价值的前缀最大值
static void kaishi(int x){
int sum = E[x].size();
pre[0] = E[x].get(0).value;
for(int i = 1; i < sum; i++){
pre[i] = Math.max(E[x].get(i).value, pre[i - 1]);
}
}
static int get(int st, long last){
int l = 0, r = E[st].size() - 1,ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(E[st].get(mid).time <= last){
ans = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
return ans;
}
//枚举两个点中代价最大的点，根据时间限制二分找出
static long function(int x, long last){
long ans = 0;
//枚举中间点
for(int i = E[x].size() - 1; i > 0; i--){
int id = get(x, last - E[x].get(i).time);
id = Math.min(id, i - 1);
if(id < 0){
continue;
}
ans = Math.max(ans, E[x].get(i).value + pre[id]);
}
return ans;
}
static class Edge{
long value, time;
Edge(long value, long time){
this.value = value;
this.time = time;
}
}
}最后插一下我们的进阶一对一辅导啦
我们是一个针对技术岗（前后端开发、测试、测开、大数据开发）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整三年的时间，带领300+学员斩获1500+大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！ 万诺coding
我们主要是针对有一定基础的同学提供一对一笔试和面试辅导，针对每个同学不同的情况定制内容，包括但不限于“数据结构与算法”/“计算机基础知识”/“项目梳理”/“面试技巧”/“面试复盘”等内容。
摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。同时这也是一个双向筛选的过程，如果基础过差的同学，抱歉我们可能无法辅导（基础过差的同学一对一辅导成本过高，对双方都不适合）；摸底测试通过的同学，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。
承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。
有兴趣的同学可以扫码添加我们的微信（whynotlab）