百度笔试 机器学习/数据挖掘卷 编程题代码 2019.4.2

题目如下：

1. 题目大概意思：给定字符串，每次可以把第一个字母移到最后，问一共能产生多少个不同的字符串
2. 给字符串A和字符串B，输入Q个[l,r]左右边界对，问每一对[l,r]对应的字符串A[l:r]中包含多少个B串

我的解法：

1. Python写的第一题暴力hash过了83%? 提示时间超时 (hash字符串变成数字，不要存字符串，否则报内存错误只能过8%）。
   以下是暴力做法：

import sys
s = input()
# print(s)
N = 10 ** 6
x = abs(hash(s) % (N))
x2 = abs(hash(s+"1") % (N))
dic = [x]
dic2 = [x2]
cnt = 1
for i in range(len(s)-1):
s = s[1:] + s[0]
x = abs(hash(s) % (N))
x2 = abs(hash(s+"1") % (N)) # 多hash一次减少碰撞，正确率70%提升到83%
if x not in dic or x2 not in dic2:
dic.append(x)
dic2.append(x2)
cnt += 1
else:
break
print(cnt)

【有人给出了ac的思想】
有多少种情况取决于字符串由多少个完全相同的字符串拼接而成，要完全相同首先要长度相同，所以需要等分，要等分就是要是原串的因数。

2. 直接用python自带的count方法可以通过70%，改用trick去做能ac，下面是ac的做法

import sys
def isEqual(A,start,B):
for i in range(0,len(B)):
if A[i+start]!=B[i]:
return False
return True
A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()
count = [0]*len(A)
i = len(B)-1
while i<len(A):
start = i-len(B)+1
count[i] = count[i-1]
if isEqual(A,start,B):
count[i]+=1
i += 1
Q = int(sys.stdin.readline().strip())
for q in range(Q):
line = sys.stdin.readline().split(' ')
l = int(line[0])
r = int(line[1])
if r-l+1<len(B):
print(0)
elif l==1:
print(count[r-1])
else:
print(count[r-1]-count[l-1+len(B)-2])

最后

以上就是积极帅哥为你收集整理的百度笔试 机器学习/数据挖掘卷 编程题代码 2019.4.2的全部内容，希望文章能够帮你解决百度笔试 机器学习/数据挖掘卷 编程题代码 2019.4.2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。