[关闭]
@yanbo01haomiao 2021-07-12T10:28:30.000000Z 字数 2415 阅读 422

T04-18

面试

题目除第一题外均为acm模式，需要自行处理输入输出。

第一题：链表的最小字典序

题目描述：已知一个无环单链表，你可以对其进行旋转操作。求在允许任意次数的旋转的情况下输出该链表的最小字典序情况。

注意 1： 旋转操作：已知链表 1->2->3->4,

包括原链表在内经过旋转有且仅有以下情况：

4->1->2->3

3->4->1->2

2->3->4->1

1->2->3->4 （原链表）

这几种情况下字典序最小的为原链表，输出为 1->2->3->4。

注意 2：字典序最小是在字典序大小的概念下的，字典序的比较定义为:序列(a)的字典序小于序列(b)：存在一个位置k，满足所有的i < k时候，ai = bi,ak < bk。 例如 21453 的字典序小于 21534。换言之，如果a和b的前若干位的子序列一致，到某一位不一致，这不一致的字典序小的整体字典序较小。字母按照字母表字典序递增，数字按照大小递增。

示例： 输入： 2->2->5->2->2

输出： 2->2->2->2->5

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* circleList(ListNode *head) {
  13.     }
  14. };

第二题：广告发放

你是广告投放者，现在已知有 n 个用户，你有 k 个广告需要投送出去，每个用户设定了一个时间 t， 代表该用户设置的接收第一封广告的时间为 t，接收第二封广告时间为 2t，以此类推。如果有用户接收时间一致，优先发给编号较小的用户。输出发送广告的用户编号序列，从1排序。

此题为 ACM模式，需要自行处理输入输出。

  1. 输入：
  2. 第一行： n  k
  3. 第二行： t1
  4. 第三行： t2
  5. ...
  6. 第 n 行： tn
  8. 输出：
  9. 第一行： idx1
  10. 第二行： idx2
  11. ...
  12. 第 k 行： idxk
  14. 举例：
  15. 输入： 有3个用户，3封邮件，第一个用户设定时刻3接收，第二个用户设定时刻6接收，第三个用户设定时刻9接收
  16. 3 3
  17. 3
  18. 6
  19. 9
  20. 输出： 第一封邮件在时刻3发送给用户1，第二封邮件在时刻6发送给用户2，虽然此时用户2也接收邮件，但是1比较小，先发给1，第三封邮件在时刻6发送给用户2，邮件发送完成，结束
  21. 1
  22. 1
  23. 2
  25. 输入：
  26. 5 8
  27. 2
  28. 4
  29. 3
  30. 6
  31. 9
  32. 输出：
  33. 1
  34. 3
  35. 1
  36. 2
  37. 1
  38. 3
  41. 解释：时刻表如下，4(1)代表时刻为4是第一个用户的
  42. 依次取到2，3，4(1),4(2)，6（1），6（3）对应的用户为1，3，1，2，1，3
  43. 5 10
  44. 2  4  6  8  10
  45. 4  8  12 16  20
  46. 3  6  9  12  15
  47. 6  12 18 24
  48. 9  18 27

第三题：游戏俱乐部

游戏俱乐部每天都开放T组每组 n 个的小游戏，每个游戏只需要 1个单位时间即可完成。每个游戏必须在时间ti内完成，否则就会扣除对应积分wi。

如果你想称为今天扣分最少的人，请问你该如何安排游戏顺序，请输出最少扣分。你进入俱乐部时间为 0 ，不计每组和每个游戏间赶路时间。

  1. 输入：游戏总组数量 T （1<=T<=1000）
  2. 第i组游戏数量 n 
  3. 必须在ti时刻内完成
  4. 未完成扣除的积分wi
  5. ...
  6. 第T组游戏数量 n 
  7. 必须在ti时刻内完成
  8. 未完成扣除的积分wi
  9. 输出：最少扣分
  11. 举例：
  12. 输入：
  13. 1  一组数据
  14. 3  三个游戏
  15. 3 1 1 三个游戏依次需要在时刻3，1，1内完成
  16. 3 6 9 三个游戏未在时刻3，1，1内完成扣除积分3，6，9
  17. 输出： 6  先玩游戏3，时刻1时完成，游戏2失败，扣除6分，然后玩游戏1，时刻2完成
  19. 输入：
  20. 2
  21. 4
  22. 1 1 2 2
  23. 6 4 2 9
  24. 3
  25. 1 3 2
  26. 5 3 2
  27. 输出：13  先玩第1组游戏1，时刻1，第一组游戏2、第二组游戏1失败4+5 =9，然后玩第一组游戏4，时刻2，第一组游戏3、第二组游戏3失败，9+2+2=13，最后游玩第二组游戏2，时刻3结束，共扣分 13.

第四题：字符串相等

判断a,b两个字符串是否相等定义：

1）如果a,b两个字符串为奇数长度，那么就一个字符一个字符比较是否相等；

2）如果a,b两个字符串为偶数长度，将a等分为a1,a2两个子串，b同理分为b1,b2，只要a1==b1 && a2 == b2 或者 a1==b2 && a2 == b1其中任意一个满足就认为其相等。

这里的相等是递归定义的，参见例子。

  1. 输入：t 表示有t组数据
  2. 接下来有2t行数据，代表每一组数据中的a和b
  3. 输出：如果a和b按照本题相等的定义相等，输出YES，反之输出NO
  5. 例子：
  6. 输入：
  7. 4
  8. aabb
  9. bbaa
  10. abaaaa
  11. aaaaba
  12. abb
  13. aba
  14. abbbabaa
  15. aaabbbab
  16. 输出：
  17. YES aa == aa,bb==bb
  18. YES aba == aba,aaa==aaa
  19. NO 3个字符直接比较不相等
  20. YES 这里8个字符，切分成abbb,abaa和aaab,bbab，其中又是偶数字符串，继续切分
  21. 发现 abbb == bbab,abaa = aaab，则整体字符串相等

第五题：打地鼠

有一个 n * m 个格子的矩阵 mp，mp[i][j]代表每经过时间mp[i][j]间隔后第 i 行第 j 列的格子会出现地鼠。

初始：时间为 0，你的位置在第1行第1列的格子中, mp[1][1]为起点，此时不视作打地鼠。

移动和打地鼠：每秒钟你都会向上、下、左、右任意一个方向移动一格，但是不能移动到矩阵外部，同时也不能移动到上次的格子中（举例：本次你从a -> b，代表下一次你不能从 b -> a，但是你可以走个圈回到a）。如果你移动到格子时刻，地鼠刚好出现，那么你就可以打一次地鼠。

终点：终点是第 n 行第 m 列的格子，也就是矩阵的右下角边界。

时间要求：现在你有 t 秒，确保你在 t 秒时候正在第 n 行第 m 列的格子情况下，你一共能打多少下地鼠。如果你在 t 秒时候不在第 n 行第 m 列的格子，记作打了 0 次地鼠。

  1. 输入：n m t
  2. 每一行地鼠矩阵时间 
  4. 输出：打地鼠的次数
  6. 例如：
  7. 输入：
  8. 2 2 6
  9. 1 1
  10. 1 1
  11. 输出：6  一种可行的行走方案 (1,1)-> (1,2)-> (2,2)-> (2,1)-> (1,1)-> (1,2)-> (2,2)
  13. 输入：
  14. 2 2 5
  15. 1 1
  16. 1 1
  17. 输出： 0  此时无论如何到达不了右下角
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注