9.3京东笔试

又是凌晨笔试的一天。。。

算法岗第二批笔试，20选择+3编程

选择包括F1-score计算，栈数据结构，概率，MySQL，Python语句，二分查找，矩阵特征值等。大概也就一两道不会。

编程1：

找到每个数x的最小因子p使得p*p>x，取sqrt遍历维护变量即可。

import math
def factor(x):
    mini = float("inf")
    res = -1
    for i in range(1, int(math.sqrt(x)) + 1):
        if x % i == 0:
            fac = x // i
            num = fac * fac
            if num < mini and num > x:
                mini = num
                res = fac
    return res

t = int(input())
for i in range(t):
    x = int(input())
    res = factor(x)
    print(res)

编程2：

定义分裂一个数字x可以为其两个因子a、b (a*b=x)，或者为1、x-1。求将数组中所有的数全分裂成1的最小分裂次数。

本人用Python递归写的，不知道是超时了还是什么，样例可以过但是用例一个都没过。。。

思路就是base case为1、2、3，其他的时候用因子来分裂x。贴一下代码有大佬可以帮忙看一下。

import math
def split(x):
    if x == 1:
        return 0
    elif x == 2:
        return 1
    elif x == 3:
        return 2
    fac1 = 0
    fac2 = 0
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0 and i>fac1:
            fac1 = i
            fac2 = x//i
    if fac1 == 0 and fac2 == 0:
        fac1 = 1
        fac2 = x-1
    cnt1 = split(fac1)
    cnt2 = split(fac2)
    cnt = cnt1+cnt2+1
    return cnt

n = int(input())
res = 0
arr = list(map(int,input().split()))
for num in arr:
    res += split(num)
print(res)

编程3：

没太看懂题意，是())())括号匹配问题。定义最长匹配子序列长度为n，求这个序列的最大匹配子序列长度？

样例为())())，解释为()匹配长度为2的一共有9个，()()匹配长度为4的一共有2个，所以返回26。。。人傻了

京东8成也G了。。。

#京东笔试##京东#

全部评论

推荐最新楼层

二月秋风

新华三_c++开发

第三题例子属实看不懂，无语子

2 回复分享

发布于 2022-09-03 21:17 重庆

好想拿个offer

门头沟学院大数据开发工程师

第三题是牛客必刷101原题

点赞回复分享

发布于 2022-09-03 23:08 浙江

还是想躺平的秋招侠很想踩缝纫机

哈尔滨工程大学 Java

第二题0不知道为啥自己测试都能过

点赞回复分享

发布于 2022-09-03 22:45 黑龙江

8点可以起床

深圳大学 Java

元素分裂我用因数求解，效率慢了点。大佬们要怎么联系做题速度和思路啊啊啊啊，前端人很痛苦。 let n = 2, count = 0; let arr = '2 6&(31168)#39;.split(' &(30184)#39;); let isPrime = (x) => { for (let i = 2; i <= Math.sqrt(x); i++) { if (x % i == 0) return false; } return true; } for (let i = 0; i < n; i++) { let x = parseInt(arr[i]), split = new Array(); if(x == 1){ continue; } split.push(x); while(split.length != 0){ let xx = split.pop(); if(xx == 2 || xx == 3){ count += (xx - 1); } else if(isPrime(xx)){ count++; split.push(xx-1); }else{ for(let j = 2; j <= xx / 2; j++){ if(isPrime(j) && xx % j == 0){ count++; split.push(j); split.push(parseInt(xx / j)); break; } } } } } console.log(count);

点赞回复分享

发布于 2022-09-03 21:49 广东

牛客273648364号

上海交通大学算法工程师

第二题直接暴力dp import math nums = [1,1,1,1,1,30] max_num = max(nums) dp = [1000000]*(max_num+1) dp[1] = 0 for i in range(2,max_num+1): for j in range(1,math.floor(math.sqrt(i))+1): if i % j ==0: x = i//j dp[i] = min(dp[j]+dp[x]+1,dp[i]) dp[i] = min(dp[i], dp[i-1]+1) res = 0 for num in nums: res += dp[num] print(dp,res)

点赞回复分享

发布于 2022-09-03 21:27 上海

Noerror!

中国科学院大学 C++

第一个题我也是遍历穷举因子，为啥我就超时了，只过了一半😭

点赞回复分享

发布于 2022-09-03 21:21 广东

Keen06

门头沟学院 Java

所有子串的有效长度和，例子中有9个子串有效长度为2，2个子串有效长度为4，和为9*2+2*4=26。我过22.22%，其他的超时，O(n2)的复杂度。。。。

点赞回复分享

发布于 2022-09-03 21:21 江苏