去哪儿软开秋招笔试——算法真题

时间：2024.10

1、给定一个长度为n且仅由小写字母构成的字符串，字符串中的位置有两种类型：固定位和流动位
• 对于一个固定位，该位置上的字符不会在操作中发生变化。
• 对于一个流动位上的字符，它可能会发生变化。
初始时所有位置都是流动位。位置标号从1开始。现在有4次操作，每次操作有下列两种可能：
• 操作一：将第i位设置为固定位（不保证之原来是流动位)。
• 操作二：将所有流动位的字符循环右移一格。不妨设流动位的下标为p1，p2, ..., pm，则该操作是将p1上的字符移动到p2；p2上的字符移动到p3；..；pm上的字符移动到p1。
例如，若字符串为”abcdef”（其中第2,4位是固定位，使用下划线表示)，则一次操作二后变为”fbadce”，再次进行操作二后变为”ebfdac”
请输出一系列探作后最终得到的字符串
输入描述：第一行输入两个整致n,q代表字符串长度和操作次数。第二行输入一个长度为n，且仅由小写字母构成的字符串s代表初始字符串。此后q行，每行先输入一个整数op代表操作次数，如果op=1，则再同一行上输入另一个整数u代表将第u位设为固定位；op=2表示一次移动操作。保证流动位至少存在一个
输出描述：一个字符串表示经过操作后最终字符串

2、小N是一名地铁职工，上级给他安排了一个奇怪的任务：从某个站出发，坐满k分钟（k最大取到m，m给定）地铁，然后回到出发站。
这个城市的地铁系统也很神奇，一共有n 个车站，相邻两站之间的通勤总是耗时 1分钟，为了方便我们也不予考虑换乘等消耗的时间。
一直坐地铁也不是件轻松事，每坐一站路就会积累特定量的疲劳值。小N 听说在去哪儿上搜索出行攻路会很方便，所以他经过查阅，发现对于相邻的a,b两站，他从a坐到b或从b坐到a 都会积累f(a,b)的疲劳值。
现在小N想要知道，对于每一个出发站，从该站出发坐x分钟（x取遍[1,m]中的整数），再回到出发站，积累的疲劳值最少可以为多少
输入描述：第一行输入两个整数n和m，代表车站数量和最长乘坐时间
随后n行，第i行输入n个整数ai,1 , ..., ai,n，其中ai,j=-1表示车站i与车站j不相邻，否则其为f(i,j)
输出描述：对于n行，每行输出m 个整数。第i行的第j个数表示从i站出发坐j 分钟坐地铁再回到i站积累的疲劳值的最小值。如果从i站坐j分钟无法回到i站，则输出-1
示例：
5 3
-1 5 1 3 4
5 -1 4 4 3
1 4 -1 5 1
3 4 5 -1 5
4 3 1 5 -1

输出：
-1 2 6 
-1 6 8 
-1 2 6 
-1 6 9 
-1 2 6