Bob Blog

京东笔试（8.6）

题型：选择题 * 30（部分多选，每题2分）+ 编程题 * 2（40分）

选择题涵盖的面比较广，从机器学习到深度学习，从C++到python，还有数据库相关的问题，但题目应该大都属于比较基础的概念。sql考察 select * from至少两次，python考察object，type等类相关概念至少两次。

编程题（1）最长公共字符串问题（不连续）

给定两串等长DNA序列(A, B)，求他们最长公共字符串的长度。

动态规划求解：

初始化DP [num+1] [num+1]大小的矩阵，
   
边界：DP [0] [:] = DP [:] [0] = 0
   
求解：if A[i-1] == B[j-1]: 	DP [i] [j] = 1+DP [i-1] [j-1]
   
​	 else: DP [i] [j] = max(DP [i-1] [j], DP[i] [j-1])
   
输出：DP [num] [num]

def max_sub(mat, num):
    dp = [[0 for _ in range(num+1)] for _ in range(num+1)]
    A = mat[0]
    B = mat[1]
    # dp[1][1] = A[0] == B[0]
    for i in range(1, num+1):
        for j in range(1, num+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = 1+dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    return dp[num][num]

编程题（2）回文素数

输入M，N，对于任意M<x<N，如果去掉x中的任一数字，其为回文素数，则满足题目要求，有多少这种数字？（若去掉一位数字后以0开头，则不满足要求）

选择了暴力求解的方式，对每个x，分别去掉其中一位数字后，判断其是否为回文素数。（ac：18%，时间超限）

def digit2num(rem):
    ans = 0
    for i in range(len(rem)):
        ans += rem[i]*(10**i)
    return ans
   
def check_hui(num):
    digits = []
    while num != 0:
        digits.append(num%10)
        num //= 10
    while(digits[-1] == 0):
        digits = digits[:-1]
    print(digits)
    count = 0
    flag = True
    rem = []
    for i in range(len(digits)):
        rem.extend(digits[:i])
        rem.extend(digits[i+1:])
        for j in range(len(rem)//2):
            if rem[i] != rem[-i-1]:
                flag = False
                break
        if flag:
            print('hhh')
            new_num = digit2num(rem)
            if check_prime(new_num):
                count += 1
    return count
   
def check_prime(num):
    for i in range(2, int(num**0.5)):
        if num%i == 0:
            return False
    return True
   
if __name__ == '__main__':
    nums = input()
    nums = list(map(int, nums.split()))
    low = nums[0]
    high = nums[1]
    ans = 0
    for i in range(low, high+1):
        huis = check_hui(i)
        ans += huis
    print(ans)