美团机器学习实习 笔试记录 4.16
ac4题,最后一个18%应该是超时了。
第一题ac
直接暴力,需要注意
1. 并列第一
2. 同一个人只能算一次
两种情况
用set保存下学生编号避免重复计算人次就好。
# -*- coding:utf-8 -*- try: while True: N, M = map(int, input().split()) scores = [] for i in range(N): scores.append(list(map(int, input().split()))) res = set() for i in range(M): max = -1 ans = [] for j in range(N): if scores[j][i] > max: ans = [] ans.append(j) max = scores[j][i] elif scores[j][i] == max: ans.append(j) else: pass for it in ans: res.add(it) print(len(res)) except: pass
第二题ac
直接实现伪代码,用set()判断是否开始循环即可。
# -*- coding:utf-8 -*- try: while True: a, b, m, x = map(int, input().split()) s = set() while True: x = (a * x + b) % m if x in s: print(len(s)) break else: s.add(x) except: pass
第三题ac
有个坑,最开始是想直接 left = K//N, right = K%N,最后结果就是 nums[left][right],只过了45。
后面发现要注意数字重复的情况:比如 2 2 1 的排序是 (2,1) (2,1) (2,2) (2,2) (2,2) (2,2)
# -*- coding:utf-8 -*- # try: while True: N, K = map(int, input().split()) nums = sorted(list(map(int, input().split()))) if N == 0: continue leftIndex = K // N # rightIndex = K % N # if rightIndex == 0: # rightIndex = N # leftIndex -= 1 cnt = 1 l = leftIndex - 1 r = leftIndex + 1 while l >= 0 and nums[l] == nums[leftIndex]: l -= 1 cnt += 1 while r < N and nums[r] == nums[leftIndex]: r += 1 cnt += 1 leftIndex = l + 1 rightIndex = (K - leftIndex * N) // cnt if rightIndex == 0: rightIndex = N leftIndex -= 1 print("({},{})".format(nums[leftIndex], nums[rightIndex-1])) # # except: # pass
try: INT_MAX = 99999999 n, k = map(int, input().split()) A = sorted(list(map(int, input().split()))) cen = (n + 1) / 2 last_idx = 0 min_res = INT_MAX temp = -1 for i in range(n): if A[i] < k: temp = i if A[i] == k and min_res > abs(cen - 1 - i): last_idx = i min_res = abs(cen - 1 - i) left, right = 0, 0 if min_res == INT_MAX: n += 1 left = temp + 1 right = n - left - 1 else: left = last_idx right = n - left - 1 if left == right: print(0) elif left < right: sub = right - left if min_res == INT_MAX: sub += 1 print(sub - 1) else: sub = left - right if min_res == INT_MAX: sub += 1 print(sub) except: pass
第五题
滑动窗口遍历S子串
DFS 匹配T子序列
用字典保存重复结果 + 剪枝,过18%超时,目测应该是DP
# -*- coding:utf-8 -*- MOD = 1e9 + 7 def helper(s, t, len_s, len_t, now_s, now_t, ans): if now_s == len_s: ans[0] += 1 ans[0] %= MOD return 0 if now_t == len_t: return 0 for i in range(now_t, len_t): if s[now_s] == t[i] and len_s - now_s <= len_t - i: helper(s, t, len_s, len_t, now_s+1, i+1, ans) try: while True: S = input() T = input() lenS = len(S) lenT = len(T) ans = [0] dic = {} for lens in range(1, lenS+1): left = 0 while left + lens <= lenS: # print(S[left:left+lens]) x = S[left:left+lens] if x in dic: ans[0] += dic[x] ans[0] %= MOD else: tt = ans[0] helper(x, T, lens, lenT, 0, 0, ans) dic[x] = ans[0] - tt # print("xxx") left += 1 print(int(ans[0])) except: pass