笔试记录 平安科技 20200918 算法

笔试记录 平安科技 20200918 算法

1个半小时，选择题(8道单选、11道多选），3道编程题

1. 圆圈上删数 （AC)

圆圈上有0 ~n-1 共n个数字，从0开始，每次从中删除第m个数字，求最后剩下的一个数字

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param n int整型 数列大小
# @param m int整型 删除位数
# @return int整型
#
class Solution:def JosephCircle(self, n, m):# write code herecircle = [i for i in range(n)]ind = 0while len(circle) > 1:ind = (ind + m - 1) % len(circle)circle.pop(ind)return circle[0]

2. 合并两个有序数组 (AC)

类似于LeetCode 21. 合并两个有序链表

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# Get merged sorted list
# @param Input1 int整型一维数组 数组1
# @param Input2 int整型一维数组 数组2
# @return int整型一维数组
#
class Solution:def sorted_two_list(self , Input1 , Input2 ):# write code hereans = []while len(Input1) and len(Input2):if Input1[0] <= Input2[0]:ans.append(Input1[0])Input1.pop(0)else:ans.append(Input2[0])Input2.pop(0)if len(Input1):ans += Input1elif len(Input2):ans += Input2return ans

3. 找出两个正序数组的中位数 （AC）

复杂度 O ( log ⁡ ( m + n ) ) O(log(m+n)) O(log(m+n))
log ⁡ log log 说明得用二分查找，LeetCode 4. 寻找两个正序数组的中位数

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param nums1 int整型一维数组
# @param nums2 int整型一维数组
# @return float浮点型
#
class Solution:def findMedianSortedArrays(self, nums1, nums2):# write code heredef getKthElement(k):ind1, ind2 = 0, 0while True:if ind1 == len1:return nums2[ind2 + k - 1]if ind2 == len2:return nums1[ind1 + k - 1]if k == 1:return min(nums1[ind1], nums2[ind2])newind1 = min(ind1 + k // 2 - 1, len1 - 1)newind2 = min(ind2 + k // 2 - 1, len2 - 1)p1, p2 = nums1[newind1], nums2[newind2]if p1 < p2:k -= newind1 - ind1 + 1ind1 = newind1 + 1else:k -= newind2 - ind2 + 1ind2 = newind2 + 1len1 = len(nums1)len2 = len(nums2)total_l = len1 + len2if total_l % 2:return getKthElement((total_l + 1) >> 1)else:return (getKthElement(total_l // 2) + getKthElement(total_l // 2 + 1)) / 2.