春招第五次算法笔试--开心消消乐 服务端开发岗

一共四道算法题，完成两道，还有一道最后1s发现问题，但已经来不及了，最后一道没看

1.不难，算两个数组范围的最大交叉部分

# 计算紫色最大连续长度
# @param redSegments Interval类一维数组 小狐狸每次涂色的起始和结束位置
# @param blueSegments Interval类一维数组 小河马每次涂色的起始和结束位置
# @return int整型
#
from typing import List
class Interval:
    def __init__(self, a=0, b=0):
        self.start = a
        self.end = b
    def printf(self):
        print(f"start={self.start}, end={self.end}")
class Solution:
    def GetMaxPurpleLength(self , redSegments: List[Interval], blueSegments: List[Interval]) -> int:
        def list_to_set(Segments: List[Interval]):
            # 将像 [2, 4] 的范围转化为 {2,3} 的集合
            segment_set = set()
            for segment in Segments:
                # segment.printf()
                for i in range(segment.start, segment.end):
                    segment_set.add(i)
            return segment_set
        red_set = list_to_set(redSegments)
        blue_set = list_to_set(blueSegments)
        in_red_and_blue = []
        for i in red_set:
            if i in blue_set:
                in_red_and_blue.append(i)
        in_red_and_blue.sort()
        last = 0
        now_num = 0
        max_num = 0
        # print(in_red_and_blue)
        for i in in_red_and_blue:
            if i - 1 == last:
                last = i
                now_num += 1
                # print("add", last, i, now_num, max_num)
            else:
                if now_num > max_num:
                    max_num = now_num
                last = i
                now_num = 1
                # print("put", last, i, now_num, max_num)
        if now_num > max_num:
            max_num = now_num
        return max_num
        
if __name__=="__main__":
    red = [[2,5],[5,11]]
    blue = [[2,7], [16,115]]
    redSegments = []
    for ll in red:
        redSegments.append(Interval(*ll))
    blueSegments = []
    for ll in blue:
        blueSegments.append(Interval(*ll))
    re = Solution().GetMaxPurpleLength(redSegments=redSegments, blueSegments=blueSegments)
    print(re)

2.计算各个数位上的数字均不同的整数个数，转换思路，每次算1位数，2位数.. ，相当于计算 C(9,1)*A(9,n-1)

# 统计各个数位上的数字均不同的整数个数
# @param n int整型 十进制n位数
# @return int整型
#
class Solution:
    def answer(self , n ):
        def get_the_k(k):
            if k == 0:
                return 1
            elif k == 1:
                return 9
            A = 1
            num = 9
            for _ in range(k-1):
                A *= num
                num -= 1
            return 9 * A
        sum = 0
        n = min(n, 10)
        for i in range(n+1):
            sum += get_the_k(i)
            # print(i, get_the_k(i))
        return sum

if __name__=="__main__":
    re = Solution().answer(4)
    print(re)

3.这题有点可惜，一开始没注意需要索引，而且索引是从1开始的，这两个细节导致我全错了

没注意需要索引，一开始就把myOptions排序了

没注意到索引是从1开始的，导致我使用枚举，结果都小了1

from typing import List
class Solution:
    def helpMeWin(self , bossDamages: List[int], myOptions: List[List[int]]) -> List[int]:
        # write code here
        bossDamages.sort()
        for ll in myOptions:
            ll.sort()
        def jisaun(options:list):
            blue = 0
            for i in bossDamages:
                for j in options:
                    if j >= i:
                        blue += j
                        break
            return blue
        def can_use(options:list):
            if options[-1] >= bossDamages[-1]:
                return True
            return False
        can_use_options = []
        for options in myOptions:
            if can_use(options):
                can_use_options.append(options)
        if len(can_use_options) == 0:
            return []
        min_blue = 10000
        min_index = []
        for index, options in enumerate(myOptions):
            if not can_use(options):
                continue
            # print(index, options)
            blue = jisaun(options)
            # print(blue)
            if blue == min_blue:
                min_index.append(index+1)
                # print(min_blue, min_index)
            if blue < min_blue:
                min_index = [index+1]
                min_blue = blue
                # print(min_blue, min_index)
        return min_index

if __name__ =="__main__":
    bossDamages = [8,12,9]
    myOptions = [[8,14],[9,13]]
    re = Solution().helpMeWin(bossDamages=bossDamages, myOptions=myOptions)
    print(re)