当前位置: 首页 > 面试经验 >

20220903京东Java岗笔试题解

优质
小牛编辑
164浏览
2023-03-28

20220903京东Java岗笔试题解

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个

考虑不同子串太麻烦,可以反向考虑,考虑每一对可以匹配的括号对答案的贡献。考虑这样一个子串: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)
#京东##京东笔试##笔试#
 类似资料: