百度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的元素的影响就行
#我的实习求职记录#