大厂数据结构与算法题总结

Myth丶恋晨 2023-07-18 06:55 32阅读 0赞

## sys.stdin.readline()和input()的区别 ##

sys.stdin.readline( )会将标准输入全部获取，包括末尾的’\\n’

input()会把‘\\n’忽略

import sys
    print('Plase input your name: ')
    name = sys.stdin.readline()
    print('Hello ', len(name))

![在这里插入图片描述][20200325095952138.png]  
从上面的小例子可以看出，sys.stdin是一个标准化输入的方法。  
python3中使用sys.stdin.readline()可以实现标准输入，其中默认输入的格式是字符串，如果是int，float类型则需要强制转换。

import sys
    try:
        while True:
            print('Please input a number:')
            n = int(sys.stdin.readline().strip('\n')) #strip('\n')表示以\n分隔，否则输出是“字符串+\n”的形式
            print('Please input some numbers:')
            sn = sys.stdin.readline().strip()#若是多输入，strip()默认是以空格分隔，返回一个包含多个字符串的list。
            if sn == '':
                break
            sn = list(map(int,sn.split())) #如果要强制转换成int等类型，可以调用map()函数。
            print(n)
            print(sn,'\n')
    except:
        pass

## 如何接收输入多个坐标 ##

先输入坐标个数，再依次输入坐标，将每个坐标由y从大到小存入列表中以便于后期处理。

n=int(input())
    res=[]
    for i in range(n):
        line=[int(item) for item in input().split()]
        res.append(line)

![在这里插入图片描述][20200325112436668.png]

## 字节：最大坐标点![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dGREdGSFNEUw_size_16_color_FFFFFF_t_70] ##

