2024暑期实习生笔试【百度】
记录一下找实习过程种各大厂的笔试，水平有限
笔试题均使用Python编码
（听大佬建议把图删了，换为文字描述）
1、归零
题目描述：A最近学习到一种新的运算，叫异或，运算符记为xor。这是对两个相同长度的二进制串(仅含有0或1的字符串)进行的运算，相同位上对应的数字如果不同则该位运算结果为1，否则为0。例如：
现在小A手上有一个二进制串s，他想让这个二进制串异或上若千个长度相等且所有的1连续的二进制串(如000111，1100，010，1等，但01010，101等不合法)，使得s所有位都为0。小A想知道最少需要进行多少次异或运算?
输入描述：
第一行一个正整数T，表示有T组数据；
接下来每一组数据对应一行，首先入x，表示该二进制串长度;之后输入一个长度为X的二进制串。中间用空格隔开。
1≤x<5*10e+4 1≤T≤100
输出描述：
输出T行，每一行一个整数，表示该数据下的最小异或次数
样例输入：
2
8 00011101
1 0
样例输出：
2
0
样例解释：
第一组数据：一种方法是异或上00000010和00011111即可
第二组数据：原串已经为0，不需要进行异或操作
解法思路：采用BFS搜索N叉树最短路径的解法。输入的二进制串作为根节点，将满足长度相等且所有1连续出现的二进制串视作子节点，通过层序遍历的方式两两异或，当异或结果为0时，遍历结束返回当前的step即为最小的step。
（还另外写了rep_one，判断所有1连续出现的二进制串，自己都觉得很麻烦。。。思路不是太好）
def rep_one(binval):
# 判断是否连续出现1
# 1000011111 False, 011110000 True
sz = len(binval)
if sz <= 2: return True
for i in range(sz):
if binval[i:i+2]=='01':
for j in range(i+1, sz):
if binval[j:j+2]=='01':
return False
return True
elif binval[i:i+2]=='10':
for j in range(i+1, sz):
if binval[j:j+2]=='01':
return False
return True
return True
def xor(nums):
# BFS：N叉树最短路径
# 00011101 取 11101，5位二进制可以表示2**5=32种状态
# 11101作为起点，00000作为终点，寻找异或操作后的最短路径
# 对5位二进制种所有满足rep_one的情况进行异或遍历
queue = [str(int(nums))]
visited = set()
step = 0
while queue:
sz = len(queue)
for i in range(sz):
cur = queue.pop(0)
if int(cur, 2) == 0:
return step # 遍历结束，返回当前的step即为最小的step
for j in range(1, 2**len(cur)):
binval = bin(j)
if rep_one(binval):
if binval not in visited:
visited.add(bin(int(cur,2)^j)[2:]) # 经过bin后显示0b100111，取[2:]
queue.append(bin(int(cur,2)^j)[2:])
step += 1
return -1
n = int(input())
if n != "":
for i in range(n):
s = input()
x = s.split(' ')
print(xor(str(x[1])))
———————————————————————————————
上面的想法过于复杂，应该可以直接统计不连续 1 的出现的次数，即为最少的异或运算次数。
def xor(binval):
# 统计不连续 1 的出现的次数，即为最少的异或运算次数
# 1000011111→2, 011110000→1
sz = len(binval)
flag = 0
if sz <= 2: return True
for i in range(sz):
if binval[i:i+2]=='01':
flag += 1
for j in range(i+1, sz):
if binval[j:j+2]=='01':
flag += 1
return flag
elif binval[i:i+2]=='10':
flag += 1
for j in range(i+1, sz):
if binval[j:j+2]=='01':
flag += 1
return flag
return flag
评论区给的统计方法，更简洁：
def xor(binval):
count = 0
index = 0
while index < len(binval):
if binval[index] == '1':
count += 1
while index < len(binval) and binval[index] == '1':
index += 1
else:
index += 1
print(count)
2、删除游戏
题目描述：现在给你一个包含 n个正整数的序列a，你可以进行许多次提作直到序列为空，每次提作可以选定当序列中的一个数ai并删除，然后删除所有等于ai+1或者ai-1的数，都除的数无法再减之后的提作选中这样的一次操作能让你获得ai分，请问你最多能获得多少分数？
输入描述：
第一行一个正整数n，表示序列a 的长度
接下来一行包含n个正整数a1,a2,...an,分别为序列a中的n个数
n≤100000，1≤ai≤100000
输出描述：
输出可以获得的最高分数
样例输入：
样例1
3
1 2 3
样例2
5
1 2 3 2 2
样例输出：
样例1
4
样例2
6
样例解释：
对于样例2，第一次可以选择删除任意一个等于2的数，这次操作同时除等于1和3的数，获得2分目序列中剩余的数为[2,2],
之后可以连续两次操作都选择等于2的数，这样总共能获得6分。
解法思路：采用回溯算法（遍历「树枝」）。把输入1 2 3 2 2看作N叉树的路径，暴力穷举所有路径的得分总和（选择路径时需要完成ai加1和ai减1的删除操作，同时还存在重复路径的情况，如有三个重复的2，需要用索id区分）
def maxSorce(nums):
# 回溯算法
# 把1 2 3 2 2看作N叉树的路径
# 暴力穷举所有路径的得分总和（选择路径时需要完成ai加1和ai减1的删除操作）
res = []
track = {}
delval = []
def backtrack(nums, track, delval, flag):
if flag == len(nums)-1: # flag等于len(nums)-1时，相当于走到叶子节点，可以作为结束条件
res.append(sum(track.values()))
return
for id, nums_i in enumerate(nums): # 由于可能存在重复路径（2 2 2），利用id和num_i记录已选择的路径
if id in track or nums_i in delval:
continue
# track.append(nums_i)
track[id] = nums_i
delval.append(nums_i-1)
delval.append(nums_i+1)
backtrack(nums, track, delval, id)
track.pop(id)
delval.pop(-1)
delval.pop(-1)
backtrack(nums, track, delval, 0)
return max(res)
n = int(input())
nums=[]
s = input()
if s != "":
for x in s.split():
nums.append(int(x))
print(maxSorce(nums))
—————————— 3.16更新 ——————————
解法思路：采用动态规划进行状态转移。
具体实现过程如下：
1、统计每个数出现的次数，用一个字典count来保存。
2、动态规划求解最大分数，用一个数组dp来保存。
3、初始化dp[1]为count[1]，表示只有1这个数时的最大分数。
4、从2开始遍历到序列中的最大数max(a)，对于每个数i，有两种选择：
- 不选i，此时最大分数为dp[i-1]；
- 选i，此时需要跳过i-1和i+1，最大分数为dp[i-2] + i * count[i]（这里i-2考虑跳过i-1的情况，i+1是未知状态）。
5、最终返回dp[-1]，即为最大分数。
def maxSorce_dp(nums):
# dp数组定义：第i个数的最大得分和为dp[i]
# 选择：选i or 不选i
from collections import Counter
count = Counter(nums)
dp = [0]*(max(nums)+1)
dp[1] = count.get(1, 0) # count中存在1返回其频次，不存在则返回0
for i in range(2, max(nums)+1):
dp[i] = max(dp[i-2]+count.get(i, 0)*i,dp[i-1]) # 只考虑-1
return dp[-1]
n = int(input())
nums=[]
s = input()
if s != "":
for x in s.split():
nums.append(int(x))
print(maxSorce_dp(nums))
#春招实习笔试##春招笔试##春招##笔试#
博世一面2人在聊