卖力 | 2022 summer intern oa | 挂经

发一个新鲜的卖力intern oa 挂经。一早起来做oa送了个人头T T。看往年面经，感觉大家收到的都是easy题。以为会挺简单的，没想到给跪了orz。第二个题test case 8/15
第一题 给一个list，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

08 +8:00):
底下楼层附了一个我当时写的第二题code（忽略我糟糕的implementation

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

应该用栈吧，挨个往栈里压，如果新的字符和栈顶组合字典序能变小，弹出栈顶，压入新的字符再压入刚才弹出的栈顶，最后把栈倒着输出就可以了。

楼主，第一题那个正方形的是什么意思？能不能解释一下

沽名钓誉 发表于 2021-8-20 09:49
应该用栈吧，挨个往栈里压，如果新的字符和栈顶组合字典序能变小，弹出栈顶，压入新的字符再压入刚才弹出的 ...

请问如果遇到 acccb 这样的，怎么输出 abccc 而不是 accbc 呀？

第二题栈不行的，会超时，万一是baa这个字符串的话，交换元素需要On时间复杂度，总共时间复杂度是On2， 会超时。
我认为做法是DP，dp[i]代表到目前i为止，可以交换元素的最小字符串，最后结果就是dp[n], 可以记录dp[i - 1]时候a, b, c的最后一个字符的位置，分情况来进行转移，这样最后就是On的时间复杂度，应该可以过。

patpat 请问楼主是什么时候投的哇？

auburn.bouquet 发表于 2021-8-20 23:21
patpat 请问楼主是什么时候投的哇？

8.4海投的

baonudesifeizha 发表于 2021-8-20 23:23
a和c相连的没法动   单独抠出来？

a和c应该是不能swap的，只能是相邻位置的ab或者bc