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:]))

#电信天翼云计算##中国电信##笔经#