笔试编程题

有选择题

三道编程题

第一题：

输入

1 3

2 5

第一行是有n个信封，后面的每一行是n个信封的长和宽，只有小信封的长款大小比大信封小才能套进去，问最多能套多少个信封？

import sys

if __name__ == "__main__":
    # 读取第一行的n
    n = int(sys.stdin.readline().strip())
    ans = []
    for i in range(n):
        # 读取每一行
        line = sys.stdin.readline().strip()
        # 把每一行的数字分隔后转化成int列表
        values = list(map(int, line.split()))
        ans.append(values)
    print(ans)
    ans.sort(key=lambda x: (x[0], x[1]))
    print(ans)
    dp = [0 for i in range(n)]
    for i in range(1, n):
        hope = []
        for j in range(0, i):
            if ans[i][1] > ans[j][1]:
                hope.append(dp[j]+1)
        if  len(hope)!=0:
            print(hope)
            dp[i] = max(hope)

    print(dp[-1])

第二题：

输入数组的长度n和一个数组，全是整数，求乘积为正数的最大连续数组的长度

import sys

if __name__ == "__main__":
    # 读取第一行的n
    line = sys.stdin.readline().strip()
    values = list(map(int, line.split()))
    n = len(values)
    dp = [0]
    p = -1
    for i in range(n):
        if values[i]>0:
            dp.append(dp[-1]+1)
        elif values[i]==0:
            dp.append(0)
            p = -1
        else:
            if p!=-1:
                dp.append(dp[p-1]+dp[-1]+2)
                p = -1
            else:
                dp.append(0)
                p = i+1
    print(dp)
    print(max(dp))

这个题目的case全过，但是代码是有问题的比如

0 0 1 1 -1 -1 -1  1 2 3 4  应该是6 但是输出4

如果牛友有很好的方法，欢迎戳我

第三题：

也是一个字符串，找到最长的回文子串

输入

abnca

输出 3 （a+a与a之间任意字母+a）

import sys

if __name__ == "__main__":
    line = list(sys.stdin.readline().strip())
    dp = [[1 for j in range(len(line))] for i in range(len(line))]
    for j in range(0, len(line)):
        for i in range(j-1, -1, -1):
            if j - i == 1:
                if line[i] == line[j]:
                    dp[i][j] = 2
                else:
                    continue
            else:
                for x in range(i, j ):
                    if line[x] == line[j] and j - x > 1:
                        print(x,i,j)
                        dp[i][j] = max(dp[x + 1][j - 1] + 2,dp[i][j] ,dp[i][j-1])
                    elif line[x] == line[j] and j - x == 1:
                        dp[i][j] = max(2,dp[i][j] ,dp[i][j-1])
                    else:
                        dp[i][j] = max( dp[i][j], dp[i][j - 1])
    print(dp[0][-1])

题目要求时间O(n^2) 我的方法是O(n^3) （笔试时还没写完，后面写的呜呜呜）

#笔试算法题#