🔥 9.21 携程笔试面经 - 编程题 & 题解

考试时间：2023-09-21（2小时）

考试平台： 牛客网

P1

游游拿到了一个排列a。她希望你构造一个长度相等的排列b，满足 且 b 的字典序尽可能小。你能帮帮她吗?

所谓排列，即长度为n的数组，其中1到n每个正整数都恰好出现了1次。

排列的字典序定义如下:两个排列的字典序比较，将比较它们第一个不相等的元素，该元素小的那个排列字典序更小。例如[2,1,3]的字典序小于[2,3,1]

输入描述

第一行输入一个正整数n，代表排列a的长度。

第二行输入 n 个正整数a，代表游游拿到的排列。

输出描述

n个正整数 ，代表构造的排列。

示例1

输入：
3
1 2 3

输出：
2 3 1

题解

贪心

import java.util.PriorityQueue;
import java.util.Scanner;

// P1
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();

        Solution solution = new Solution();
        int[] b = solution.solve(a, n);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(b[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

class Solution {
    public int[] solve(int[] a, int n) {
        int[] b = new int[n];
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) queue.offer(i + 1);
        for (int i = 0; i < n; i++) {
            Integer cur = queue.poll();
            if (a[i] == cur) { // 最小的元素重复
                if (!queue.isEmpty()) { // 取下一个最小的元素
                    b[i] = queue.poll();
                    queue.offer(cur);
                } else {    // 最后一个元素重复，选择和前一个元素替换
                    b[i] = b[i - 1];
                    b[i - 1] = cur;
                }
            } else {
                b[i] = cur;
            }
        }
        return b;
    }
}

P2

小红拿到了一个字符串s。她可以进行任意次以下提作: 选择字符串中的一个字母ch1和任意一个字母ch2 (ch2可以不在字符串中出现)，将字符串s中的所有ch1变成ch2。 小红想知道，自己能否通过一些提作将字符串s变成t?

输入描述

第一行输入一个正整数9，代表查询次数。对于每次查询输入2行: 第一行输入一个字符串s。 第二行输入一个字符串t. 1 ≤ q ≤10

保证s和t的长度相同，且均由小写字母组成。长度不超过10000

输出描述

输出q行，每行输出一个字符串代表答案。如果可以把s变成t，则输出Yes。否则输出No.

示例1

输入：
3
ab
ba
abc
aaa
aaaa
abcd

输出：
Yes
Yes
No

题解

构造题

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// P2
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();

        Solution solution = new Solution();
        for (int i = 0; i < q; i++) {
            System.out.println(solution.solve(in.next(), in.next()) ? "Yes" : "No");
        }
    }
}


class Solution {
    public boolean solve(String s, String t) {
        // 旧-新 字符对照表
        Map<Character, Character> map = new HashMap<>();
        char[] cs = s.toCharArray(), ct = t.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            Character nchar = map.get(cs[i]);
            if (null == nchar) {
                map.put(cs[i], ct[i]);
            } else if (nchar != ct[i]) {
                return false;
            }
        }

        return true;
    }
}

P3

游游拿到了一个n行m列的字母矩阵，矩阵中所有字符都是小