小红书20230326暑假实习笔试

第一题：加密

小明学会了一种加密方式。他定义suc(x)为x在字母表中的后继，例如a的后继为b，b的后继为c… （即按字母表的顺序后一个）。特别的，z的后继为a。对于一个原字符串S，将其中每个字母x都替换成其三重后继，即suc(suc(suc(x)))的字母，即完成了加密。例如，abc加密后变成def （suc(suc(suc(a)))=d suc(suc(suc(b)))=e, suc(suc(suc©))=f）。 现在小明知道一个加密后的字符串S’，想请你找出他的原串S。
输入数据

3
def

输出数据

abc

直接模拟完成

Class solution{public static String findString(String s){int n = s.length();String ans = "";for(int i = 0; i < n; i ++){if(s.charAt(i)=='a' || s.charAt(i)=='b' || s.charAt(i)=='c'){ans += (char) (s.charAt(i) - 3 + 26);}else{ans += (char)(s.charAt(i) - 3);}}return ans;}
}
public main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.print("请输入字符串的长度：");int n = scanner.nextInt();System.out.print("请输入字符串：");String input = scanner.next();Solution s = new Solution();System.out.println(s.findString(input));scanner.close();}
}

第二题：K排序

在算法中，有各种各样的排序算法，例如归并排序，冒泡排序，快速排序等等。本题中，我们会使用一种新的排序算法：K排序。

K排序算法描述如下：首先，算法需要按照某种规则选择该数列上至多K个位置，将其对应的数抽出来，其他的数都往左对齐，之后这K个数排好序之后依次放在原数列末尾。以上过程算作一次操作。
例如，对于数列[1,3,5,4,2]，当K=2时可以选择数字5和4，之后数列变成[1,3,2,4,5]。
你的任务是：对于给定的数列，你需要计算出最少需要多少次上述操作，使得整个数列从小到大排好序？

样例输入

2
5 1
1 2 3 4 5
5 2
1 3 5 4 2

样例输出

0
2

主要思路是贪心，每次找到当前未排序部分的最小值，将其移动到正确的位置，如果需要移动的距离超过了k，则需要进行一次K排序操作。

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0) {int n = sc.nextInt();int k = sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = sc.nextInt();}int ans = 0;int cur = 0;while (cur < n) {int minIndex = cur;for (int i = cur + 1; i < Math.min(cur + k + 1, n); i++) {if (nums[i] < nums[minIndex]) {minIndex = i;}}if (minIndex == cur) {cur++;} else {int temp = nums[minIndex];for (int i = minIndex; i > cur; i--) {nums[i] = nums[i - 1];}nums[cur] = temp;ans++;}}System.out.println(ans);}}
}

第三题: 涂色

给出一个数组。你需要求出按顺序对其进行一系列区间操作后最终所得的数组。

操作有三种：

将下标在L到R之间的元素全部或上X。
将下标在L到R之间的元素全部与上X。
将下标在L到R之间的元素全部设为X。
输入描述

第一行有一个正整数N(1<=N<=100000)，代表数组的长度。

第二行有N个非负整数，范围在0到2^20-1之间，代表数组中的元素。

第三行有一个正整数M(1<=M<=100000)，代表操作次数。

第四行有M个正整数，代表M次操作中的区间左端点L。

第五行有M个正整数，代表M次操作中的区间右端点R。

第六行是一个长度为M的字符串，|代表操作1，&代表操作2，=代表操作3。

第七行有M个正整数，代表M次操作中的参数X。

输出描述

在一行中输出N个数，代表所有操作按顺序完成后最终所得的数组。

样例输入

4
5 4 7 4
4
1 2 3 2
4 3 4 2
=|&=
8 3 6 2

样例输出

8 2 2 0