8.19 小红书笔试面经 - 编程题 & 题解

考试平台： 赛码

T1

题目描述

小红的天都要背的闻，然后她会把每天记住了多少单词记录下来，并在小红书上打卡。 当小红背单同时，如果她已经记住了 i 个单词，且背了一个没有记住的单词 i+1 次，则她就会记住这个新单词。

例如，当她按顺序背 [“you”, "thank“, ”thank”] 时，她第一次背诵 ”you"时她就能记住”you”，而由于她已经记住了一个单词，所以需要背诵两次 "thank“ 才能记住 "thank”。 现在你如道了小红背单词的顺序，请你求出小红今天记住了多少个单间。

输入描述

第一行一个整数n(1sns10000)。 接下来n行，每行一个字符串，保证每个字等超长度不超过 10。

输出描述

输出一个整数，表示她记住了多少个单词。

示例

输入

5

you

chank

queue

queue

thank

输出

2

提示

小红先记住了单词"you",又因为背了两次“queue”，于是记住了单词"queue”。由于已经记住了两个单词，所以背两次"thank"还不能让小红记住。

题解

简单模拟题

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());

        // 存储已经记住的单词
        Set<String> mem = new HashSet<>();
        // 记录单词背诵次数
        Map<String, Integer> cntMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String word = in.nextLine();
            // 已经记住不再重复记
            if (mem.contains(word)) {
                continue;
            } else {
                int cnt = cntMap.getOrDefault(word, 0) + 1;
                // 记住单词 word
                if (cnt > mem.size()) {
                    mem.add(word);
                } else {
                    cntMap.put(word, cnt);
                }
            }
        }

        System.out.println(mem.size());
    }
}

T2 小红的回文串

题目描述

小红有一个字符串，她可以进行以下操作;

• 拆分。把 'w' 拆成2个 'v'，'m' 拆成 2个 'n'。
• 轴对称，把 'b' 轴对称成 ’d'，'p' 轴对称成 'q'，反之亦然。
• 翻转。把 b' 翻转成 q'，把 ’d’ 翻转成 'p'，把'n’ 翻转成 'u'，反之亦然。

经过若干次操作后，小红想知道这个字符串能不能变成回文串。

输入描述

第一行输入一个整数T（1 ≤ T ≤ ）表示询问次数。

接下来T行，每行输入一个字符串表示询问。

所有字符串长度之和不超过

输出描述

输出T行，每行输出“YES或"NO”表示是否可以变成回文串。

示例

输入

5
wovv
bod
pdd
moom
lalalai

输出

YES 
YES 
YES 
YES 
NO

提示说明

第一个字符串可以变成:vvovv(将第一个w拆成两个v)

第二个字符串可以变成:bob、dod、pop或qoq

第三个字符串可以变成:bdb

第四个字符串本来就是回文的，不用进行操作。

题解

通过双指针去判断是否回文， 特别需要注意条件比较多特别容易遗漏。

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());

        Solution solution = new Solution();
        for (int i = 0; i < n; i++) {
            System.out.println(solution.solve(in.nextLine()) ? "YES" : "NO");
        }
    }
}


class Solution {
    static Set<Character>[] eqSet = new HashSet[2];
    static Set<String> mEqSet;

    static {
        // 字符等价的集合
        eqSet[0] = new HashSet<>(Arrays.asList('b', 'd', 'q', 'p'));
        eqSet[1] = new HashSet<>(Arrays.asList('n', 'u'));

        // 特别容易遗漏， m 拆-> nn,  n 和 u 翻转。
        mEqSet = new HashSet<>(Arrays.asList("nn", "uu", "nu", "un"