oppo 240727 笔试AK

方向 机器学习
📝笔试题目思路介绍

1. n-》m（可以-1 可以整除k）
核心判断：
- 还有没有必要除以k （n/k > m?)
- 快速到要整除的位置 （n = （n // k） * k）

2. 字符串s 包含子串a b的最大数量
题目巧妙的地方 首字母大写 保证子串不会重叠（这个很关键 题目因此变得简单）
剩下的就是统计字符串s a b的各字母个数即可（ch[26])
我写了个函数判断 ch_a[26] 最多能造出多少个ch_b[26] 其实就是判断字符数量够不够

比如s最多能造出k个a串
遍历（0-k）个a串情况 + 剩余字符能造出的 x个b串
结果选最长即可

吐槽：a、b互为子串的时候（Ab、Abc）不会统计两次
这个是我在测试的时候发现的 还特意写了个if 废弃了

3. 二部图的最多增加边数

核心思路 二部图最大边数 （x*y）x、y是两个部分的节点数量
那么就是把n分成两个部分 让他们尽可能平衡
除去给出的（n-1）条边 最终结果就是x*y- （n-1）

新的问题是分配成两个部分
每一条边的u v两端 都必须分散在两个部分

给出的n-1条边会构造出k个子图（k个二分图 大小不一）
本来想用并查集弄结果没必要 用set暴力存就行

构造出k个子图[子图大小，set（左半边），set（右半边）]

然后根据大小排序 先排大子图，之后平衡最终子图两边的数量（贪心的分配节点）
最后 len（左半边节点数量）*len（右半边节点数量）-（n-1）就结束

只讲思路就不实现了

AK完还剩10min，不过选择题挺多蒙的

祝大家offer++