3.13百度计算机视觉算法研发工程师笔试

前面都是选择题，考察面很广，有线性代数，机器学习，图像处理等等，也有3个C++的题，但是我都是蒙的。。

一共两个编程题

第一题，balabala一堆什么异或算法。然后目的是把例如00111001这样的二进制串变成全是0。但是只能使用如00001111，010，1这样的连着的1才可以，也就是说，只需要统计有多少个连着的1的串就可以了。比如00111001，就是两个，给一个00111000和一个00000001，就可以得到全0。

解题思路：

用一个flags记录现在的情况（True代表之前是1，False代表之前是0），再有一个res统计连1的个数

从前往后遍历，如果遇到1，看一下flags是不是True，如果是True，则代表上一个字符也是1，这里的1和上个在一个字段里，直接continue，判断下一个字符。如果是False，则代表上一个字符是0，当前这个1是这段1的第一个1，所以需要res+1，同时flags变为True

如果遇到的是0，那么就把Flags变成False就可以了。

结果返回res就是连续的1的个数，也是需要操作的异或次数。

第二题

有一串正整数，为a0...ai...an，如果取ai，那么你就得到了分数（就是ai的大小），但同时要删掉所有的数值等于ai-1和ai+1的数字。问怎么选能得到最大的数值。例如对于1,2,3,3,4，正确的选法是取1,3,3这样数值是7。这里要注意的就是3是可以有多少取多少的。

解题思路就是先做一个字典，统计每个数字出现了几次。然后用一维动态规划dp。dp的定义就是在选取<=当前这个数值的所有数字的时候，最大的分数是多少分。那么我们首先要计算ai到底价值是多少，也就是ai*ai出现的个数（利用前面统计的字典），把这个价值记作score，然后计算score+dp[i-2]。这里说一下为什么是i-2，因为如果我们选取了ai，那么我们应该删除ai-1和ai+1，所以我们是不能考虑状态dp[i-1]的，而i+1和我们又没关系，所以这样计算就可以。然后dp[i]选取score+dp[i-2]与dp[i]的最大值就可以，分别对应的是选取ai和不选取ai（选取了ai-1）的结果

代码如下：

n = int(input())

a = list(map(int, input().split()))

num_count = {}

for num in a:

    num_count[num] = num_count.get(num, 0) + 1

max_num = max(a)

# print(max_num)

dp = [0] * (max_num+1)

dp[1] = num_count.get(1,0)

for i in range(2,max_num+1):

    score = i * num_count.get(i,0)

    if i > 2:

        score += dp[i - 2]

    dp[i] = max(dp[i-1], score)

print(dp[max_num])