08.30 中国电信 天翼云 算法笔试
第一题：贪心算法里的重叠问题（原A 50%，修改后下面代码不知道能不能全A）
from typing import List
class Solution:
def SumLength(self, lines: List[List[int]]) -> int:
if not lines:
return 0
n = len(lines)
if n == 1:
return lines[0][1] - lines[0][0]
lines.sort(key=lambda x: (x[0], x[1]))
for i in range(1, n):
if lines[i][0] < lines[i - 1][1]:
lines[i][0], lines[i - 1][1] = lines[i - 1][1], lines[i][0]
res = 0
for i in range(n):
if lines[i][0] >= lines[i][1]:
continue
else:
res += lines[i][1] - lines[i][0]
return res
if __name__ == "__main__":
sl = Solution()
N = int(input())
Lines = list()
for _ in range(N):
Lines.append(list(map(int, input().split(","))))
print(sl.SumLength(Lines)) 第二题：奇偶数排序（AC） from typing import List
class Solution:
def reOrderArray(self, nums: List[int]):
j_list = []
o_list = []
for num in nums:
if num % 2 == 0:
o_list.append(num)
if num % 2 == 1:
j_list.append(num)
return o_list + j_list
if __name__ == "__main__":
sl = Solution()
N = int(input())
arr = list(map(int, input().split(",")))
ans = sl.reOrderArray(arr)
print(",".join([str(i) for i in ans])) 第三题：01背包问题（AC）
from typing import List class Solution: def MaxSumValue(self, m: int, values: List[int], cost: List[int]): n = len(cost) dp = [[0] * (m + 1) for _ in range(n)] for i in range(n): dp[i][0] = 0 for j in range(m + 1): if j < cost[0]: dp[0][j] = 0 else: dp[0][j] = cost[0] for i in range(n): for j in range(m + 1): if j < cost[i]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + values[i]) return dp[n - 1][m] if __name__ == "__main__": sl = Solution() M = int(input()) list_1 = list(map(int, input().split())) list_2 = list(map(int, input().split())) N = list_1[0] print(sl.MaxSumValue(M, list_1[1:], list_2[1:]))