SIG 25 intern 8.2 OA / 求米

lz今天白嫖了SIG的OA，之前刷了下地里和小红书里面的，给我的感觉是SIG今年的题库有很多题，看这些肯

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

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

完有点累了等有空写一下题解

贴一下lz之前做的xhs上的题和对应的解；这里就直接抱图当mock做了（感觉题库很大，那么mock的意义在于简单的不用做，难的做不起（。。事实证明是这样的= =
Q1，找数组中出现的奇数0计数，判断为0的特殊情况，其他的正常整除计数就行了，感觉可以用to_string方法逐个遍历为’0’的情况，这样给lz的感觉更快？
Q2，向前替换vowel元素，lz的思路是先遍历一遍string，当unordered_set里面的元素出现时(vowel)就将当前下标和vowel按顺序放入vector<pair<int,char>>，之后遍历vector容器，找出从下一个位置i+1开始，替换为当前i位置的元素，边界情况用(i+1) % size()，返回最开头，替换为末尾的i元素
Q3，给一个图，判断图中的一个元素是否是局部最大值，由于这里说了基础的matrix的元素为0，故遍历图的时候遇到0直接continue，只读>0的数字，之后读到就进入check函数，又进行一次On2的遍历，这里之前lz一直出错发现是把自身matrix[c][r] = =忘排除了，边界条件跟dfs遍历边界差不多，只不过这里多了一个边角条件，这里lz就直接用了四次判断加上把自身排除，当找到就返回，push当前的[c][r]
Q4，给一串指令，对字符串进行读取，感觉只是0/1，如果每次flip都要变一次时间复杂度上来了？而且指令只有flip和count两种，就声明了一个bool flag，当读到flip的时候flag取反，然后处理count:的情况，因为count后面的数范围在binary.size()-1的大小，之前想的是直接取r[6]-‘0’得到整数，但对于两位数或者更多应该通过不了，就直接用substr在stoi一次得到整数，对binary count一遍，如果有flag就是原来size – ‘1’ + 1的个数，如果没有就直接输出

Lz觉得这次白嫖SIG最坑的是第四题（。。之前mock了一下别人的题感觉第三题肯定是图会复杂一点就先做的第四题，没想到是第四题最麻烦= =，最开始lz是两次for循环逐个比较，只通过了140/300，后来去掉了一个for循环，创建了一个unordered_map<int,vector<int>>，先for一次存入map，int表示该数的位数，符合就存入，后面遍历map，对vector里面的数字进行比较，通过率200/300，实在比不下去了，后来想了想这样最坏的复杂度也是On2级别的，后来去看了搜索算法，感觉这个为了不超时查找应该用字典树，每个数看作可以构成树节点的digit组合，字典树构造有很多种方法，lz这里用的是指针指向next[digit]节点，默认构造函数创建nullptr，当存在时构造Trie节点，从而达到On的时间复杂度

昨天只是跑出来3这个数字= =，有点晚了，没检查代码，发现1 == 1的时候被check了，故加了一层逻辑，diff == 1，但字典树插入1只被插入了1一次，到9的时候check只会1次，为了到9check两次1，又加了一层count，记录出现的次数，今天改了一下主逻辑

3题的图其实很好懂，只不过lz当时以为又是dfs/bfs，先做的第四题数字查找后没多少时间了，直接把row column放进去再处理，代码很不美观= =，其实只需要把所有提及的坐标点都-1清理一下就好了，画个图就很好理解了