按照y从大到小排序，然后x从小到大选择，x值比前一个大的y值肯定比前一个大（y从大到小排列），从而是“最大的”点```
    或者理解为对y轴从大到小排序，然后记录输出的点的x轴，若下一点的x大于刚输出点的x则也为最外围点。

import sys
    n = int(sys.stdin.readline().strip())
    point=[]
    for i in range(n):
        point.append(list(map(int, sys.stdin.readline().strip().split())))
        point.sort(key=lambda k:k[1],reverse=True)
    
    res = []
    res.append(point[0])
    for i in  range(1,len(point)):
        if point[i][0] > res[-1][0]:
            res.append(point[i])
        else:
            continue
    res.sort(key=lambda k:k[0])
    for i in res:
        print(i[0],i[1])

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dGREdGSFNEUw_size_16_color_FFFFFF_t_70 1]

## 字节：最大区间数 ##

给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：
    区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列  [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:
    
    [6] = 6 * 6 = 36;
    
    [2] = 2 * 2 = 4;
    
    [1] = 1 * 1 = 1;
    
    [6,2] = 2 * 8 = 16;
    
    [2,1] = 1 * 3 = 3;
    
    [6, 2, 1] = 1 * 9 = 9;
    从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。区间内的所有数字都在[0, 100]的范围内

时间复杂度为O（n）算法：
    对序列维护一个单调非减的栈。遍历输入数组，当栈不为空且栈顶元素大于当前的值时，栈顶出栈，并记录现在还留在栈中但需要出栈总和(pop_sum),还要记录在出栈元素之前出栈的总和,用stack_pop_before来记录栈中每个元素在加入栈前需要出栈的总和，也就是说，因为栈中的某些元素在加入栈前需要让其前面的一些元素出栈，而后面的结果计算需要用这部分已经出栈的元素，故要增加一个辅助的栈记录。

n=int(raw_input())
    arr=[int(x) for x in raw_input()[:-1].split(' ')]
     
    arr.append(-1)
    i=0
    stack_pop_before=[]
    stack=[]
    ans=0
    while i<=n:
        num=arr[i]
        pop_sum=0
        pop_before=0
        while stack and num<stack[-1]:
            pop_num=stack.pop()
            pop_sum+=pop_num
            pop_before+=stack_pop_before.pop()
            ans=max(ans,(pop_before+pop_sum)*pop_num)
        stack_pop_before.append(pop_before+pop_sum)
        stack.append(num)
        i+=1
    print ans

## 快手：运动会 ##

一年一度的快手运动会又要开始了，同学们终于有一天可以离开鼠标键盘显示器，全身心的投入到各种体育项目中。UED设计师小红虽然没有参加体育项目，但她的责任重大，因为她是拉拉队的队长，她需要在每个项目中为参赛的同学们加油助威。
    因为运动会的项目众多，很多项目在同一时间会同时进行着。作为拉拉队长，小红需要遵守以下规则：
    不能同时给多个体育项目加油助威
    给每个体育项目加油的时长必须超过项目时长的一半，每个体育项目只能加油一次
    体育项目的开始和结束时间都是整点，如果项目进行到一半想要离开，也只能选择整点离开
    不考虑往返于各个体育项目比赛场地中花费的时间
    请帮小红设计一个算法，在已知所有体育项目日程的前提下，计算是否能在每个体育项目中为参赛的同学们加油。
    说明：
    如果体育项目时长为2，超过时长的一半为2;
    
    如果体育项目时长为3，超过时长的一半为2;
    
    如果体育项目时长为4，超过时长的一半为3；

def f():
        n=int(input())
        events=[]
        for i in range(n):
            line=[int(item) for item in input().split()]
            events.append(line)
        events=sorted(events,key=lambda x:x[1]-(x[1]-x[0])//2-1)
        start=events[0][0]
        for i in range(n):
            if start>events[i][1]-(events[i][1]-events[i][0])//2-1):
                return -1
            end=start+(events[i][1]-events[i][0])//2+1
            if i==n-1:
                return 1
            start=max(end,events[i+1][0])
        return 1
    ans=f()
    print(ans)

## 快手：合法跳跃分数 ##

有位老铁设计了一个跳格子游戏，游戏有N个格子顺序排成一行，编号从1到N，每个格子有点数Qi，有标记Li（标记的范围是1-M），每次跳格子，要选择一个格子a，以任意正偶数距离x跳到格子b，如果格子b在游戏区域内，且La=Lb，则称为一次合法跳跃，获得的分数是(a + b) * (Qa + Qb)。
    在继续设计游戏玩法时，这位老铁纠结了很久，于是他决定放弃……但是他想知道所有合法跳跃总共能获得多少分。

while True:
        try:
            n, m = list(map(int, input().strip().split()))
            q = list(map(int, input().strip().split()))
            l = list(map(int, input().strip().split()))
            sum = 0
            for i in range(0, n):
                for j in range(i + 2, n, 2):
                    if l[i] == l[j]:
                        sum += (i + j + 2) * (q[i] + q[j])
                        if sum > 10007:
                            sum %= 10007
            print(sum)
        except:
            break

## 约瑟夫中的丢手绢 ##

# 丢手绢问题
    # 游戏规则： 有N个小朋友玩丢手绢游戏，做成一圈，从第一个小朋友开始数数，从一开始数，数到指定数字的小朋友要出列，然后下一个小朋友继续从1开始数，依次类推，算出最后一个留下来的小朋友是谁？
    
    #!/usr/bin/python
    #coding:utf-8
    
    if __name__=="__main__":
    
        pcount = 6   # 丢手绢的小朋友数量
        out_num = 4  # 指定捡手绢的小朋友位数
        num_list = [i for i in range(1,pcount+1)] # 将小朋友排成一列
        print_list = []  # 记录出局小朋友
        i = 0   # 手绢
        index = -1   # 当前拿到手绢的小朋友
    
        while True:
            i += 1
            index += 1
            # 如果手绢在最后一个小朋友手里要传回到第一
            if index>=len(num_list) or index<0:
                index = 0
    
            # 当前要移除的小朋友
            if i==out_num:
                i = 0
                is_add = 0
    
                # 判断是否是最后一个小朋友，如果不是，那么小朋友被移除，
                # 后面的小朋友要向前走一步
                if index <len(num_list)-1:
                    is_add = -1
    
                print_list.append(num_list[index])
                del num_list[index]
    
                index += is_add
    
            # 只剩下一个小朋友，游戏结束
            if len(num_list)==1:
                print_list.append(num_list[0])
                break
    
        # 打印出小朋友出局的顺序
        for item in print_list:
            print("%s, " % item)

## 快手：丢手绢（不同于约瑟夫中的丢手绢） ##

有n 个老铁（编号为 1 到n）正在玩丢手绢。在游戏里每人会把当前手里的手绢丢给一个固定的人，编号为Ti。 游戏开始时，每人手里有自己的手绢。之后每一轮中，所有人会同时将自己当前手里的手绢全部丢给接收的对象。当有人重新拿到自己的手绢时，游戏结束。
    
    那么游戏几轮会结束呢？

def f():
        n = int(input())
     
        to = [int(item) - 1 for item in input().split()]
        in_degree = [0] * n
        for i in range(n):
            in_degree[to[i]] += 1
        stack = []
        for i in range(n):
            if in_degree[i] == 0:
                stack.append(i)
        while len(stack) != 0:
            top = stack[-1]
            in_degree[top] -= 1  # in_degree==-1,则代表删除了
            stack.pop(-1)
            in_degree[to[top]] -= 1
            if in_degree[to[top]] == 0:
                stack.append(to[top])
        min_num = 200000
        for i in range(n):
            if in_degree[i] == -1:
                continue
            else:
                start = i
                num = 1
                while to[i] != start:
                    i = to[i]
                    num += 1
                    in_degree[i] = -1  # 同一个圈内的就不重复计算环了
                min_num = min(min_num, num)
        return min_num
     
     
    ans = f()
    print(ans)

## 快手：滑动窗口的最大值（最大池化操作） ##

while True:
        try:
            n = int(input())
            nums = list(map(int, input().split()))
            ks = int(input())
            res = []
            res.append(max(nums[:ks]))
            for i in range(1, n - ks + 1):
                if nums[i-1] == res[-1]:# 如果最大值是窗口的第一位，则在下一轮中需比较窗口所有的值，因为不确定那个大。
                    res.append(max(nums[i:i+ks]))
                else:# 如果最大值不是窗口的第一位，则在下一轮中只需比较最大值与窗口中的最后一位！
                    res.append(max(res[-1], nums[i + ks - 1]))
            res = [str(i) for i in res]
            print(' '.join(res))
        except:
            break
        '''
        while True:
        try:
            n = int(input())
            nums = list(map(int, input().split()))
            k = int(input())
            res = []
            max_n = max(nums[:k])
            res.append(max_n)
            i = 0
            while i < n-k:
                if max_n == nums[i]:
                    max_n = max(nums[i+1:i+k+1])
                else: # 如果最大值不是窗口的第一位，则在下一轮中只需比较最大值与窗口中的最后一位
                    max_n = max(max_n, nums[i+k])
                i += 1
                res.append(max_n)
            print(' '.join(str(i) for i in res))
     
        except:
            break
            '''

[20200325095952138.png]: /images/20230528/76228fcf04394c2faa8fa9c01e2187d8.png
[20200325112436668.png]: /images/20230528/02ec410f81b7488a8822797b0eed4679.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dGREdGSFNEUw_size_16_color_FFFFFF_t_70]: /images/20230528/610ffc284c7c4d89810355f879ecb250.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dGREdGSFNEUw_size_16_color_FFFFFF_t_70 1]: /images/20230528/6e0008edc83b4b6790d24b6d4413ea25.png