CMU Codility

CMU申请会邮件一个链接，去codility上做一个笔试，邮件里会告诉你是哪三道题，我的是：

1. ABSplit
    由a、b两种字符构成的字符串，切两刀分成三份子串，使得每一份中a的数量相同，有多少种切法。
2. AddFive
    在一个整数中添加一个“5”，可以得到的最大数字是多少。如 456->5456。
3. AlternatingCoins
    一排硬币正反面用0、1表示，如何反转最少硬币数量使得这一排硬币0、1交替出现。（dp问题）

祝好！

这个题目所有人都是一样的，只有部分专业会有

请问是什么专业

realmadrid1016 发表于 2020-12-20 17:41
请问是什么专业

scalable system

第三题用不着dp吧，虽然一开始我也觉得是dp哈哈

彭东强 发表于 2020-12-20 21:59
第三题用不着dp吧，虽然一开始我也觉得是dp哈哈

codility上的题目感觉都这样怪怪的，很长的题目，但是读完发现没有怎么考察数据结构和算法知识。我反正压缩成O(1)空间的dp交了。

第三題反正不管怎麼轉 只會有 1010101010... or 0101010101... 我是直接遍歷兩次 找較小的那個。 O(2N) time, O(1) space

ke755024 发表于 2020-12-21 13:26
第三題反正不管怎麼轉 只會有 1010101010... or 0101010101... 我是直接遍歷兩次 找較小的那個。 O(2N) tim ...

这么一说好像确实是的诶，就两种情况，找汉明距离就行了。学习了。

biubiu汪汪汪 发表于 2020-12-20 23:02
codility上的题目感觉都这样怪怪的，很长的题目，但是读完发现没有怎么考察数据结构和算法知识。我反正压 ...

我想怎么着都得遍历一遍吧，至少O(n)的复杂度，如何做出O(1)呢？纯讨论

彭东强 发表于 2020-12-22 13:37
我想怎么着都得遍历一遍吧，至少O(n)的复杂度，如何做出O(1)呢？纯讨论

没看到是o1空间，我的锅