08 16 老虎集团 笔试 后端开发 Python

分析

2道编程，10道选择，选择的分值还是挺重的。

1

给定非递减序列如[-8 -4 -3 0 1 2 4 5 8 9]和数k，找出不重复的两数和为k的数对。要求时间复杂度O(n)，空间O(1)

示例输出 K=10
1 9
2 8

• 思路就是左右双指针向中间遍历，注意需要判断是不是和上一对重复了。

while True:
    try:
        n,k = list(map(int,input().split()))
        nums = list(map(int,input().split()))

        left,right = 0,n-1
        while left < right:
            if nums[left] + nums[right] < k:
                left += 1
            elif nums[left] + nums[right] == k:
                if left == 0 or right == n-1:
                    print("{} {}".format(nums[left],nums[right]))
                elif left-1>=0 and nums[left-1]!=nums[left] and right+1<n and nums[right+1]!=nums[right]:
                    print("{} {}".format(nums[left],nums[right]))
                left += 1
                right -= 1
            else:
                right -= 1
    except:
        break

2.

给定的数组，通过两次操作计算剩下的数组和的最小值。该操作定义：选取数字x，所有大于等于x的数字减去x。

• 两次选择之间好像是有关联的，一开始分别求每一阶段的最优只A了50
• 然后换成了暴力怼，A到60

class Solution:
    def minimumValueAfterDispel(self , nums ):
        # write code here
        if len(nums) <= 1:return 0

        min_val = 1e9
        nums.sort()
        unique_vals = set(nums)
        for val in unique_vals:
            nnums = nums.copy()
            for i in range(len(nnums)):
                if nnums[i] >= val:
                    nnums[i] -= val
            next_vals = self.calc_max_minus(nnums)
            for i in range(len(nnums)):
                if nnums[i] >= next_vals:
                    nnums[i] -= next_vals
            min_val = min(min_val,sum(nnums))
        return min_val

    def calc_max_minus(self,nums):
        nums.sort()
        length = len(nums)
        _max = 0
        _val = 0
        for i,val in enumerate(nums):
            cur_val = val * (length -i)
            if cur_val > _max:
                _max = cur_val
                _val = val
        return _val

总结

还是菜