笔试编程题
有选择题
三道编程题
第一题：
输入
2
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 如果牛友有很好的方法，欢迎戳我
第三题：
也是一个字符串，找到最长的回文子串
输入
5
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) （笔试时还没写完，后面写的呜呜呜）
