3.15 oppo笔经

1.给一个数组和另一个数t，求sum - 2 * nums[i]是否在[1, t]之间，简单题

2.给一个数组，数组元素大小在0 ~ 1e9，对于每一个数组元素，求去掉这个数组元素后数组中未出现的最小数是多少。

思路：先接收数组，同时把每个数放到一个map中，key是这个数，value是这个数出现的次数。随后找不去掉任何数的数组中未出现的最小数gap，直接遍历一遍数组，如果nums[i] + 1在map中不存在，则gap = min(gap, nums[i] + 1)，特判当0不在map中时，gap = 0。最后再遍历一次数组，如果nums[i]比gap大则输出gap，否则依靠map判断nums[i]在数组中出现的次数，如果大于1则输出gap，否则输出nums[i]。
这题用Java写会因为输入输出超时😅，换cpp写的

3.给一个字符串表示一个数，这个数里面有些位可能带有?，求有多少种方案可以使得替换掉数中的？后得到的数能被3整除。答案要排除前导0的情况，并对1e9 + 7取模

思路：记忆化搜索，先找出字符串中的所有?并统计当前所有不是?的位的数字之和，这个数字之和对3取余得到数a，假设替换？的数字之和取余得到b，要满足(a + b) % 3 == 0才能算一个方案。记忆集设为memo[n][3]，n是？的个数。记忆化搜索中除了常规的i和n还有其他两个参数pre和canZero，pre表示之前位数字的和对3取余的结果，canZero表示该位能否取0，结果对i和pre做记忆化。

#笔试##oppo##牛客AI配图神器#