百度3.13-算法岗笔试AK

1. 字符串异或运算

只需要判断字符串中不连续的1的个数就行

2. 删除游戏

描述：

假设输入一个数组nums，其中的元素大于0小于100000

题目要求做的是：最大化结果分数score

如果选中一个数i的话，就将其添加到结果分数中，即(score+ i * freq（i出现的频率）)，那么 i - 1和i + 1就不能被选择。

解法:

动态规划。

维护两个dp数组left_dp，right_dp

left_dp[i][0]表示从1到 i 位置不选中 i 元素获得的最大分数

left_dp[i][1]表示从1到 i 位置选中 i 元素获得的最大分数

要注意的是元素频率为0可以直接继承前一个状态的最大值，

即 left_dp[i][0] = left_dp[i][1] = max(left_dp[i - 1][0], left_dp[i - 1][1])

left_dp[i][0] = max(left_dp[i - 1][0], left_dp[i - 1][1])

left_dp[i][1] = left_dp[i - 1][0] + i * （i出现的频率）

right_dp[i][0]表示从max_value(数组中的最大值)到 i 位置不选中 i 元素获得的最大分数

right_dp[i][1]表示从max_value(数组中的最大值)到 i 位置选中 i 元素获得的最大分数

right_dp[i][0] = max(right_dp[i + 1][0], right_dp[i + 1][1])

right_dp[i][1] = right_dp[i + 1][0] + i * （i出现的频率）

最后的结果需要遍历dp数组，为max(left_dp[i][1] + right_dp[i][1] - i * i出现的频率))

最后的减号是因为元素 i 被选中了两次。

不使用right_dp应该也能过，只需要注意频率为0的元素的影响就行