0411网易互娱-数据挖掘算法AC
题目1：三数求和
给定数组nums和Target，求数组中i,j,k a[i] + a[j] + a[k] = target i != j != k的三元组个数。
AC
import sys
from collections import Counter
def two_pointers(nums, target):
left = 0
right = len(nums) - 1
cnt = Counter(nums)
res = 0
while left < right:
tsum = nums[left] + nums[right]
if tsum < target:
left += 1
while left < right and nums[left] == nums[left-1]: # 去重
left += 1
elif tsum > target:
right -= 1
while left < right and nums[right] == nums[right+1]: # 去重
right -= 1
else:
if nums[left] == nums[right]: # 如果左右两数相等，则有C(n,2) = n*(n-1)/2种组合
res += cnt[nums[left]] * (cnt[nums[left]] - 1) // 2
else: # 两数不等，则有n_left * n_right 个数
res += cnt[nums[left]] * cnt[nums[right]]
left += 1
while left < right and nums[left] == nums[left-1]: # 去重
left += 1
right -= 1
while left < right and nums[right] == nums[right+1]: # 去重
right -= 1
return res
def func(nums, target):
if len(nums) < 3:
return 0
nums.sort()
res = 0
for i in range(len(nums)):
tmp_target = target - nums[i]
res += two_pointers(nums[i+1:], tmp_target)
return res
nums = input().strip().split(',')
nums = [int(i) for i in nums]
target, nums = nums[0], nums[1:]
res = func(nums, target)
print(res) 题目二：闯关问题 给定一个数组，可以从任意位置开始并到最后。闯关后会获得想要奖励，不能闯相邻关卡。
解题：动态规划，参考leetcode抢劫问题
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
AC 代码就不贴了，直接在牛客上写的，没有保存本地。
#网易互娱笔试##网易互娱##笔试题目##数据挖掘工程师#
投递比特大陆等公司10个岗位