京东Java岗笔试题及解析（2022年9月3号）

╰半夏微凉° 2023-09-27 08:23 20阅读 0赞

新鲜出炉的京东Java岗笔试题及解析，面试时间：2022年9月3号。

## T1 ##

小红拿到了n个物品，每个物品的品质为ai。这n个物品中至少有一个真品。
    已知所有真品的品质都是相同的，但赝品的品质比真品低。小红想知道，这n个物品中最多有多少赝品。
    输入描述：
    第一行输入一个正整数n，代表小红拿到的物品数量。
    第二行输入n个正整数ai，代表每个物品的品质。
    n≤1e5, ai ≤ 1e9
    输出描述：
    一个整数，代表赝品的数量。
    
    input:
    1
    5
    
    output:
    0
    
    只有一个物品，显然是真品

签到题，排个序统计一下就可以了。

from collections import Counter
    
    n = int(input())
    a = list(map(int, input().split()))
    print(len(a) - Counter(a)[sorted(a)[-1]])

## T2 ##

题目描述
    小红拿到了一个数组，她每次可以进行如下操作之一：
    选择一个元素x，将其分裂为1和x-1。
    ·选择一个元素x，将其分裂为a和b，需要保证a*b=x
    小红希望用最少的操作次数，将所有数组的所有元素全部变成1。你能帮帮她吗？
    输入描述：
    第一行输入一个正整数n，代表数组的长度。
    第二行输入n个正整数ai，代表小红拿到的数组。
    1 ≤ n, ai ≤ 1e5
    输出描述：
    一个整数，代表最小的操作次数。
    
    input:
    2
    2 6
    
    output:
    5

预处理所有因数，然后记忆化搜索即可，不想写递归也可以写数组格式dp。

from functools import lru_cache
    
    n = int(input())
    a = list(map(int, (input().split())))
    v = int(1e5) + 1
    fs = [[] for _ in range(v)]
    for i in range(2, v):
        for j in range(2 * i, v, i):
            fs[j].append(i)
    
    @lru_cache(None)
    def solve(n):
        if n == 1:
            return 0
        ans = 1 + solve(n - 1)
        for f in fs[n]:
            ans = min(ans, 1 + solve(f) + solve(n // f))
        return ans
    
    print(sum(map(solve, a)))

## T3 ##

题目描述
    定义一个括号串的权值为，它的最长合法括号子序列的长度。
    例如，"())())的权值是4，它的最长合法括号子序列为"()()”
    现在求一个给定括号串的所有子串权值之和。
    输入描述：
    一个仅包含'('和')'的字符串，长度不超过2e5。
    输出描述：
    所有子串的权值和。
    
    input:
    (()())
    
    output:
    26
    
    解释：
    权值为2的子串有2个
    权值为4的子串有2个
    
    插播一条广告：需要开通正版JetBrains全家桶的可以联系我，56元一年，正版授权，官网可查有效期，
    有需要的加我微信：poxiaozhiai6，备注：905。

考虑不同子串太麻烦，可以反向考虑，考虑每一对可以匹配的括号对答案的贡献。考虑这样一个子串：`xx()x`，x表示任意字符。如何计算中间这对括号的贡献呢？其实可以看出来，带有这对括号的子串的数量只和它左右侧的字符数量有关，根据上面这个字符串，可以得到的带有这个括号的子串：

*  xx()x
 *  xx()
 *  x()x
 *  x()
 *  ()x
 *  ()

也就是6个。如何得到这个数字呢？实际上就是（括号左侧的字符数+1）\*（括号右侧的字符数+1）。为什么这样是正确的呢？因为我们要考虑这对括号的贡献，那么我们就要考虑所有包含该括号的子串。假设左括号左边有n个数字，那么左边其实有(n+1)种选择——什么都不选、选1个、选2个、选3个...因为要求是连续子串，所以只能有(n+1)种选择，右侧同理。两边选择的方案数需要乘起来。

那么只需要遍历一下字符串，查到每一个右括号对应的左括号位置，(左括号左侧的字符数+1)\*(右括号右侧的字符数+1)则为这个括号的贡献，总复杂度O(n)

s = input()
    ans = 0
    n = len(s)
    l = []
    for i, v in enumerate(s):
        if v == '(': l.append(i)
        elif l: ans += 2 * (l.pop() + 1) * (n - i)
    print(ans)

## 最后，点个赞吧，谢谢~ ##