快手笔试 算法 3.22
第一题:给两个整数k, n 求将n分成k份后的最大乘积
k, n = list(map(int, input().split())) sig = n//k sig2 = n%k print(sig**(k-sig2) * (sig+1)**sig2)第二题:求二维矩阵从左上角到左下角的最小路径
class Solution: def find_best_path_cost(self , A ): line = len(A) col = len(A[0]) for i in reversed(list(range(line))): for j in reversed(list(range(col))): if i == line-1 and j == col-1: continue elif i == line-1: A[i][j] += A[i][j+1] elif j == col-1: A[i][j] += A[i+1][j] else: A[i][j] += min(A[i+1][j], A[i][j+1]) return A[0][0]第三题:给定S, A, B, P, 初始arr[0] = S, 接下来arr[i+1] = (arr[i] * A + B) % P, 并且arr数组里的每个数字最多出现两次,当某个数字出现3次时,终止序列生成。给定两组S, A, B, P分别生成两个序列,求两个序列的最长公共子序列
T = int(input().strip()) for _ in range(T): s1, a1, b1, p1 = list(map(int, input().split())) s2, a2, b2, p2 = list(map(int, input().split())) dic1 = dict() dic1[s1] = 1 dic2 = dict() dic2[s2] = 1 nums1 = [s1] nums2 = [s2] while True: num = (nums1[-1] * a1 + b1) % p1 dic1[num] = dic1.get(num, 0) + 1 if dic1[num] == 3: break nums1.append(num) if [s1, a1, b1, p1] == [s2, a2, b2, p2]: print(len(nums1)) continue while True: num = (nums2[-1] * a2 + b2) % p2 dic2[num] = dic2.get(num, 0) + 1 if dic2[num] == 3: break nums2.append(num) del dic1 del dic2 nlen1, nlen2 = len(nums1), len(nums2) dp = [[0 for j in range(nlen2 + 1)] for i in range(nlen1 + 1)] for i in range(nlen1): for j in range(nlen2): if nums1[i] == nums2[j]: dp[i + 1][j + 1] = dp[i][j] + 1 else: dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) print(dp[-1][-1])一直超时..有没有大佬有更好的解决思路?
第四题:三维坐标系下半径为1的求,然后与椭球:(x-a)^2/d^2 + (y-b)^2/e^2 + (z-c)^2/f^2 = 1相较,求相较后椭球内部和在椭球外部的表面积分别是多少
这种题完全没思路,有没有大佬给点方法
#快手笔试##笔试题目##快手#